ในกราฟอะไซคลิกโดยตรง เราสามารถจัดเรียงจุดยอดในลำดับเชิงเส้นโดยใช้การเรียงลำดับทอพอโลยี
การเรียงลำดับทอพอโลยีใช้ได้กับกราฟอะไซคลิกโดยตรงเท่านั้น ใน Directed Acyclic Graph (DAG) มีการจัดเรียงทอพอโลยีได้มากกว่าหนึ่งประเภท
ในโปรแกรม C++ ต่อไปนี้ เราจะทำการเรียงลำดับทอพอโลยีเพื่อตรวจสอบการมีอยู่ของวงจรในกราฟ
อัลกอริทึม
สำหรับฟังก์ชัน Topo_Sort
Begin Define function Topo_Sort() Declare x to the integer datatype, vstd[] of the Boolean array and Stack as a stack. Pass them as parameter. Initialize vstd[x] = true to mark the current node as vstd. Declare an iterator i. for (i = a[x].begin(); i != a[x].end(); ++i) if (!vstd[*i]) then Call Topo_Sort(*i, vstd, Stack) function. Call push() function to insert values into stack. End.
ตัวอย่าง
#include<iostream> #include <list> #include <stack> using namespace std; class grph { // Class to represent a graph int ver; list<int> *a; // Pointer to an array containing adjacency listsList void Topo_Sort(int x, bool vstd[], stack<int> &Stack); // A function used by TopologicalSort public: grph(int ver); // Constructor of grpf void Insert_Edge(int x, int y); // to insert an edge to graph void Topol_Sort(); // prints a Topological Sort of the complete graph }; grph::grph(int ver) { this->ver = ver; a = new list<int>[ver]; } void grph::Insert_Edge(int x, int y) { a[x].push_back(y); // Add y to x’s list. } // A recursive function used by Topol_Sort void grph::Topo_Sort(int x, bool vstd[], stack<int> &Stack) { vstd[x] = true; // Mark the current node as vstd. list<int>::iterator i; for (i = a[x].begin(); i != a[x].end(); ++i) if (!vstd[*i]) Topo_Sort(*i, vstd, Stack); // Push current vertex to stack which stores result Stack.push(x); } void grph::Topol_Sort() { stack<int> Stack; // Mark all the vertices as not vstd bool *vstd = new bool[ver]; for (int i = 0; i < ver; i++) vstd[i] = false; for (int i = 0; i < ver; i++) if (vstd[i] == false) Topo_Sort(i, vstd, Stack); while (Stack.empty() == false) { cout << Stack.top() << " "; Stack.pop(); } } int main() { grph g(6); // Create a graph given in the above diagram g.Insert_Edge(5, 2); g.Insert_Edge(5, 0); g.Insert_Edge(4, 0); g.Insert_Edge(4, 1); g.Insert_Edge(2, 3); g.Insert_Edge(3, 1); cout << "Topological Sort of the graph is: \n"; g.Topol_Sort(); return 0; }
ผลลัพธ์
Topological Sort of the graph is: 5 4 2 3 1 0