โปรแกรม C++ เพื่อสร้างส่วนขยายเชิงเส้นแบบสุ่มสำหรับ DAG

เราจะมาดูวิธีการสร้าง Random Linear Extension ของ Directed Acyclic Graph (DAG) ส่วนขยายเชิงเส้นนั้นโดยทั่วไปแล้วเป็นการเรียงลำดับทอพอโลยีของ DAG ให้เราพิจารณาว่ากราฟเป็นดังนี้ -

การเรียงลำดับทอพอโลยีสำหรับกราฟอะไซคลิกโดยตรงคือการเรียงลำดับเชิงเส้นของจุดยอด สำหรับทุกขอบ u-v ของกราฟกำกับ จุดยอด u จะอยู่ก่อนจุดยอด v ในลำดับ

ดังที่เราทราบดีว่าจุดยอดต้นทางจะมาหลังจุดยอดปลายทาง เราจึงจำเป็นต้องใช้สแต็กเพื่อเก็บองค์ประกอบก่อนหน้า หลังจากเสร็จสิ้นโหนดทั้งหมด เราก็สามารถแสดงโหนดจากสแต็กได้

อินพุต

ผลลัพธ์

โหนดหลังการเรียงลำดับทอพอโลยี − 5 4 2 3 1 0

อัลกอริทึม

topoSort(u, เยี่ยมชม, stack)

ป้อนข้อมูล − จุดยอดเริ่มต้น u อาร์เรย์เพื่อติดตามว่าโหนดใดถูกเยี่ยมชมหรือไม่ สแต็คสำหรับเก็บโหนด

ผลผลิต − การจัดเรียงจุดยอดในลำดับทอพอโลยีในสแต็ก

Begin
   mark u as visited
   for all vertices v which is adjacent with u, do
      if v is not visited, then
         topoSort(c, visited, stack)
      done
      push u into stack
End

performTopologicalSorting(กราฟ)

ป้อนข้อมูล − กราฟวงกลมกำกับที่กำหนด

ผลผลิต − ลำดับของโหนด

Begin
   initially mark all nodes as unvisited
   for all nodes v of the graph, do
      if v is not visited, then
         topoSort(i, visited, stack)
      done
      pop and print all elements from the stack
End

ตัวอย่าง

#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; //set as the node v is visited
   for(int v = 0; v<NODE; v++) {
      if(graph[u][v]){ //for allvertices v adjacent to u
         if(!visited[v])
            topoSort(v, visited, stk);
      }
   }
   stk.push(u); //push starting vertex into the stack
}
void performTopologicalSort() {
   stack<int> stk;
   bool vis[NODE];
   for(int i = 0; i<NODE; i++)
      vis[i] = false; //initially all nodes are unvisited
   for(int i = 0; i<NODE; i++)
      if(!vis[i]) //when node is not visited
         topoSort(i, vis, stk);
   while(!stk.empty()) {
      cout << stk.top() << " ";
      stk.pop();
   }
}
main() {
   cout << "Nodes after topological sorted order: ";
   performTopologicalSort();
}

ผลลัพธ์

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