用C++表示以邻接矩阵作为存储方式,实现图的广度优先遍历和深度优先遍历
时间: 2023-07-24 21:04:27 浏览: 119
以邻接矩阵作为存储方式的图,可以用一个二维数组来表示。其中,数组的每个元素表示图中两个顶点的连通情况,如果它的值为1,则表示这两个顶点相邻;否则表示不相邻。
我们可以通过一个访问标记数组来记录图中每个顶点是否被访问过。在遍历过程中,对于每个未被访问的顶点,我们都要访问它,并将它的所有邻居顶点标记为已访问。广度优先遍历使用队列来实现,深度优先遍历使用递归或栈来实现。
下面是C++实现代码:
```cpp
#include<iostream>
#include<queue>
#include<stack>
using namespace std;
const int MAXN = 100; // 最大顶点数
int G[MAXN][MAXN]; // 邻接矩阵表示的图
bool visited[MAXN]; // 访问标记数组
// 广度优先遍历
void BFS(int s, int n) {
queue<int> Q;
visited[s] = true;
Q.push(s);
while (!Q.empty()) {
int u = Q.front();
cout << u << " ";
Q.pop();
for (int v = 0; v < n; ++v) {
if (G[u][v] && !visited[v]) {
visited[v] = true;
Q.push(v);
}
}
}
}
// 深度优先遍历
void DFS(int u, int n) {
visited[u] = true;
cout << u << " ";
for (int v = 0; v < n; ++v) {
if (G[u][v] && !visited[v]) {
DFS(v, n);
}
}
}
int main() {
int n, m; // n个顶点,m条边
cin >> n >> m;
// 初始化邻接矩阵和访问标记数组
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
G[i][j] = 0;
}
visited[i] = false;
}
// 读入边
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
G[u][v] = G[v][u] = 1;
}
// 从顶点0开始遍历
cout << "BFS: ";
BFS(0, n);
cout << endl;
// 重新初始化访问标记数组
for (int i = 0; i < n; ++i) {
visited[i] = false;
}
// 从顶点0开始遍历
cout << "DFS: ";
DFS(0, n);
cout << endl;
return 0;
}
```
注意,在实现中,我们假设图中顶点的编号从0开始,到n-1结束。同时,我们也假设输入的边是无向边,因此在邻接矩阵中,对于每条边(u, v),我们都将G[u][v]和G[v][u]设置为1。如果输入的边是有向边,则只需要将G[u][v]设置为1即可。
阅读全文