写一个邻接表的求图的连通分量的个数写一个邻接表的求图的连通分量的个数写一个邻接表的求图的连通分量的个数写一个邻接表的求图的连通分量的个数的算法
时间: 2024-09-18 15:05:49 浏览: 28
为了计算使用邻接表表示的无向图的连通分量个数,我们可以采用深度优先搜索(DFS)或者广度优先搜索(BFS)。这里我给出一个基于DFS的算法:
1. 创建一个空集合`components`,用于存储每个连通分量。
2. 遍历所有节点,对每个未访问过的节点u执行以下操作:
- 对于节点u,设置它的颜色为“已访问”(例如使用一个标记数组或哈希集)。
- 开始深度优先遍历:
- 递归访问u的所有未访问过的邻居v。
- 每次访问新节点,将其添加到当前的连通分量集合中。
3. 当遍历完所有的节点后,`components`中就会有每个连通分量的一个标识符。
以下是算法的伪代码:
```python
def count_connected_components(adj_list):
visited = [False] * len(adj_list) # 假设每个节点的初始状态为未访问
components_count = 0
def dfs(node):
nonlocal components_count
visited[node] = True
components_count += 1
for neighbor in adj_list[node]:
if not visited[neighbor]: # 如果邻居未访问过,则继续搜索
dfs(neighbor)
for node in range(len(adj_list)):
if not visited[node]:
dfs(node)
return components_count
# 示例:
adj_list = {0: [1, 2], 1: [0], 2: [0]}
print(count_connected_components(adj_list)) # 输出:3(因为有三个连通分量)
```
阅读全文