定义一有n个结点的的以邻接矩阵为存储方式的网(有向或无向均可),并对其进行如下操作: 1.深度优先遍历,并输出遍历序列; 2.广度优先遍历,并输出遍历序列; 3.求源点到图中每个点的最短路径,并输出; 4.输出图 C++代码怎么写?

时间: 2024-03-27 10:41:41 浏览: 18
好的,以下是实现以上操作的 C++ 代码: ```c++ #include <iostream> #include <queue> #include <stack> using namespace std; const int MAXN = 100; //最大结点数 int n; //结点数 int a[MAXN][MAXN]; //邻接矩阵 bool visited[MAXN]; //标记结点是否访问过 //深度优先遍历 void dfs(int u) { visited[u] = true; cout << u << " "; for (int v = 0; v < n; v++) { if (a[u][v] != 0 && !visited[v]) { dfs(v); } } } //广度优先遍历 void bfs(int s) { queue<int> q; q.push(s); visited[s] = true; while (!q.empty()) { int u = q.front(); q.pop(); cout << u << " "; for (int v = 0; v < n; v++) { if (a[u][v] != 0 && !visited[v]) { visited[v] = true; q.push(v); } } } } //求最短路径 void shortestPath(int s) { const int INF = 0x3f3f3f3f; //表示正无穷 int dist[MAXN]; //dist[i]表示源点s到结点i的最短距离 bool inQueue[MAXN]; //标记结点是否在队列中 queue<int> q; for (int i = 0; i < n; i++) { dist[i] = INF; inQueue[i] = false; } dist[s] = 0; inQueue[s] = true; q.push(s); while (!q.empty()) { int u = q.front(); q.pop(); inQueue[u] = false; for (int v = 0; v < n; v++) { if (a[u][v] != 0 && dist[v] > dist[u] + a[u][v]) { dist[v] = dist[u] + a[u][v]; if (!inQueue[v]) { q.push(v); inQueue[v] = true; } } } } //输出最短路径 cout << "源点到各点的最短路径如下:" << endl; for (int i = 0; i < n; i++) { if (dist[i] == INF) { cout << "源点" << s << "到结点" << i << "不存在路径" << endl; } else { cout << "源点" << s << "到结点" << i << "的最短路径长度为:" << dist[i] << endl; } } } int main() { //读入数据 cout << "请输入结点数n:"; cin >> n; cout << "请输入邻接矩阵a:" << endl; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> a[i][j]; } } //深度优先遍历 cout << "深度优先遍历序列为:"; for (int i = 0; i < n; i++) { visited[i] = false; } for (int i = 0; i < n; i++) { if (!visited[i]) { dfs(i); } } cout << endl; //广度优先遍历 cout << "广度优先遍历序列为:"; for (int i = 0; i < n; i++) { visited[i] = false; } for (int i = 0; i < n; i++) { if (!visited[i]) { bfs(i); } } cout << endl; //求最短路径 int s; cout << "请输入源点s:"; cin >> s; shortestPath(s); return 0; } ``` 注意:以上代码只是一种实现方式,实际上还有很多其他实现方式,比如使用邻接表存储图等。

相关推荐

最新推荐

recommend-type

邻接表或者邻接矩阵为存储结构实现连通无向图的深度优先和广度优先遍历

程序设计任务: 设计一个程序,实现以邻接表或者邻接矩阵为存储结构,实现连通无向图的深度优先和广度优先遍历。基本要求:以邻接表或者邻接矩阵为存储结构,实现连通无向图的深度优先和广度优先遍历。以用户指定的...
recommend-type

C语言实现图的邻接矩阵存储操作

主要为大家详细介绍了C语言实现图的邻接矩阵存储操作,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
recommend-type

Python根据已知邻接矩阵绘制无向图操作示例

主要介绍了Python根据已知邻接矩阵绘制无向图操作,涉及Python使用networkx、matplotlib进行数值运算与图形绘制相关操作技巧,需要的朋友可以参考下
recommend-type

STM32H562实现FreeRTOS内存管理【支持STM32H系列单片机】.zip

STM32H562 FreeRTOS驱动程序,支持STM32H系列单片机。 项目代码可直接运行~
recommend-type

恶魔轮盘.cpp

恶魔轮盘
recommend-type

zigbee-cluster-library-specification

最新的zigbee-cluster-library-specification说明文档。
recommend-type

管理建模和仿真的文件

管理Boualem Benatallah引用此版本:布阿利姆·贝纳塔拉。管理建模和仿真。约瑟夫-傅立叶大学-格勒诺布尔第一大学,1996年。法语。NNT:电话:00345357HAL ID:电话:00345357https://theses.hal.science/tel-003453572008年12月9日提交HAL是一个多学科的开放存取档案馆,用于存放和传播科学研究论文,无论它们是否被公开。论文可以来自法国或国外的教学和研究机构,也可以来自公共或私人研究中心。L’archive ouverte pluridisciplinaire
recommend-type

MATLAB柱状图在信号处理中的应用:可视化信号特征和频谱分析

![matlab画柱状图](https://img-blog.csdnimg.cn/3f32348f1c9c4481a6f5931993732f97.png) # 1. MATLAB柱状图概述** MATLAB柱状图是一种图形化工具,用于可视化数据中不同类别或组的分布情况。它通过绘制垂直条形来表示每个类别或组中的数据值。柱状图在信号处理中广泛用于可视化信号特征和进行频谱分析。 柱状图的优点在于其简单易懂,能够直观地展示数据分布。在信号处理中,柱状图可以帮助工程师识别信号中的模式、趋势和异常情况,从而为信号分析和处理提供有价值的见解。 # 2. 柱状图在信号处理中的应用 柱状图在信号处理
recommend-type

解释这行代码 c = ((double)rand() / RAND_MAX) * (a + b - fabs(a - b)) + fabs(a - b);

这行代码是用于生成 a 和 b 之间的随机数。首先,它使用 rand() 函数生成一个 [0,1) 之间的随机小数,然后将这个小数乘以 a、b 范围内的差值,再加上 a 和 b 中的较小值。这可以确保生成的随机数大于等于 a,小于等于 b,而且不会因为 a 和 b 之间的差距过大而导致难以生成足够多的随机数。最后,使用 fabs() 函数来确保计算结果是正数。
recommend-type

JSBSim Reference Manual

JSBSim参考手册,其中包含JSBSim简介,JSBSim配置文件xml的编写语法,编程手册以及一些应用实例等。其中有部分内容还没有写完,估计有生之年很难看到完整版了,但是内容还是很有参考价值的。