微客导航 » 文章资讯 » C语言数据结构之图的遍历实例详解

C语言数据结构之图的遍历实例详解

2024-02-17 10:00:03 244

C语言数据结构之图的遍历实例详解

输入一组顶点，建立无向图的邻接矩阵。输入一组顶点，建立有向图的邻接表。分别对无向图和有向图进行DFS（深度优先遍历）和BFS（广度优先遍历）。写出深度优先遍历的递归和非递归算法。根据建立的有向图，判断该图是否是有向无环图，若是，则输出其一种拓扑有序序列。

实现代码：

#include
#include
#defineMAX20

typedefstructArcNode{
intadjvex;
structArcNode*nextarc;
}ArcNode;

typedefstruct{
chardata;
ArcNode*firstarc;
}AdjList[MAX];

typedefstruct{
AdjListvertices;
intvexnum;
intarcnum;
}ALGraph;

typedefstruct{
int*base;
intfront,rear;
}CqQueue;

voidInitQueue(CqQueue&Q)
{//初始化一个队列
Q.base=(int*)malloc(MAX*sizeof(int));
Q.front=Q.rear=0;
}

intQueueEmpty(CqQueueQ)
{//判断队列是否为空
if(Q.rear==Q.front)
return1;
return0;
}

voidEnQueue(CqQueue&Q,inte)
{//入队操作
if((Q.rear+1)%MAX==Q.front)
return;
Q.base[Q.rear]=e;
Q.rear=(Q.rear+1)%MAX;
}

voidDeQueue(CqQueue&Q,int&e)
{//出队操作
if(Q.rear==Q.front)
return;
e=Q.base[Q.front];
Q.front=(Q.front+1)%MAX;
}

intLocateVex(ALGraphG,charv)
{//查找顶点v在图G中的位置
for(inti=0;iadjvex=j;
s->nextarc=NULL;
if(!G.vertices[i].firstarc)
G.vertices[i].firstarc=s;
else{
p=G.vertices[i].firstarc;
while(p->nextarc)
p=p->nextarc;
p->nextarc=s;
}
s=(ArcNode*)malloc(sizeof(ArcNode));
s->adjvex=i;
s->nextarc=NULL;
if(!G.vertices[j].firstarc)
G.vertices[j].firstarc=s;
else{
p=G.vertices[j].firstarc;
while(p->nextarc)
p=p->nextarc;
p->nextarc=s;
}
}
}

intvisited[MAX];

voidDFS(ALGraphG,intv)
{//从顶点v开始对图G进行深度优先搜索
ArcNode*p;
printf("%3c",G.vertices[v].data);
visited[v]=1;
for(p=G.vertices[v].firstarc;p;p=p->nextarc)
if(!visited[p->adjvex])
DFS(G,p->adjvex);
}

voidDFSTraverse(ALGraphG)
{//对用邻接表存储的无向图G进行深度优先遍历
intv;
for(v=0;vnextarc)
if(!visited[p->adjvex]){
printf("%3c",G.vertices[p->adjvex].data);
visited[p->adjvex]=1;
EnQueue(Q,p->adjvex);
}
}
}
}

intmain(){
ALGraphG;
printf("建立无向图的邻接表：\n");
CreateAdjList(G);
printf("无向图的深度优先遍历序列如下：\n");
DFSTraverse(G);
printf("\n\n无向图的广度优先遍历序列如下：\n");
BFSTraverse(G);
printf("\n");
return0;
}

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

返回顶部
3162201930
czq8825@qq.com

C语言数据结构之图的遍历实例详解

热门推荐

随机推荐