以邻接矩阵定义无向图,其中每个元素的数据类型为int。实现图的广度优先遍历,打印所有的节点
时间: 2024-04-30 09:19:53 浏览: 73
数据结构(visualc++)用邻接矩阵表示给定无向图并进行深度遍历借鉴.pdf
以下是基于邻接矩阵的无向图广度优先遍历的实现示例,其中每个节点用数字表示:
```c++
#include <iostream>
#include <queue>
using namespace std;
const int MAXN = 100;
int graph[MAXN][MAXN]; // 邻接矩阵存储图
bool visited[MAXN]; // 标记节点是否被访问过
void bfs(int start, int n) {
queue<int> q;
q.push(start);
visited[start] = true;
while (!q.empty()) {
int cur = q.front();
q.pop();
cout << cur << " ";
for (int i = 0; i < n; i++) {
if (graph[cur][i] && !visited[i]) { // 该节点与cur相邻且未被访问
visited[i] = true;
q.push(i);
}
}
}
}
int main() {
int n, m;
cin >> n >> m; // n为节点数,m为边数
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
graph[u][v] = graph[v][u] = 1; // 无向图,所以要将两个方向都设置为1
}
for (int i = 0; i < n; i++) {
if (!visited[i]) { // 如果该节点未被访问过,则从该节点开始进行BFS
bfs(i, n);
}
}
return 0;
}
```
这个程序的输入格式如下:
```
6 7
0 1
0 2
1 2
1 3
2 4
3 4
3 5
```
其中第一行的两个数字分别表示节点数和边数,接下来的m行表示边的情况。输出结果为:
```
0 1 2 3 4 5
```
表示广度优先遍历的结果。
阅读全文