利用广度优先搜索编程实现确定无向图的连通分量。
时间: 2023-09-02 14:14:58 浏览: 21
好的,以下是利用广度优先搜索实现确定无向图连通分量的 Python 代码:
```python
from collections import defaultdict
# 定义一个图类
class Graph:
def __init__(self):
self.graph = defaultdict(list)
# 添加节点
def add_edge(self, u, v):
self.graph[u].append(v)
self.graph[v].append(u)
# 广度优先搜索
def BFS(self, v, visited):
queue = []
queue.append(v)
visited[v] = True
while queue:
s = queue.pop(0)
print(s, end=" ")
for i in self.graph[s]:
if visited[i] == False:
queue.append(i)
visited[i] = True
# 确定连通分量
def connected_components(self):
visited = [False] * (max(self.graph) + 1)
for i in range(len(visited)):
if visited[i] == False:
self.BFS(i, visited)
print()
```
你可以通过以下方式测试代码:
```python
g = Graph()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(3, 4)
g.add_edge(4, 5)
g.add_edge(6, 6)
g.connected_components()
```
输出结果如下:
```
0 1 2
3 4 5
6
```
其中,输出的每一行代表一个连通分量。
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![md](https://img-home.csdnimg.cn/images/20210720083646.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)