如何使用邻接矩阵实现图的存储?并给出使用邻接矩阵存储的图的深度优先遍历算法实现。
时间: 2024-06-05 15:04:05 浏览: 17
邻接矩阵是一种常见的图的存储结构,它可以用二维数组表示图中各个节点之间的关系,其中数组中的每一个元素代表一个节点之间的连通情况。具体来说,如果节点i和节点j之间有边相连,则邻接矩阵中的第i行第j列为1;如果没有相连,则为0。
使用邻接矩阵实现图的深度优先遍历算法,可以按照以下步骤进行:
1. 定义一个栈,并将遍历的起始节点入栈。
2. 将栈顶节点出栈,并将其标记为已访问。
3. 遍历该节点的所有邻居节点,如果某个邻居节点没有被访问过,则将其入栈。
4. 重复执行步骤2和3,直到栈为空。
以下是使用邻接矩阵存储的图的深度优先遍历算法的实现:
```
#include <iostream>
#include <stack>
using namespace std;
const int MAXN = 100;
int G[MAXN][MAXN]; // 邻接矩阵存储图
bool visited[MAXN]; // 标记节点是否已访问
int n; // 节点数
void dfs(int start) {
stack<int> s;
s.push(start);
visited[start] = true;
cout << start << " ";
while (!s.empty()) {
int cur = s.top();
s.pop();
for (int i = 0; i < n; i++) {
if (G[cur][i] && !visited[i]) {
s.push(i);
visited[i] = true;
cout << i << " ";
}
}
}
}
int main() {
cin >> n;
// 初始化邻接矩阵
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
G[i][j] = 0;
}
}
// 读入图
int u, v;
while (cin >> u >> v) {
G[u][v] = 1;
G[v][u] = 1;
}
// 深度优先遍历
dfs(0);
return 0;
}
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![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)