有向图环检测

图

说明

DFS 用三色状态区分未访问、搜索中、已完成；指向搜索中节点的边形成环。

分析

三色分别表示未访问、当前递归路径中和已经完成。遇到指向“路径中”节点的边，就是返回祖先的回边，说明有向环存在。

图解推演

沿 0→1→2 递归时，三点都在当前路径中。2→0 指向灰色祖先，闭合成环；若某邻点早已完成并标黑，说明它不在当前递归链上，不能据此报环。每个递归调用退出时必须标黑，否则后续合法汇合边会被误判。

查看图表代码

适用前提与边界

指向已经完成的节点并不构成当前路径上的环，这正是普通 visited 标记不够用的原因。

示例输入与调用

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

运行输出

true

完整 Go 示例

package main

import "fmt"

func HasCycle(g [][]int) bool {
	color := make([]int, len(g))
	var visit func(int) bool
	visit = func(v int) bool {
		color[v] = 1
		for _, w := range g[v] {
			if color[w] == 1 || color[w] == 0 && visit(w) {
				return true
			}
		}
		color[v] = 2
		return false
	}
	for v := range g {
		if color[v] == 0 && visit(v) {
			return true
		}
	}
	return false
}

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