建立一个有向图的邻接矩阵存储,然后在主函数中输出该二维矩阵(注意输出格式要为一个矩阵),以检验存储的正确性;再从0号顶点出发对该图进行深度优先搜索,按顺序输出所访问的顶点。
时间: 2024-01-21 22:16:37 浏览: 47
好的,以下是一个简单的实现:
```c++
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 100;
vector<int> G[MAXN]; // 存储图的邻接表
int n; // 顶点数
void dfs(int u, vector<bool>& visited) {
visited[u] = true;
cout << u << " ";
for (int v : G[u]) {
if (!visited[v]) {
dfs(v, visited);
}
}
}
int main() {
cin >> n;
vector<vector<int>> adj_mat(n, vector<int>(n)); // 邻接矩阵
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> adj_mat[i][j];
if (adj_mat[i][j]) {
G[i].push_back(j); // 构建邻接表
}
}
}
// 输出邻接矩阵
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << adj_mat[i][j] << " ";
}
cout << endl;
}
// 深度优先搜索
vector<bool> visited(n, false);
dfs(0, visited);
return 0;
}
```
输入格式为:
```
6
0 1 1 0 0 0
1 0 0 1 0 0
1 0 0 1 1 0
0 1 1 0 1 1
0 0 1 1 0 1
0 0 0 1 1 0
```
其中第一行是顶点数,接下来的 $n$ 行是邻接矩阵。输出格式中,先输出邻接矩阵,再输出深度优先搜索的结果。
阅读全文