编程利用广度优先搜索算法确定无向图的连通分量。
时间: 2023-06-14 07:04:28 浏览: 125
下面是使用广度优先搜索算法确定无向图连通分量的 Python 代码示例:
```python
from collections import deque
# 无向图的邻接表表示
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
# 广度优先搜索函数
def bfs(start, visited):
queue = deque([start])
visited.add(start) # 标记起点已访问
component = []
while queue:
node = queue.popleft()
component.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return component
# 获取无向图的连通分量
def connected_components():
visited = set() # 已访问的节点集合
components = []
for node in graph:
if node not in visited:
component = bfs(node, visited)
components.append(component)
return components
# 测试代码
components = connected_components()
print(components) # [['A', 'C', 'B', 'E', 'D', 'F']]
```
在上面的代码中,我们首先定义了一个无向图的邻接表表示。然后,我们定义了一个广度优先搜索函数 `bfs`,该函数从指定的起点开始遍历图,并返回与起点连通的所有节点。在搜索过程中,我们使用一个队列来存储待访问的节点,并使用一个集合来记录已经访问过的节点,以避免重复访问。
最后,我们定义了一个 `connected_components` 函数,该函数遍历整个无向图,并返回其中所有的连通分量。该函数首先创建一个空的已访问节点集合,然后从图中的每个未访问节点开始遍历,并将遍历得到的连通节点集合添加到 `components` 列表中。最终,`connected_components` 函数返回 `components` 列表,其中每个元素都是一个连通分量。在本例中,由于无向图是连通的,因此 `connected_components` 函数返回一个包含所有节点的列表。
阅读全文