การเรียงลำดับแบบโตโปโลจิคัล (Topological Sorting)

การเรียงลำดับแบบโตโปโลจิคัล (Topological Sorting) สำหรับกราฟมีทิศทางไม่มีวงจร (DAG) คือการเรียงลำดับโหนดแบบเส้นตรง โดยที่สำหรับเส้นเชื่อม U-V ทุกเส้น โหนด U จะอยู่ก่อนโหนด V ในลำดับ

เนื่องจากโหนดต้นทางจะอยู่หลังโหนดปลายทาง จึงใช้ Stack เก็บโหนดที่ผ่านมาแล้ว และนำมาแสดงผลจากบนลงล่างของ Stack

การรับค่าและแสดงผล

Input: เมทริกซ์ตyacency (6x6)
Output: Nodes after topological sorted order: 5 4 2 3 1 0

อัลกอริทึม

topoSort(u, visited, stack)

Begin
  ทำเครื่องหมาย u ว่าเยี่ยมชมแล้ว
  for ทุกโหนด v ที่ติดกับ u do
    if v ยังไม่ได้เยี่ยมชม then topoSort(v, visited, stack)
  done
  push u ลงใน stack
End

performTopologicalSorting(Graph)

Begin
  ทำเครื่องหมายทุกโหนดว่าไม่ได้เยี่ยมชม
  for ทุกโหนด v ในกราฟ do
    if v ไม่ได้เยี่ยมชม then topoSort(v, visited, stack)
  done
  
  pop และพิมพ์ทุกข้อมูลจาก stack
End

ตัวอย่างโค้ด (C++)

#include <iostream>
#include <stack>
#define NODE 6
using namespace std;

int graph[NODE][NODE] = {
  {0, 0, 0, 0, 0, 0},
  {0, 0, 0, 0, 0, 0},
  {0, 0, 0, 1, 0, 0},
  {0, 1, 0, 0, 0, 0},
  {1, 1, 0, 0, 0, 0},
  {1, 0, 1, 0, 0, 0}
};

void topoSort(int u, bool visited[], stack<int> &stk) {
  visited[u] = true;
  for(int v = 0; v < NODE; v++)
    if(graph[u][v] && !visited[v])
      topoSort(v, visited, stk);
  stk.push(u);
}

void performTopologicalSort() {
  stack<int> stk;
  bool vis[NODE];
  
  for(int i = 0; i < NODE; i++) vis[i] = false;
  for(int i = 0; i < NODE; i++)
    if(!vis[i]) topoSort(i, vis, stk);
  
  while(!stk.empty()) {
    cout << stk.top() << " ";
    stk.pop();
  }
}

int main() {
  cout << "Nodes after topological sorted order: ";
  performTopologicalSort();
}

ผลลัพธ์

Nodes after topological sorted order: 5 4 2 3 1 0