如何判断有向图是否有环?并给出拓扑排序。

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()  // 逆后序 = 拓扑序
}

同分类其他题目