帮我写一段关于邻接矩阵存储图的深度优先遍历的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 1 0 0 0 0 0 1 0 5 输出样例:DFS from 5: 5 1 3 0 2 4 6
时间: 2024-01-01 18:06:34 浏览: 87
好的,以下是实现邻接矩阵存储图的深度优先遍历的C++代码:
```c++
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 100;
vector<int> adj[MAXN]; // 邻接表
int G[MAXN][MAXN]; // 邻接矩阵
bool visited[MAXN]; // 记录每个节点是否被访问过
// 深度优先遍历
void dfs(int u) {
visited[u] = true;
cout << u << " ";
for (int v = 0; v < adj[u].size(); v++) {
if (!visited[adj[u][v]]) {
dfs(adj[u][v]);
}
}
}
int main() {
int n, start;
cin >> n >> start;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> G[i][j];
if (G[i][j] == 1) {
adj[i].push_back(j);
}
}
}
cout << "DFS from " << start << ": ";
dfs(start);
cout << endl;
return 0;
}
```
其中,`adj`是邻接表,`G`是邻接矩阵,`visited`是记录每个节点是否被访问过的数组。首先输入图的节点数`n`和起点`start`,然后读入邻接矩阵并将其转换为邻接表。最后调用`dfs`函数进行深度优先遍历,并输出结果。
阅读全文