C++实现图的邻接矩阵存储和广度、深度优先遍历实例分析
更新时间:2020年4月25日 17:39 点击:1895
本文实例讲述了C++实现图的邻接矩阵存储和广度、深度优先遍历的方法。分享给大家供大家参考。具体如下:
示例:建立如图所示的无向图
由上图知,该图有5个顶点,分别为a,b,c,d,e,有6条边.
示例输入(按照这个格式输入):
5
6
abcde
0 1 1
0 2 1
0 3 1
2 3 1
2 4 1
1 4 1
输入结束(此行不必输入)
注:0 1 1表示该图的第0个顶点和第1个定点有边相连,如上图中的a->b所示
0 2 1表示该图的第0个顶点和第2个定点有边相连,如上图中的a->c所示
2 3 1表示该图的第2个顶点和第3个定点有边相连,如上图中的c->d所示
实现代码如下:
#include <stdio.h> #define MAX_GRAPH 100 #define MAX_QUEUE 30 typedef struct { char vex[MAX_GRAPH]; /* 顶点 */ int edge[MAX_GRAPH][MAX_GRAPH]; /* 邻接矩阵 */ int n; /* 当前的顶点数 */ int e; /* 当前的边数 */ }GRAPH; void Create(GRAPH *G); /* 图的邻接矩阵表示法 */ void BFS(GRAPH *G,int k); /* 广度优先遍历 */ void DFS(GRAPH *G,int k); /* 深度优先遍历 */ int visited[MAX_GRAPH]; int main(int argc, char *argv[]) { int i; for(i = 0 ; i < MAX_QUEUE ; ++i) visited[i] = 0; GRAPH G; Create(&G); /* BFS(&G,0);*/ DFS(&G,0); return 0; } void BFS(GRAPH *G,int k) { int queue[MAX_QUEUE]; /* 队列 */ int front = -1,rear = -1,amount = 0; int visited[MAX_GRAPH]; /* 标记已经访问过的元素 */ int i,j; for(i = 0 ; i < MAX_GRAPH ; ++i) visited[i] = 0; printf("访问顶点%c\n",G->vex[k]); visited[k] = 1; rear = (rear + 1) % MAX_QUEUE; /* 入队操作 */ queue[rear] = k; front = rear; ++amount; while(amount > 0) { i = queue[front]; /* 出队操作 */ front = (front + 1) % MAX_QUEUE; --amount; for(j = 0 ; j < G->n ; ++j) { if(G->edge[i][j] != 0 && visited[j] == 0) { printf("访问顶点%c\n",G->vex[j]); visited[j] = 1; rear = (rear + 1) % MAX_QUEUE; /* 入队 */ queue[rear] = j; ++amount; } } } printf("遍历结束\n"); } void DFS(GRAPH *G,int k) { int j; printf("访问顶点:%c\n",G->vex[k]); visited[k] = 1; for(j = 0 ; j < G->n ; ++j) { if(G->edge[k][j] != 0 && visited[j] == 0) DFS(G,j); } } void Create(GRAPH *G) { printf("输入顶点数:\n"); scanf("%d",&G->n); printf("输入边数:\n"); scanf("%d",&G->e); getchar(); int i,j,k,w; printf("请输入端点(char型):\n"); for(i = 0 ; i < G->n ; ++i) /* 建立表头 */ scanf("%c",&G->vex[i]); for(i = 0 ; i < G->n ; ++i) /* 初始化邻接矩阵 */ for(j = 0 ; j < G->n ; ++j) G->edge[i][j] = 0; printf("请输入边:\n"); for(k = 0 ; k < G->e ; ++k) { scanf("%d%d%d",&i,&j,&w); /* 输入(vi,vj)上的权w */ G->edge[i][j] = w; G->edge[j][i] = w; } }
希望本文所述对大家的C++程序设计有所帮助。
上一篇: C++中的重载、覆盖、隐藏介绍
下一篇: VC++植物大战僵尸中文版修改器实现代码
相关文章
- vector是表示可以改变大小的数组的序列容器,本文主要介绍了C++STL标准库std::vector的使用详解,文中通过示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2022-03-06
- 这篇文章主要介绍了matplotlib绘制正余弦曲线图的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-22
- 这篇文章主要介绍了C++中取余运算的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-23
- 这篇文章主要介绍了matplotlib bar()实现百分比堆积柱状图,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-24
- 这篇文章主要介绍了C++ string常用截取字符串方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本文通过例子,讲述了C++调用C#的DLL程序的方法,作出了以下总结,下面就让我们一起来学习吧。...2020-06-25
- 本篇文章主要介绍了C++中四种加密算法之AES源代码,小编觉得挺不错的,现在分享给大家,也给大家做个参考。...2020-04-25
- 这篇文章主要介绍了解决echarts 一条柱状图显示两个值,类似进度条的问题,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-07-20
- 整数拆分,指把一个整数分解成若干个整数的和。本文重点给大家介绍C++ 整数拆分方法详解,非常不错,感兴趣的朋友一起学习吧...2020-04-25
- 这篇文章主要介绍了R语言基本画图函数与多图多线的用法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-05-06
- overlay就是在地图上以另外一种形式浮现在地图上,常见的地图覆盖物为这三种类型,如:popup 弹窗、label标注信息、text文本信息等,接下来跟随小编看下openlayers6之地图覆盖物overlay详解,一起看看吧...2021-09-15
- 本篇文章是对GDI+简单绘图的绘图知识进行了详细的分析介绍,需要的朋友参考下...2020-06-25
- 采用CSS覆盖的方法就可以了,但是官方是不允许这么做的...2013-10-13
- 下面小编就为大家带来一篇js遍历json的key和value的实例。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2017-01-26
- 这篇文章主要介绍了C++中Sort函数详细解析,sort函数是algorithm库下的一个函数,sort函数是不稳定的,即大小相同的元素在排序后相对顺序可能发生改变...2022-08-18
JavaScript中的数组遍历forEach()与map()方法以及兼容写法介绍
下面小编就为大家带来一篇JavaScript中的数组遍历forEach()与map()方法以及兼容写法介绍。小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2016-05-20详解pandas.DataFrame.plot() 画图函数
这篇文章主要介绍了详解pandas.DataFrame.plot()画图函数,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-06-15- 这篇文章主要介绍了vue+高德地图实现地图搜索及点击定位操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-09-09
- 这篇文章主要介绍了如何使用JavaScript实现“无缝滚动 自动播放”轮播图效果,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2020-08-20
- 这篇文章主要介绍了C++万能库头文件在vs中的安装步骤(图文),文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-23