如何判断有向图是否有环?并给出拓扑排序。
DFS + 三色标记:白(未访问)/ 灰(递归中)/ 黑(已完成)。遇到灰节点即存在环。
function topoSort(n, edges) {
const adj = Array.from({ length: n }, () => [])
for (const [u, v] of edges) adj[u].push(v)
const color = new Array(n).fill(0) // 0白 1灰 2黑
const order = []
let hasCycle = false
function dfs(u) {
color[u] = 1
for (const v of adj[u]) {
if (color[v] === 1) { hasCycle = true; return }
if (color[v] === 0) dfs(v)
}
color[u] = 2
order.push(u) // 后序入栈
}
for (let i = 0; i < n; i++) if (color[i] === 0) dfs(i)
return hasCycle ? [] : order.reverse() // 逆后序 = 拓扑序
}- 时间
O(V + E) - 应用:课程表(207)、依赖构建顺序、任务调度
- Kahn 算法(入度+BFS)也能做,更适合「边处理」场景