c++有向图邻接矩阵建立深度遍历
时间: 2023-08-29 09:12:56 浏览: 65
下面是C++语言实现邻接矩阵建立有向图并进行深度遍历的示例代码:
```cpp
#include<iostream>
#include<cstring>
using namespace std;
const int maxn = 100; //最大节点数
int G[maxn][maxn]; //邻接矩阵
bool vis[maxn]; //标记节点是否已被访问
int n, m; //节点数和边数
void DFS(int u) { //深度遍历
vis[u] = true; //标记节点已被访问
cout << u << " "; //输出节点编号
for (int v = 1; v <= n; v++) { //枚举所有节点
if (G[u][v] && !vis[v]) { //如果u和v之间有边,并且v未被访问过
DFS(v); //从v开始继续深度遍历
}
}
}
int main() {
cin >> n >> m; //读入节点数和边数
memset(G, 0, sizeof(G)); //初始化邻接矩阵
memset(vis, false, sizeof(vis)); //初始化节点访问标记
for (int i = 1; i <= m; i++) { //读入m条边
int u, v;
cin >> u >> v;
G[u][v] = 1; //建立有向边
}
for (int i = 1; i <= n; i++) { //枚举所有节点
if (!vis[i]) { //如果节点未被访问过
DFS(i); //从该节点开始深度遍历
}
}
return 0;
}
```
以上代码中,DFS函数表示深度遍历函数,vis数组用于标记节点是否已被访问,G数组表示邻接矩阵。输入节点数和边数后,读入每条边,并建立邻接矩阵。最后枚举所有节点,从未被访问过的节点开始深度遍历。
相关推荐
![](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)