C语言数据结构之图的遍历实例详解
输入一组顶点，建立无向图的邻接矩阵。输入一组顶点，建立有向图的邻接表。分别对无向图和有向图进行DFS（深度优先遍历）和BFS（广度优先遍历）。写出深度优先遍历的递归和非递归算法。根据建立的有向图，判断该图是否是有向无环图，若是，则输出其一种拓扑有序序列。
实现代码：
#include <stdio.h>
#include <stdlib.h>
#define MAX 20
typedef struct ArcNode{
int adjvex;
struct ArcNode *nextarc;
}ArcNode;
typedef struct{
char data;
ArcNode *firstarc;
}AdjList[MAX];
typedef struct{
AdjList vertices;
int vexnum;
int arcnum;
}ALGraph;
typedef struct{
int *base;
int front,rear;
}CqQueue;
void InitQueue(CqQueue &Q)
{//初始化一个队列
Q.base=(int*)malloc(MAX*sizeof(int));
Q.front=Q.rear=0;
}
int QueueEmpty(CqQueue Q)
{//判断队列是否为空
if(Q.rear==Q.front)
return 1;
return 0;
}
void EnQueue(CqQueue &Q,int e)
{//入队操作
if((Q.rear+1)%MAX==Q.front)
return;
Q.base[Q.rear]=e;
Q.rear=(Q.rear+1)%MAX;
}
void DeQueue(CqQueue &Q,int &e)
{//出队操作
if(Q.rear==Q.front)
return;
e=Q.base[Q.front];
Q.front=(Q.front+1)%MAX;
}
int LocateVex(ALGraph G,char v)
{//查找顶点v在图G中的位置
for(int i=0;i<G.vexnum;i++)
if(G.vertices[i].data==v)
return i;
return -1;
for(int i=0;i<G.vexnum;i++)
if(G.vexs[i]==v)
return i;
return -1;
}
void CreateAdjList(ALGraph &G)
{//建立无向图的邻接表
int v,i,j,k;
char v1,v2;
ArcNode *p,*s;
printf("输入无向图的顶点数和边数：\n");
scanf("%d%d",&G.vexnum,&G.arcnum);
getchar();
printf("输入图的顶点信息：\n");
for(v=0;v<G.vexnum;v++){
scanf("%c",&G.vertices[v].data);getchar();
G.vertices[v].firstarc=NULL;
}
printf("输入无向图的边：\n");
for(k=0;k<G.vexnum;k++){
scanf("%c%c",&v1,&v2);
getchar();
i=LocateVex(G,v1);
j=LocateVex(G,v2);
s=(ArcNode*)malloc(sizeof(ArcNode));
s->adjvex=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;
}
}
}
int visited[MAX];
void DFS(ALGraph G,int v)
{//从顶点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);
}
void DFSTraverse(ALGraph G)
{//对用邻接表存储的无向图G进行深度优先遍历
int v;
for(v=0;v<G.vexnum;v++)
visited[v]=0;
for(v=0;v<G.vexnum;v++)
if(!visited[v])
DFS(G,v);
}
void BFSTraverse(ALGraph G)
{//对用邻接表存储的无向图G进行深度优先遍历
int u,v;
CqQueue Q;
ArcNode *p;
for(v=0;v<G.vexnum;v++)
visited[v]=0;
InitQueue(Q);
for(v=0;v<G.vexnum;v++)
if(!visited[v]){
printf("%3c",G.vertices[v].data);
visited[v]=1;
EnQueue(Q,v);
while(!QueueEmpty(Q)){
DeQueue(Q,u);
for(p=G.vertices[u].firstarc;p;p=p->nextarc)
if(!visited[p->adjvex]){
printf("%3c",G.vertices[p->adjvex].data);
visited[p->adjvex]=1;
EnQueue(Q,p->adjvex);
}
}
}
}
int main(){
ALGraph G;
printf("建立无向图的邻接表：\n");
CreateAdjList(G);
printf("无向图的深度优先遍历序列如下：\n");
DFSTraverse(G);
printf("\n\n无向图的广度优先遍历序列如下：\n");
BFSTraverse(G);
printf("\n");
return 0;
}
感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！
以上是 C语言数据结构之图的遍历实例详解 的全部内容， 来源链接： utcz.com/z/346640.html
