C语言数据结构之图的遍历实例详解
成都创新互联公司服务项目包括洛浦网站建设、洛浦网站制作、洛浦网页制作以及洛浦网络营销策划等。多年来，我们专注于互联网行业，利用自身积累的技术优势、行业经验、深度合作伙伴关系等，向广大中小型企业、政府机构等提供互联网行业的解决方案，洛浦网站推广取得了明显的社会效益与经济效益。目前，我们服务的客户以成都为中心已经辐射到洛浦省份的部分城市，未来相信会继续扩大服务区域并继续获得客户的支持与信任！
输入一组顶点，建立无向图的邻接矩阵。输入一组顶点，建立有向图的邻接表。分别对无向图和有向图进行DFS（深度优先遍历）和BFS（广度优先遍历）。写出深度优先遍历的递归和非递归算法。根据建立的有向图，判断该图是否是有向无环图，若是，则输出其一种拓扑有序序列。
实现代码：
#include
#include
#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;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;
}
}
}
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;vnextarc)
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语言数据结构之图的遍历实例详解
分享链接：
http://cxhlcq.com/article/ihdjig.html
重庆分公司
重庆分公司
