簡析圖論算法：拓撲排序

發佈於 — 12月 06, 2022
#算法 #圖論

簡單整理拓撲排序(Topological Sorting)及Java實現

拓撲排序(Topological Sorting)的任務是給有向無環圖(DAG, Directed Acyclic Graph)上的所有節點(vertex)排序，其要求是：

如果有從u到v的邊(edge)，或存在由u到v的路徑(path)，那麼u不能出現在v後

CSCI2110 中使用的算法是 Kahn’s Algorithm，基本思路爲維護一個入度(indegree)爲 0 的節點的隊列，然後依次“刪除”從入度爲 0 點出發的邊，基本思路如下：

  1. 首先計算 DAG 中所有點的入度，並將入度爲 0 的點放入一個隊列中
  2. 從隊列中取出(dequeue)一個點加入結果，依次刪除從該節點出發的邊
  3. 如果刪除後其後繼節點入度爲 0，將其入隊(enqueue)
  4. 重複 2~3 步直到隊列爲空

核心代碼：

TopologicalSort.java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

// Enqueue the vertices with a `0` indegree and mark them as visited
for (int i = 0; i < graph.getNumberOfVertex(); i++) {
  if (inDegree[i] == 0) {
    queue.add(i);
    isVisited[i] = true;
  }
}

while (!queue.isEmpty()) {
  int u = queue.poll();
  result.add(u + 1);

  // Enqueue the succeeding vertices and
  //   update the indegree of them
  for (int v : graph.getEdges().get(u)) {
    inDegree[v]--;
    if (inDegree[v] == 0 && !isVisited[v]) {
      queue.add(v);
      isVisited[v] = true;
    }
  }
}

演示:

graph

TopologicalSortDemo.java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

Graph graph = new Graph(7);

graph.addEdge(1, 3);
graph.addEdge(1, 4);
graph.addEdge(2, 4);
graph.addEdge(3, 5);
graph.addEdge(3, 6);
graph.addEdge(3, 7);
graph.addEdge(4, 6);
graph.addEdge(4, 7);

System.out.println(TopologicalSort.of(graph));

輸出：

1

[1, 2, 3, 4, 5, 6, 7]

一點需要解釋的實現細節：

  • 我使用鄰接表(Adjacency List) 存儲圖
  • 我使用了Static Factory來封裝類的實例化過程

具體實現見完整源代碼：Github Repo