深度优先搜索

图

说明

沿一条路径探索到底再回溯；时间 O(V+E)。

分析

从起点递归访问尚未见过的邻居，seen 防止在环中重复进入节点。它能用于可达性、连通分量和回溯搜索。

图解推演

正文链先访问 0，再递归 1，最后递归 2；到达无新邻居处依次返回。访问顺序依赖邻接表顺序，不是唯一排序。seen 要在展开邻居前置真，否则带环输入会无限递归；需要完整遍历非连通图时，还要在外层为未访问点重启搜索。

查看图表代码

适用前提与边界

每个顶点和边至多处理常数次；极深图可改用显式栈避免递归栈过深。

示例输入与调用

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

运行输出

[true true true]

完整 Go 示例

package main

import "fmt"

func DFS(g [][]int, start int) []bool {
	seen := make([]bool, len(g))
	var visit func(int)
	visit = func(v int) {
		seen[v] = true
		for _, w := range g[v] {
			if !seen[w] {
				visit(w)
			}
		}
	}
	visit(start)
	return seen
}

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