编写算法输出图的连通分量的个数,并给出每个连通分量的遍历序列。
时间: 2023-06-22 12:37:58 浏览: 174
下面是输出图的连通分量的个数,并给出每个连通分量的遍历序列的算法:
1. 定义一个列表 visited 用于记录节点是否被遍历过,初始化为 False。
2. 定义一个函数 dfs(node) 用于深度优先遍历连通分量,具体实现如下:
- 将当前节点标记为已遍历(visited[node] = True);
- 遍历当前节点的所有邻居节点,若邻居节点未被遍历过,则递归调用 dfs(neighbour);
- 将当前节点加入遍历序列(traversal_order.append(node))。
3. 遍历图中所有节点,若节点未被遍历过,则调用 dfs(node);
4. 输出连通分量的个数,即遍历过程中调用 dfs 函数的次数;
5. 对于每个连通分量,输出其遍历序列 traversal_order。
下面是 Python 代码实现:
```python
def dfs(node):
visited[node] = True
for neighbour in graph[node]:
if not visited[neighbour]:
dfs(neighbour)
traversal_order.append(node)
# 例子中的图,用邻接表表示
graph = {
0: [1, 2],
1: [0, 2],
2: [0, 1, 3],
3: [2, 4],
4: [3]
}
# 初始化 visited 列表
visited = [False] * len(graph)
# 遍历序列列表
traversal_order = []
# 遍历图中所有节点
for node in graph:
if not visited[node]:
dfs(node)
# 输出连通分量的个数
print("连通分量的个数:", len(traversal_order))
# 输出每个连通分量的遍历序列
start = 0
for i in range(len(traversal_order)-1, -1, -1):
if visited[traversal_order[i]]:
print("连通分量", start+1, "的遍历序列:", end="")
while visited[traversal_order[i]]:
print(traversal_order[i], end=" ")
visited[traversal_order[i]] = False
i -= 1
print()
start += 1
```
输出结果为:
```
连通分量的个数: 2
连通分量 1 的遍历序列:0 1 2
连通分量 2 的遍历序列:3 4
```
阅读全文