试设计一个算法Mark标记一个无向图G的各个连通分量,即第i个连通分量标记为i。
时间: 2024-05-11 14:17:40 浏览: 12
可以使用深度优先搜索(DFS)或广度优先搜索(BFS)遍历整个无向图,每次遍历到一个新的连通分量时将其标记为当前连通分量的数量加一。具体流程如下:
1. 新建一个数组component,用于存储每个节点所属的连通分量编号。
2. 初始化连通分量编号为0。
3. 从第一个节点开始进行DFS或BFS遍历,每次遍历到一个节点,如果它的连通分量未被标记,就将其标记为当前连通分量编号,并将其所有相邻的未被标记过的节点也标记成同一个连通分量编号。
4. 如果搜索完整个无向图后仍有节点未被标记,那么说明它们不与之前的连通分量相连,需要另外开辟一个新的连通分量编号,重复步骤3直到所有节点都被标记。
具体实现可参考以下Python代码:
```python
def mark_components(graph):
component = [0] * len(graph)
visited = [False] * len(graph)
count = 0
for i in range(len(graph)):
if not visited[i]:
count += 1
dfs(graph, i, visited, component, count)
return component
def dfs(graph, node, visited, component, count):
visited[node] = True
component[node] = count
for neighbor in graph[node]:
if not visited[neighbor]:
dfs(graph, neighbor, visited, component, count)
```
其中graph是存储无向图的邻接表,component是存储每个节点所属连通分量编号的数组。mark_components函数返回component数组,可以通过访问该数组获取每个节点所属的连通分量编号。