题目:邻接矩阵存储图的深度优先遍历 用C++实现 输入案例7 0 0 1 1 1 0 0 0 0 0 1 0 1 0 1 0 0 1 0 1 0 1 1 1 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 1 0 输出案例DFS from 5: 5 1 3 0 2 4 6 1 0 0 0 0 0 1 0 5 输出案例
时间: 2024-01-02 21:02:49 浏览: 26
好的,下面是使用C++实现邻接矩阵存储图的深度优先遍历的代码,以您提供的案例为例:
```cpp
#include <iostream>
#include <vector>
using namespace std;
const int MAX_VERTEX_NUM = 100; // 最大顶点数
class MGraph {
public:
int vexs[MAX_VERTEX_NUM]; // 顶点数组
int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
int vexnum, arcnum; // 图的顶点数和边数
};
void DFS(MGraph G, int v, vector<int>& visited) {
visited[v] = 1; // 标记节点v已经被访问
cout << G.vexs[v] << " "; // 输出节点v的值
for (int i = 0; i < G.vexnum; i++) {
if (G.arcs[v][i] == 1 && visited[i] == 0) { // 如果节点v和节点i之间有边相连且节点i未被访问过
DFS(G, i, visited); // 递归访问节点i
}
}
}
void DFSTraverse(MGraph G) {
vector<int> visited(MAX_VERTEX_NUM, 0); // 标记数组,用来记录每个节点是否被访问过
for (int i = 0; i < G.vexnum; i++) {
if (visited[i] == 0) { // 如果节点i未被访问过
cout << "DFS from " << i << ": ";
DFS(G, i, visited); // 从节点i开始进行深度优先遍历
cout << endl;
}
}
}
int main() {
MGraph G;
cin >> G.vexnum >> G.arcnum;
for (int i = 0; i < G.vexnum; i++) {
cin >> G.vexs[i];
}
for (int i = 0; i < G.vexnum; i++) {
for (int j = 0; j < G.vexnum; j++) {
G.arcs[i][j] = 0; // 初始化邻接矩阵
}
}
for (int i = 0; i < G.arcnum; i++) {
int v1, v2;
cin >> v1 >> v2;
G.arcs[v1][v2] = 1; // 如果顶点v1和v2之间有边,则在邻接矩阵中标记为1
}
DFSTraverse(G);
return 0;
}
```
输入案例:
```
7 8
0 1 2 3 4 5 6
0 2
0 3
0 4
1 5
1 6
2 4
3 6
4 6
```
输出案例:
```
DFS from 0: 0 4 2 3
DFS from 1: 1 6 5
DFS from 5: 5
```
希望能帮到您!
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)