无向图采用领接表作为存储结构,设计一个算法,求解该图的连通分量个数并输出各连通分量的顶点集
时间: 2023-06-20 20:04:06 浏览: 114
可以使用深度优先搜索(DFS)算法来求解无向图的连通分量。具体步骤如下:
1. 初始化一个空的集合connected_components来存储连通分量的顶点集。
2. 对于图中的每个顶点v,如果它还没有被访问过,就从v开始进行DFS遍历,并将遍历到的所有顶点添加到一个新的集合component中。
3. 将component添加到connected_components中。
4. 重复步骤2和3,直到所有的顶点都被访问过。
5. 输出connected_components中的每个集合,它们分别对应图的不同连通分量的顶点集。
下面是使用Python语言实现该算法的代码:
```python
from collections import defaultdict
def dfs(vertex, visited, graph, component):
visited[vertex] = True
component.append(vertex)
for neighbor in graph[vertex]:
if not visited[neighbor]:
dfs(neighbor, visited, graph, component)
def find_connected_components(graph):
visited = defaultdict(bool)
connected_components = []
for vertex in graph.keys():
if not visited[vertex]:
component = []
dfs(vertex, visited, graph, component)
connected_components.append(component)
return connected_components
# 示例
graph = {1: [2, 3],
2: [1, 3],
3: [1, 2],
4: [5],
5: [4]}
connected_components = find_connected_components(graph)
print(connected_components)
```
输出结果为:
```
[[1, 2, 3], [4, 5]]
```
其中,[1, 2, 3]和[4, 5]分别表示两个连通分量的顶点集。
阅读全文