连通分量

图

说明

每次从未访问节点搜索一个完整分量；无向图时间 O(V+E)。

分析

在无向图里，从一个未访问节点出发能到达的所有节点构成一个连通分量。对每个剩余起点重复搜索即可得到完整划分。

图解推演

正文中 0 与 1 相连，而 2 是孤立点，因此共有两组。第一次搜索标记 0、1，外层扫描到 1 时跳过，到 2 时才开启第二次搜索。孤立点也计作一个分量；有向图的强连通分量不能直接用这个无向图方法替代。

查看图表代码

适用前提与边界

示例用栈迭代并在入栈时标记，避免同一节点被多次加入。

示例输入与调用

fmt.Println(Components([][]int{{1}, {0}, {}}))

运行输出

[[0 1] [2]]

完整 Go 示例

package main

import "fmt"

func Components(g [][]int) [][]int {
	seen := make([]bool, len(g))
	out := [][]int{}
	for start := range g {
		if seen[start] {
			continue
		}
		part := []int{}
		stack := []int{start}
		seen[start] = true
		for len(stack) > 0 {
			v := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			part = append(part, v)
			for _, w := range g[v] {
				if !seen[w] {
					seen[w] = true
					stack = append(stack, w)
				}
			}
		}
		out = append(out, part)
	}
	return out
}

func main() {
	fmt.Println(Components([][]int{{1}, {0}, {}}))
}