C语言数据结构之图的遍历实例详解
更新时间:2020年4月25日 17:30 点击:2022
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++中的菱形继承深入分析
下一篇: C++类中的继承实例详解
相关文章
- 这篇文章主要为大家详细介绍了C语言实现放烟花的程序,有音乐播放,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-02-23
- 本篇文章主要介绍C语言中char的知识,并附有代码实例,以便大家在学习的时候更好的理解,有需要的可以看一下...2020-04-25
- 这篇文章主要介绍了matplotlib绘制正余弦曲线图的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-22
- 这篇文章主要介绍了matplotlib bar()实现百分比堆积柱状图,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-24
- 这篇文章主要介绍了详解如何将c语言文件打包成exe可执行程序,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-25
- 这篇文章主要介绍了解决echarts 一条柱状图显示两个值,类似进度条的问题,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-07-20
- 这篇文章主要介绍了R语言基本画图函数与多图多线的用法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-05-06
- overlay就是在地图上以另外一种形式浮现在地图上,常见的地图覆盖物为这三种类型,如:popup 弹窗、label标注信息、text文本信息等,接下来跟随小编看下openlayers6之地图覆盖物overlay详解,一起看看吧...2021-09-15
- 采用CSS覆盖的方法就可以了,但是官方是不允许这么做的...2013-10-13
- 本篇文章是对GDI+简单绘图的绘图知识进行了详细的分析介绍,需要的朋友参考下...2020-06-25
- 这篇文章主要介绍了vue+高德地图实现地图搜索及点击定位操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-09-09
- 这篇文章主要介绍了如何使用JavaScript实现“无缝滚动 自动播放”轮播图效果,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2020-08-20
详解pandas.DataFrame.plot() 画图函数
这篇文章主要介绍了详解pandas.DataFrame.plot()画图函数,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-06-15- 这篇文章主要介绍了React使用高德地图的实现示例(react-amap),文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-04-18
- 这篇文章主要介绍了C#数据结构之队列(Quene),结合实例形式较为详细的讲述了队列的功能、原理与C#实现队列的相关技巧,需要的朋友可以参考下...2020-06-25
- free函数是释放之前某一次malloc函数申请的空间,而且只是释放空间,并不改变指针的值。下面我们就来详细探讨下...2020-04-25
- 这篇文章主要介绍了python进行相关性分析并绘制散点图,具有一定借鉴价值,需要的朋友可以参考下,希望能够给你带来帮助...2021-09-18
- 这篇文章主要介绍了如何用c# 实现实时曲线图,文中讲解非常细致,代码帮助大家更好参考和学习,感兴趣的朋友可以了解下...2020-11-03
- 这篇文章主要介绍了C语言中计算正弦的相关函数总结,包括正弦和双曲线正弦以及反正弦的函数,需要的朋友可以参考下...2020-04-25
详解C语言中的rename()函数和remove()函数的使用方法
这篇文章主要介绍了详解C语言中的rename()函数和remove()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25