无向表采用邻接表储存结构,编写算法输出图中各联通分量的顶点序列
时间: 2024-02-22 18:56:30 浏览: 23
好的,以下是一个 Python 算法,用于输出无向图中各联通分量的顶点序列:
```python
# 无向图类
class UndirectedGraph:
def __init__(self):
self.adj_list = {}
# 添加边
def add_edge(self, u, v):
if u not in self.adj_list:
self.adj_list[u] = []
if v not in self.adj_list:
self.adj_list[v] = []
self.adj_list[u].append(v)
self.adj_list[v].append(u)
# 深度优先搜索
def dfs(self, v, visited, component):
visited[v] = True
component.append(v)
for neighbor in self.adj_list[v]:
if not visited[neighbor]:
self.dfs(neighbor, visited, component)
# 输出各联通分量的顶点序列
def print_connected_components(self):
visited = {v: False for v in self.adj_list}
components = []
for v in self.adj_list:
if not visited[v]:
component = []
self.dfs(v, visited, component)
components.append(component)
for i, component in enumerate(components):
print(f"Component {i+1}: {component}")
# 测试
g = UndirectedGraph()
g.add_edge(1, 2)
g.add_edge(2, 3)
g.add_edge(4, 5)
g.add_edge(5, 6)
g.add_edge(6, 4)
g.add_edge(7, 8)
g.print_connected_components()
```
这个算法首先定义了一个 `UndirectedGraph` 类,用于存储无向图的邻接表。然后,它通过 `add_edge` 方法添加边。接下来,它定义了一个 `dfs` 方法,用于深度优先搜索无向图,并将遍历到的顶点加入到指定的联通分量中。最后,它通过 `print_connected_components` 方法输出各联通分量的顶点序列。
在测试部分,我们创建了一个无向图,并通过 `print_connected_components` 方法输出了各联通分量的顶点序列。输出结果如下:
```
Component 1: [1, 2, 3]
Component 2: [4, 5, 6]
Component 3: [7, 8]
```
这表明该无向图包含三个联通分量,分别为 `{1, 2, 3}`、`{4, 5, 6}` 和 `{7, 8}`。