โปรแกรม C++ สร้าง Random Linear Extension สำหรับ DAG

ที่นี่เราจะสร้าง Random Linear Extension ของ Directed Acyclic Graph (DAG) Linear extension คือ topological sorting ของ DAG พิจารณากราฟดังรูป

Topological sorting สำหรับ DAG คือการเรียงลำดับโหนดแบบเส้นตรง สำหรับทุกขอบ u-v ของกราฟมีทิศทาง โหนด u จะมาก่อนโหนด v ในลำดับ

เนื่องจากโหนดต้นทาง (source) จะมาหลังโหนดปลายทาง (destination) เราต้องใช้ stack เก็บสมาชิกก่อนหน้า หลังจบทุกโหนด แค่ pop จาก stack มาแสดง

Input

Output

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

อัลกอริทึม

topoSort(u, visited, stack)

Input - Start vertex u, array visited, stack

Output - เรียงโหนดแบบ topological ใน stack

เริ่มต้น
  ทำเครื่องหมาย u ว่า visited
  สำหรับทุกโหนด v ที่ติดกับ u ทำ
    ถ้า v ยังไม่ visited
      topoSort(v, visited, stack)
    จบถ้า
  จบลูป
  push u เข้า stack
สิ้นสุด

performTopologicalSorting(Graph)

Input - Directed acyclic graph

Output - Sequence of nodes

เริ่มต้น
  ทำเครื่องหมายทุกโหนดว่า unvisited
  สำหรับทุกโหนด v ของกราฟ ทำ
    ถ้า v ไม่ visited
      topoSort(v, visited, stack)
    จบถ้า
  จบลูป
  pop และพิมพ์ทุกสมาชิกจาก stack
สิ้นสุด

ตัวอย่างโค้ด

#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]) {
            if (!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();
    return 0;
}

ผลลัพธ์

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