利用广度优先搜索编程实现确定无向图的连通分量。
时间: 2023-09-02 15:14:58 浏览: 110
搜索算法_广度优先搜索算法判断图的连通性_matlab
5星 · 资源好评率100%
可以使用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()
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()
```
运行程序会输出无向图的连通分量。
阅读全文