根据输入的邻接矩阵判断此图的连通分量
时间: 2023-12-07 14:03:32 浏览: 125
可以使用深度优先搜索或广度优先搜索来判断一个图的连通分量。以下是使用深度优先搜索的算法步骤:
1. 从任意一个节点开始,标记为已访问过。
2. 对于该节点的每一个未访问过的邻居节点,递归执行步骤1和步骤2。
3. 所有与该起始节点直接或间接相连的节点都被标记为已访问过后,将起始节点所在的连通分量标记为已完成。
4. 从未被访问过的节点中选取一个作为新的起始节点,重复执行步骤1到步骤3,直到所有节点都被标记为已访问过。
下面是 Python 代码实现:
```
def dfs(adj_matrix):
n = len(adj_matrix)
visited = [False] * n
components = []
def dfs_helper(node, component):
visited[node] = True
component.append(node)
for neighbor in range(n):
if adj_matrix[node][neighbor] and not visited[neighbor]:
dfs_helper(neighbor, component)
for node in range(n):
if not visited[node]:
component = []
dfs_helper(node, component)
components.append(component)
return components
```
其中,`adj_matrix` 是输入的邻接矩阵,`n` 是节点个数,`visited` 数组记录每个节点是否已经访问过,`components` 则记录所有连通分量。`dfs_helper` 是递归函数,用于搜索与当前节点直接或间接相连的所有节点,并将它们添加到同一个连通分量中。最终,返回所有连通分量。
阅读全文