拓撲排序 — Kahn's BFS 與 DFS 雙解法完整教學 | 資料結構與演算法

interface TopologicalResult {
  order: number[];
  hasCycle: boolean;
}

function kahnTopologicalSort(n: number, edges: [number, number][]): TopologicalResult {
  // 建立鄰接表與入度陣列
  const graph: number[][] = Array.from({ length: n }, () => []);
  const inDegree = new Array(n).fill(0);

  for (const [u, v] of edges) {
    graph[u].push(v);
    inDegree[v]++;
  }

  // 將所有入度為 0 的節點加入 Queue
  const queue: number[] = [];
  for (let i = 0; i < n; i++) {
    if (inDegree[i] === 0) queue.push(i);
  }

  const order: number[] = [];

  while (queue.length > 0) {
    const u = queue.shift()!;
    order.push(u);

    for (const v of graph[u]) {
      inDegree[v]--;
      if (inDegree[v] === 0) queue.push(v);
    }
  }

  // 若結果長度 < n，代表有環存在
  return {
    order,
    hasCycle: order.length < n,
  };
}

// 使用範例
const result = kahnTopologicalSort(6, [[0,2],[0,3],[1,3],[1,4],[2,5],[3,5],[4,5]]);
console.log(result.order);    // 輸出：[0, 1, 2, 3, 4, 5]
console.log(result.hasCycle); // 輸出：false

interface LayeredResult {
  layers: number[][];
  hasCycle: boolean;
}

function kahnWithLayers(n: number, edges: [number, number][]): LayeredResult {
  const graph: number[][] = Array.from({ length: n }, () => []);
  const inDegree = new Array(n).fill(0);

  for (const [u, v] of edges) {
    graph[u].push(v);
    inDegree[v]++;
  }

  // 初始層：所有入度為 0 的節點
  let currentLayer: number[] = [];
  for (let i = 0; i < n; i++) {
    if (inDegree[i] === 0) currentLayer.push(i);
  }

  const layers: number[][] = [];
  let processed = 0;

  while (currentLayer.length > 0) {
    layers.push([...currentLayer]);
    processed += currentLayer.length;
    const nextLayer: number[] = [];

    for (const u of currentLayer) {
      for (const v of graph[u]) {
        inDegree[v]--;
        if (inDegree[v] === 0) nextLayer.push(v);
      }
    }
    currentLayer = nextLayer;
  }

  return {
    layers,
    hasCycle: processed < n,
  };
}

// 使用範例
const { layers } = kahnWithLayers(6, [[0,2],[0,3],[1,3],[1,4],[2,5],[3,5],[4,5]]);
// layers[0] = [0, 1]  → 第一學期可修
// layers[1] = [2, 3, 4]  → 第二學期可修
// layers[2] = [5]  → 第三學期可修
// 最少需要 3 個學期（layers.length）

function dfsTopologicalSort(n: number, edges: [number, number][]): TopologicalResult {
  const graph: number[][] = Array.from({ length: n }, () => []);
  for (const [u, v] of edges) graph[u].push(v);

  // 三色標記：0=未訪問, 1=訪問中（在當前 DFS 路徑上）, 2=已完成
  const state = new Array(n).fill(0);
  const stack: number[] = [];
  let hasCycle = false;

  function dfs(u: number): void {
    if (hasCycle) return;
    state[u] = 1; // 標記為「訪問中」

    for (const v of graph[u]) {
      if (state[v] === 1) {
        // 遇到「訪問中」的節點 → Back Edge → 有環！
        hasCycle = true;
        return;
      }
      if (state[v] === 0) {
        dfs(v);
      }
    }

    state[u] = 2; // 後序：標記為「已完成」，推入 Stack
    stack.push(u);
  }

  for (let i = 0; i < n; i++) {
    if (state[i] === 0) dfs(i);
  }

  return {
    order: hasCycle ? [] : stack.reverse(),
    hasCycle,
  };
}

class CourseScheduler {
  private n: number;
  private prerequisites: [number, number][];

  constructor(numCourses: number, prerequisites: [number, number][]) {
    this.n = numCourses;
    this.prerequisites = prerequisites;
  }

  // 是否可完成所有課程（環偵測）
  canFinish(): boolean {
    const { hasCycle } = kahnTopologicalSort(this.n, this.prerequisites);
    return !hasCycle;
  }

  // 回傳一個合法的修課順序
  findOrder(): number[] {
    const { order, hasCycle } = kahnTopologicalSort(this.n, this.prerequisites);
    return hasCycle ? [] : order;
  }

  // 回傳每個學期可以修的課（最少學期數）
  findParallelSchedule(): number[][] {
    const { layers, hasCycle } = kahnWithLayers(this.n, this.prerequisites);
    return hasCycle ? [] : layers;
  }
}

// 使用範例
const scheduler = new CourseScheduler(4, [[1,0],[2,0],[3,1],[3,2]]);
console.log(scheduler.canFinish());         // 輸出：true
console.log(scheduler.findOrder());          // 輸出：[0, 1, 2, 3]（其中一種合法順序）
console.log(scheduler.findParallelSchedule()); // 輸出：[[0], [1, 2], [3]]

#include <vector>
#include <queue>
using namespace std;

struct TopologicalResult {
    vector<int> order;
    bool hasCycle;
};

TopologicalResult kahnTopologicalSort(int n, vector<pair<int,int>>& edges) {
    vector<vector<int>> graph(n);
    vector<int> inDegree(n, 0);

    for (auto [u, v] : edges) {
        graph[u].push_back(v);
        inDegree[v]++;
    }

    queue<int> q;
    for (int i = 0; i < n; i++)
        if (inDegree[i] == 0) q.push(i);

    vector<int> order;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);
        for (int v : graph[u]) {
            if (--inDegree[v] == 0) q.push(v);
        }
    }

    return { order, (int)order.size() < n };
}

#include <vector>
#include <stack>
using namespace std;

class TopoSortDFS {
    int n;
    vector<vector<int>>& graph;
    vector<int> state; // 0=未訪 1=訪問中 2=完成
    stack<int> stk;
    bool hasCycle = false;

    void dfs(int u) {
        if (hasCycle) return;
        state[u] = 1;
        for (int v : graph[u]) {
            if (state[v] == 1) { hasCycle = true; return; }
            if (state[v] == 0) dfs(v);
        }
        state[u] = 2;
        stk.push(u);
    }

public:
    TopoSortDFS(int n, vector<vector<int>>& g) : n(n), graph(g), state(n, 0) {}

    vector<int> sort() {
        for (int i = 0; i < n; i++)
            if (state[i] == 0) dfs(i);

        if (hasCycle) return {};
        vector<int> result;
        while (!stk.empty()) { result.push_back(stk.top()); stk.pop(); }
        return result; // 已是正確拓撲順序（Stack 反轉）
    }
};

#include <vector>
#include <queue>
using namespace std;

// 回傳每層可並行執行的節點，若有環則回傳空
vector<vector<int>> kahnLayers(int n, vector<pair<int,int>>& edges) {
    vector<vector<int>> graph(n);
    vector<int> inDegree(n, 0);

    for (auto [u, v] : edges) {
        graph[u].push_back(v);
        inDegree[v]++;
    }

    vector<vector<int>> layers;
    vector<int> current;
    for (int i = 0; i < n; i++)
        if (inDegree[i] == 0) current.push_back(i);

    int processed = 0;
    while (!current.empty()) {
        layers.push_back(current);
        processed += (int)current.size();
        vector<int> next;
        for (int u : current)
            for (int v : graph[u])
                if (--inDegree[v] == 0) next.push_back(v);
        current = next;
    }

    return processed == n ? layers : vector<vector<int>>{};
}

// 用排序陣列模擬 Min-Heap（面試可接受）
function lexSmallestTopoSort(n: number, edges: [number, number][]): number[] {
  const graph: number[][] = Array.from({ length: n }, () => []);
  const inDegree = new Array(n).fill(0);

  for (const [u, v] of edges) {
    graph[u].push(v);
    inDegree[v]++;
  }

  // 初始化：保持升序排列以模擬 Min-Heap
  const minHeap: number[] = [];
  for (let i = 0; i < n; i++) if (inDegree[i] === 0) minHeap.push(i);
  minHeap.sort((a, b) => a - b);

  const result: number[] = [];
  while (minHeap.length > 0) {
    const u = minHeap.shift()!; // 取出最小值
    result.push(u);
    for (const v of graph[u]) {
      if (--inDegree[v] === 0) {
        // 二分搜尋找插入位置，維持有序
        let lo = 0, hi = minHeap.length;
        while (lo < hi) {
          const mid = (lo + hi) >> 1;
          if (minHeap[mid] < v) lo = mid + 1;
          else hi = mid;
        }
        minHeap.splice(lo, 0, v);
      }
    }
  }

  return result.length === n ? result : []; // 空陣列代表有環
}

// 在 DAG 上求最長路徑（可代表最多串連任務數）
function longestPathInDAG(n: number, edges: [number, number][]): number {
  const graph: number[][] = Array.from({ length: n }, () => []);
  const inDegree = new Array(n).fill(0);

  for (const [u, v] of edges) {
    graph[u].push(v);
    inDegree[v]++;
  }

  // Step 1：Kahn's Algorithm 得到拓撲順序
  const queue: number[] = [];
  for (let i = 0; i < n; i++) if (inDegree[i] === 0) queue.push(i);

  // dp[i] = 以節點 i 為終點的最長路徑長度
  const dp = new Array(n).fill(1);

  while (queue.length > 0) {
    const u = queue.shift()!;
    for (const v of graph[u]) {
      // Step 2：按拓撲順序做 DP 轉移
      dp[v] = Math.max(dp[v], dp[u] + 1);
      if (--inDegree[v] === 0) queue.push(v);
    }
  }

  return Math.max(...dp);
}

// 使用範例
console.log(longestPathInDAG(6, [[0,2],[0,3],[1,3],[1,4],[2,5],[3,5],[4,5]]));
// 輸出：4（最長路徑：0→2→5 或 1→3→5 等）

// 給定 numCourses 門課與 prerequisites 陣列
// prerequisites[i] = [a, b] 表示修 a 之前必須先修 b（邊：b → a）
// 判斷能否完成所有課程
function canFinish(numCourses: number, prerequisites: number[][]): boolean {
  const graph: number[][] = Array.from({ length: numCourses }, () => []);
  const inDegree = new Array(numCourses).fill(0);

  for (const [course, pre] of prerequisites) {
    graph[pre].push(course); // 邊：pre → course
    inDegree[course]++;
  }

  const queue: number[] = [];
  for (let i = 0; i < numCourses; i++) {
    if (inDegree[i] === 0) queue.push(i);
  }

  let completed = 0;
  while (queue.length > 0) {
    const course = queue.shift()!;
    completed++;
    for (const next of graph[course]) {
      inDegree[next]--;
      if (inDegree[next] === 0) queue.push(next);
    }
  }

  return completed === numCourses; // 全部處理完 → 無環
}
// 時間：O(V+E)，空間：O(V+E)

// 在 207 基礎上，回傳一個合法修課順序；若有環則回傳空陣列
function findOrder(numCourses: number, prerequisites: number[][]): number[] {
  const graph: number[][] = Array.from({ length: numCourses }, () => []);
  const inDegree = new Array(numCourses).fill(0);

  for (const [course, pre] of prerequisites) {
    graph[pre].push(course);
    inDegree[course]++;
  }

  const queue: number[] = [];
  for (let i = 0; i < numCourses; i++) {
    if (inDegree[i] === 0) queue.push(i);
  }

  const order: number[] = [];
  while (queue.length > 0) {
    const course = queue.shift()!;
    order.push(course);
    for (const next of graph[course]) {
      inDegree[next]--;
      if (inDegree[next] === 0) queue.push(next);
    }
  }

  return order.length === numCourses ? order : [];
}
// 時間：O(V+E)，空間：O(V+E)

// 給定排好序的單字列表，推導出字母之間的相對大小順序
function alienOrder(words: string[]): string {
  // 收集所有出現過的字母
  const chars = new Set(words.join(''));
  const n = chars.size;
  const charIndex = new Map<string, number>();
  let idx = 0;
  for (const c of chars) charIndex.set(c, idx++);

  const graph: number[][] = Array.from({ length: n }, () => []);
  const inDegree = new Array(n).fill(0);

  // 相鄰單字兩兩比較，找出字母順序關係
  for (let i = 0; i < words.length - 1; i++) {
    const w1 = words[i], w2 = words[i + 1];
    const len = Math.min(w1.length, w2.length);
    let found = false;
    for (let j = 0; j < len; j++) {
      if (w1[j] !== w2[j]) {
        // w1[j] 排在 w2[j] 之前（邊：w1[j] → w2[j]）
        const u = charIndex.get(w1[j])!;
        const v = charIndex.get(w2[j])!;
        graph[u].push(v);
        inDegree[v]++;
        found = true;
        break;
      }
    }
    // 若 w1 是 w2 的前綴且 w1 更長，則字典序無效（如 ["abc", "ab"]）
    if (!found && w1.length > w2.length) return '';
  }

  // Kahn's Algorithm
  const queue: number[] = [];
  for (let i = 0; i < n; i++) if (inDegree[i] === 0) queue.push(i);

  const indexChar = new Map<number, string>();
  for (const [c, i] of charIndex) indexChar.set(i, c);

  let result = '';
  while (queue.length > 0) {
    const u = queue.shift()!;
    result += indexChar.get(u);
    for (const v of graph[u]) {
      inDegree[v]--;
      if (inDegree[v] === 0) queue.push(v);
    }
  }

  return result.length === n ? result : ''; // 有環則字典序矛盾
}
// 時間：O(C)，C 為所有單字的字母總數；空間：O(1)（最多 26 個字母）

// 安全節點：從該節點出發的所有路徑，最終都終止於終端節點（無出邊）
// 等同於：不在任何環上，且不指向環中節點的節點
//
// 關鍵洞見：在反向圖中，終端節點（原圖出度=0）的入度=0
// 對反向圖做拓撲排序，能被排入的節點即為安全節點
function eventualSafeNodes(graph: number[][]): number[] {
  const n = graph.length;
  const reverseGraph: number[][] = Array.from({ length: n }, () => []);
  const outDegree = new Array(n).fill(0); // 原圖出度 = 反向圖「入度」

  for (let u = 0; u < n; u++) {
    for (const v of graph[u]) {
      reverseGraph[v].push(u); // 反向邊 v → u
      outDegree[u]++;
    }
  }

  // 原圖終端節點（出度=0）在反向圖中入度=0，最先處理
  const queue: number[] = [];
  for (let i = 0; i < n; i++) {
    if (outDegree[i] === 0) queue.push(i);
  }

  const safe = new Array(n).fill(false);
  while (queue.length > 0) {
    const u = queue.shift()!;
    safe[u] = true;
    for (const prev of reverseGraph[u]) {
      outDegree[prev]--;
      if (outDegree[prev] === 0) queue.push(prev);
    }
  }

  const result: number[] = [];
  for (let i = 0; i < n; i++) {
    if (safe[i]) result.push(i); // 結果自然按升序排列
  }
  return result;
}
// 時間：O(V+E)，空間：O(V+E)

// 每個學期只能修入度為 0 的課程，求修完所有課程的最少學期數
// 若有環（某些課程永遠無法修），回傳 -1
function minimumSemesters(n: number, relations: number[][]): number {
  const graph: number[][] = Array.from({ length: n + 1 }, () => []);
  const inDegree = new Array(n + 1).fill(0);

  for (const [prev, next] of relations) {
    graph[prev].push(next);
    inDegree[next]++;
  }

  // 初始層：所有入度為 0 的課程（課程編號從 1 開始）
  let currentLayer: number[] = [];
  for (let i = 1; i <= n; i++) {
    if (inDegree[i] === 0) currentLayer.push(i);
  }

  let semesters = 0;
  let completed = 0;

  while (currentLayer.length > 0) {
    semesters++;
    completed += currentLayer.length;
    const nextLayer: number[] = [];

    for (const course of currentLayer) {
      for (const next of graph[course]) {
        inDegree[next]--;
        if (inDegree[next] === 0) nextLayer.push(next);
      }
    }
    currentLayer = nextLayer;
  }

  return completed === n ? semesters : -1; // 若有環，部分課程無法修完
}
// 時間：O(V+E)，空間：O(V+E)