采用邻接表存储结构,编写一个求无向图的连通分量个数的算法
时间: 2023-04-16 10:02:05 浏览: 144
使用邻接表存储无向图,可以通过深度优先搜索(DFS)或广度优先搜索(BFS)来求连通分量的个数。以下是一个基于深度优先搜索的算法:
1. 初始化一个visited数组,用来记录每个顶点是否已经被访问过。将所有元素初始化为false。
2. 遍历所有顶点,对于每个未被访问的顶点v,进行DFS操作。
3. 在DFS操作中,将当前顶点v标记为已访问,然后遍历v的邻居节点w。如果w未被访问,就对w进行DFS操作。
4. 当DFS操作完成后,当前连通分量中的所有顶点都已被访问,将该连通分量计数器加1。
5. 重复2-4步,直到所有顶点都被访问过。最终计数器的值即为图的连通分量个数。
下面是一个伪代码实现:
```
function countConnectedComponents(graph):
visited = [false] * graph.numVertices
numComponents = 0
for v in range(graph.numVertices):
if not visited[v]:
dfs(graph, visited, v)
numComponents += 1
return numComponents
function dfs(graph, visited, v):
visited[v] = true
for w in graph.adjacencyList[v]:
if not visited[w]:
dfs(graph, visited, w)
```
其中,graph.adjacencyList[v]表示顶点v的邻接表,即与v相邻的所有顶点。