/*************************************************************************************
以下函数建立图的邻接表结构,并实现图的深度和广度优先搜索,深度优先生成树,广度优先
生成树,结点之间连通性判断,最小生成树(普尼姆算法和克鲁斯卡尔算法),拓扑排序,最短
路径和关键路径等算法。
图的存储结构定义在WORK18.H中
编写者:黄海于
2002、12、6
*************************************************************************************/
#include "work18.h"
/*************************************************************************************
函数:Graph CreateGraph(int Choice);
功能:根据用户要求建立有向图、网和无向图、网的邻接表存储结构
形式参数:
Choice: 对于无向图而言,输入大于1的值,对于有向图的入表,则输入0,
对于有向图的出表,则输入1。
函数输出:
指向邻接表存储结构第一个存储单元的指针
*************************************************************************************/
Graph CreateGraph(int Choice)
{
Graph G;
int i;
char Head[20],Tail[20],*stemp,*htemp;
float weight;
//分配内存
G=(Graph)malloc(sizeof(ALGraph));
//输入图的类型
printf("Please input the type of Graph:\n");
if(Choice<=1){
printf("0: diGraph\n");
printf("1: diNetwork\n");
}
else{
printf("2: UndiGraph\n");
printf("3: UndiNetwork\n");
}
printf("Choice:");
scanf("%d",&G->kind);
//输入顶点数目和弧的数目
printf("Please input number Arc:");
scanf("%d",&G->arcnum);
//输入所有的弧或线段
printf("please input each Arc in the Graph\n");
//输入所有的弧或线段,若为有向图,则按起点和终点输入方式,
//结点名为字符串,不超过20个字节
G->vexnum=0;
G->vertices=(AdjList)malloc(sizeof(VNode)*(G->vexnum+1));
for(i=0;i<G->arcnum;i++){
//每条弧的起点和终点,对于图而言,不需要输入权值
printf("Input Arc %d ==> Tail Head",i+1);
if(G->kind==1 || G->kind==3)
printf(" weight");
printf(":");
scanf("%s%s",Tail,Head);
if(G->kind==1 || G->kind==3)
scanf("%f",&weight);
else
weight=0;
stemp=Tail;
htemp=Head;
//如果是有向图且为出表或者为无向图
if(Choice<=0)
InsertNode(htemp,stemp,G,weight);
//如果是有向图且为入表
else
InsertNode(stemp,htemp,G,weight);
}
return G;
}
/*************************************************************************************
函数:void InsertNode(char *stemp,char *htemp,Graph G,float weight);
功能:根据输入的信息,在邻接表中插入一个结点。
形式参数:
stemp: 弧的一个顶点名,对有向图而言为起点。
htemp: 弧的一个顶点名,对有向图而言为终点。
G: 指向图邻接表存储结构的指针
weight: 弧上的权值,如果为图,则输入0,否则输入实际的权值
函数输出:
无
*************************************************************************************/
void InsertNode(char *stemp,char *htemp,Graph G,float weight)
{
int pos,prepos;
//确定是否需要将输入的弧插入到邻接表连续存储空间中,并得到插入位置
prepos=InsertStr(stemp,G);
pos=InsertStr(htemp,G);
//插入结点
InsNode(prepos,pos,G,weight);
//如果为无向图,则需要在链表中插入两次
switch(G->kind){
case AG:
case AN:
InsNode(pos,prepos,G,weight);
break;
}
return;
}
/*************************************************************************************
函数:int InsertStr(char *stemp,Graph G);
功能:在图的邻接表存储结构中查找是否有值为stemp的结点,如果无,则插入,如果有,则
只返回该结点的相对位置。
形式参数:
stemp: 弧的一个顶点名
G: 指向图邻接表存储结构的指针
函数输出:
该结点名在邻接表中的相对位置
*************************************************************************************/
int InsertStr(char *stemp,Graph G)
{
int i;
char *ctemp;
//指向0号存储单元
ctemp=G->vertices[0].data;
//查找此前的所有存储单元,如果该结点名已经存在,则不再保留
for(i=0;i<G->vexnum;i++){
ctemp=G->vertices[i].data;
if(strcmp(stemp,ctemp)==0)
break;
}
//若不存在,则保存该结点,并增加结点数目
if(i==G->vexnum){
ctemp=G->vertices[i].data;
strcpy(ctemp,stemp);
G->vertices[i].firstarc=NULL;
G->vertices[i].visited=0;
G->vertices[i].Indegree=0;
G->vertices[i].Outdegree=0;
G->vexnum++;
G->vertices=(AdjList)realloc(G->vertices,sizeof(VNode)*(G->vexnum+1));
}
return i;
}
/*************************************************************************************
函数:void InsNode(int pos1,int pos2,Graph G,float weight);
功能:根据弧或线段的信息,在邻接表中插入一个结点
形式参数:
pos1: 弧或线段的一个顶点在邻接表中的相对位置
pos2: 弧或线段的另一个顶点在邻接表中的相对位置
G: 指向图邻接表存储结构的指针
weight: 弧上的权值,如果为图,则输入0,否则输入实际的权值
函数输出:
无
*************************************************************************************/
void InsNode(int pos1,int pos2, Graph G,float weight)
{
ArcNode *p,*q;
//分配存储空间,并设置结点的信息
p=(ArcNode*)malloc(sizeof(ArcNode));
p->weight=weight;
p->adjvex=pos2;
p->nextarc=NULL;
//如果是第一个邻接点
if(G->vertices[pos1].firstarc==NULL)
G->vertices[pos1].firstarc=p;
//如果不是第一个邻接点,则成为链表中最后一个结点
else{
q=G->vertices[pos1].firstarc;
while(q->nextarc!=NULL)
q=q->nextarc;
q->nextarc=p;
}
G->vertices[pos1].Outdegree++;
G->vertices[pos2].Indegree++;
return;
}
/*************************************************************************************
函数:void DepthSearch(Graph G);
功能: 采用深度优先搜索方法遍历图中的所有结点
形式参数:
G: 指向图邻接表存储结构的指针,如果为有向图或网该,G为出表
函数输出:
无
*************************************************************************************/
void DepthSearch(Graph G)
{
int i;
//设置未访问标志
for(i=0;i<G->vexnum;i++)
G->vertices[i].visited=0;
for(i=0;i<G->vexnum;i++){
if(G->vertices[i].visited==0)
DepthOneSearch(G,i);
}
return;
}
/*************************************************************************************
函数:void DepthOneSearch(Graph G,int i);
功能:从某个结点出发,一次深度优先搜索图的邻接表结构
形式参数:
G: 指向图邻接表存储结构的指针
i: 该结点在邻接表中的相对位置
函数输出:
无
*************************************************************************************/
int DepthOneSearch(Graph G,int i)
{
int j=0,visited=0;
ArcNode *p,**Node,*q;
Node=(ArcNode **)malloc(sizeof(ArcNode)*(j+1));
//访问第一个结点,该结点一定是没有被访问过
printf("%s ",G->vertices[i].data);
G->vertices[i].visited=1;
visited++;
//指向其第一个邻接点
p=G->vertices[i].firstarc;
//循环直到条件满足后自动返回
while(1){
//如果当前顶点的邻接点不为空并且该邻接点已经访问过,则找其下一个邻接点
while( p!=NULL && G->vertices[p->adjvex].visited==1)
p=p->nextarc;
//q指向当前未访问结点
q=p;
//如果当前已经访问完该结点的所有邻接点,则从堆栈中弹出下一个要访问的邻接点
if(p==NULL){
//如果堆栈中还有未访问的邻接点,则弹出一个未曾访问的邻接点
if(j>0){
//在堆栈中查找未访问过的邻接点
do{
j--;
p=Node[j];
}while(j>=0 && G->vertices[p->adjvex].visited!=0);
//如果栈中没有未被访问的元素,则遍历结束,并释放空间
if(j<0){
free(Node);
return visited;
}
//查找该结点后面未曾访问过的结点
q=p;
while(q->nextarc!=NULL &&
G->vertices[q->nextarc->adjvex].visited==1)
q=q->nextarc;
}
//如果堆栈为空,并且该结点的所有邻接点都访问过,则退出�
《数据结构》算法实现源代码
5星 · 超过95%的资源 需积分: 12 21 浏览量
2009-11-22
10:56:58
上传
评论 8
收藏 83KB RAR 举报
hyhuangsc
- 粉丝: 0
- 资源: 8
最新资源
- 202304910142原道明(1).pbix
- 文本.txt
- 基于Lua的聊天过滤修改版设计源码
- A1_SSE_123090177.py
- Uibot6.0 (RPA财务机器人师资培训第5天 ) 报销汇总机器人案例实战
- 基于Vue的西安美食攻略应用程序设计源码
- tensorflow-2.6.2-cp38-cp38-win-amd64.whl
- 2023-04-06-项目笔记 - 第八十六阶段 - 4.4.2.84全局变量的作用域-84 -2024.03.28
- 基于C语言解决九宫重排问题(源码+剖析)
- 考研分数计算神器(通过考研分数计算规则制作出来的计算工具,结果精准,操作简单,并且还可以与第二个人进行比较)
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
- 1
- 2
前往页