根据图的邻接矩阵确定图中连分量的个数并输出每个连通分量的顶点
时间: 2024-02-06 07:09:57 浏览: 24
可以使用深度优先搜索(DFS)来解决此问题。
具体步骤如下:
1. 初始化一个数组visited,表示每个顶点是否被访问过。初始时,所有顶点都未被访问,因此visited数组的所有元素均为false。
2. 从第一个顶点开始,依次对每个未被访问过的顶点进行DFS操作。在DFS操作中,先标记当前顶点为已访问(将visited数组对应位置的元素设为true),然后递归访问当前顶点的所有邻居顶点。
3. 在DFS操作中,对于已经访问过的顶点,不需要重复访问,因为它们已经被访问过,并且已经属于同一个连通分量。
4. 当DFS操作结束后,所有属于同一个连通分量的顶点都已经被访问过,并且visited数组对应位置的元素都为true。此时,我们就找到了一个连通分量。
5. 重复步骤2-4,直到所有顶点都被访问过。
6. 统计连通分量的个数,并输出每个连通分量的顶点。
下面是基于邻接矩阵的代码实现:
```python
def find_connected_components(adj_matrix):
num_nodes = len(adj_matrix)
visited = [False] * num_nodes
connected_components = []
def dfs(node, component):
visited[node] = True
component.append(node)
for neighbor in range(num_nodes):
if adj_matrix[node][neighbor] == 1 and not visited[neighbor]:
dfs(neighbor, component)
for node in range(num_nodes):
if not visited[node]:
component = []
dfs(node, component)
connected_components.append(component)
return connected_components
```
这个函数的输入是邻接矩阵,输出是一个列表,其中每个元素是一个连通分量的顶点列表。例如,如果图有两个连通分量,第一个连通分量包含节点0、1、2,第二个连通分量包含节点3、4,那么输出将是[[0, 1, 2], [3, 4]]。
你可以通过以下方式调用该函数:
```python
adj_matrix = [
[0, 1, 1, 0, 0],
[1, 0, 1, 0, 0],
[1, 1, 0, 0, 0],
[0, 0, 0, 0, 1],
[0, 0, 0, 1, 0]
]
connected_components = find_connected_components(adj_matrix)
print(connected_components)
```
输出结果为:
```
[[0, 1, 2], [3, 4]]
```