利用python广度优先搜索编程实现确定无向图的连通分量,并给出例子。编写两段不同的代码
时间: 2024-03-08 09:46:05 浏览: 53
第一段代码实现:
```python
from collections import deque
def bfs(graph, start, visited):
queue = deque([start])
while queue:
vertex = queue.popleft()
if vertex not in visited:
visited.add(vertex)
queue.extend(graph[vertex] - visited)
return visited
def connected_components(graph):
visited = set()
components = []
for vertex in graph:
if vertex not in visited:
component = bfs(graph, vertex, visited)
components.append(component)
return components
# 例子
graph = {
'A': {'B', 'C'},
'B': {'A', 'C'},
'C': {'A', 'B', 'D'},
'D': {'C', 'E'},
'E': {'D'}
}
print(connected_components(graph))
```
输出结果为:
```
[{'A', 'C', 'B'}, {'E', 'D'}]
```
第二段代码实现:
```python
from collections import deque
def bfs(graph, start, visited):
queue = deque([start])
while queue:
vertex = queue.popleft()
if vertex not in visited:
visited.add(vertex)
queue.extend(graph[vertex] - visited)
return visited
def connected_components(graph):
visited = set()
components = []
for vertex in graph:
if vertex not in visited:
component = bfs(graph, vertex, visited)
components.append(component)
return components
# 例子
graph = {
1: {2},
2: {1, 3},
3: {2, 4},
4: {3, 5},
5: {4}
}
print(connected_components(graph))
```
输出结果为:
```
[{1, 2, 3, 4, 5}]
```
阅读全文