图的广度遍历-邻接表实现
时间: 2023-11-27 15:06:21 浏览: 71
图的广度遍历可以使用队列来实现。下面是邻接表实现图的广度遍历的步骤:
1. 创建一个队列,将起始顶点入队。
2. 创建一个 visited 数组,用来记录每个顶点是否被访问过,并将起始顶点标记为已访问。
3. 当队列不为空时,进行以下操作:
a. 从队列中取出一个顶点,输出该顶点。
b. 遍历该顶点的所有邻接点,如果邻接点未被访问过,将其标记为已访问并入队。
4. 重复步骤 3,直到队列为空。
下面是邻接表实现图的广度遍历的 C++ 代码:
```c++
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int MAXN = 100; // 最大顶点数
vector<int> G[MAXN]; // 邻接表
bool visited[MAXN]; // 标记数组
void bfs(int s) {
queue<int> q;
q.push(s);
visited[s] = true;
while (!q.empty()) {
int u = q.front();
cout << u << " ";
q.pop();
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i];
if (!visited[v]) {
visited[v] = true;
q.push(v);
}
}
}
}
int main() {
int n, m;
cin >> n >> m; // 输入顶点数和边数
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v; // 输入一条边的两个端点
G[u].push_back(v); // 存储邻接关系,注意是无向图
G[v].push_back(u);
}
bfs(1); // 从顶点 1 开始遍历
return 0;
}
```
其中,输入格式为:
```
n m // 顶点数、边数
u1 v1
u2 v2
...
um vm // m 条边的两个端点
```
例如,下面是一个无向图的邻接表和其广度遍历的示例:
```
6 7
1 2
1 3
2 4
2 5
3 5
4 6
5 6
```
邻接表:
```
G[1]: 2 3
G[2]: 1 4 5
G[3]: 1 5
G[4]: 2 6
G[5]: 2 3 6
G[6]: 4 5
```
广度遍历结果:
```
1 2 3 4 5 6
```
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.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)