采用邻接表存储结构,编写一个求无向图的连通分量个数的算法。
时间: 2023-06-05 19:47:47 浏览: 197
算法功能:采用邻接表存储结构建立无向图.pdf
邻接表是一种存储图的方式,可以表示图中的每个顶点以及每个顶点所连接的边。我们可以通过遍历图的所有顶点,并且在遍历时使用深度优先搜索(DFS)算法来计算无向图的连通分量个数。
具体算法步骤如下:
1. 遍历图的所有顶点,对于每个顶点,如果它没有被访问过,就以该顶点为起点进行深度优先搜索。
2. 在深度优先搜索中,对于每个未被访问过的相邻顶点,将其标记为已访问,并以该顶点为起点进行递归搜索。
3. 在搜索结束后,如果搜索到的所有顶点都已被标记为已访问,说明这些顶点构成一个连通分量,将其计数器加1。
4. 重复以上步骤,直到所有顶点都被访问过。
下面是一个具体的实现:
```python
def count_connected_components(graph):
visited = set() # 用一个集合记录已经访问过的顶点
count = 0 # 连通分量的个数
def dfs(v):
visited.add(v) # 标记顶点v为已访问
for neighbor in graph[v]:
if neighbor not in visited:
dfs(neighbor)
for v in graph:
if v not in visited:
dfs(v)
count += 1
return count
```
其中 `graph` 是以邻接表的形式存储的无向图,每个顶点以及与它相邻的顶点都被表示为一个列表。
该算法的时间复杂度为 $O(|V| + |E|)$,其中 $|V|$ 是顶点的个数,$|E|$ 是边的个数。
阅读全文