একটি নির্দেশিত অ্যাসাইক্লিক গ্রাফে, আমরা টপোলজিকাল সাজানোর ব্যবহার করে শীর্ষবিন্দুগুলিকে রৈখিক ক্রমে সাজাতে পারি।
টপোলজিক্যাল সর্ট শুধুমাত্র নির্দেশিত অ্যাসাইক্লিক গ্রাফে কাজ করে। একটি ডাইরেক্টেড অ্যাসাইক্লিক গ্রাফে (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
