একটি ডায়রেক্টেড্যাসাইক্লিক গ্রাফ (Directed Acyclic Graph - DAG) এর ভার্টেক্সগুলো টপোলজিক্যাল সোর্ট (Topological Sort) ব্যবহার করে লিনিয়ার অর্ডারে সর্ট করা যায়।
টপোলজিক্যাল সোর্ট শুধু DAG-এ কাজ করে। একটি DAG-এ একাধিক টপোলজিক্যাল সোর্ট থাকতে পারে।
নিচের C++ প্রোগ্রামে আমরা টপোলজিক্যাল সোর্ট করব এবং গ্রাফে সাইকেল (cycle) আছে কিনা তা চেক করব।
এলগরিদম
Topo_Sort ফাংশনের জন্য
Begin
Function Topo_Sort() ডিফাইন
x ইন্টিজার, vstd[] বুলিয়ান অ্যারে এবং Stack স্ট্যাক ডিক্লেয়ার করে প্যারামিটার হিসেবে পাস করুন।
vstd[x] = true সেট করে করেন্ট নোড ভিজিটেড (visited) মার্ক করুন।
ইটারেটর i ডিক্লেয়ার করুন।
for (i = a[x].begin(); i != a[x].end(); ++i)
if (!vstd[*i]) Topo_Sort(*i, vstd, Stack) কল করুন।
push() কল করে স্টকে ভ্যালু ইনসার্ট করুন।
End.
উদাহরণ
#include <iostream>
#include <list>
#include <stack>
using namespace std;
class grph { // গ্রাফ রিপ্রেজেন্ট করার ক্লাস
int ver;
list *a; // অ্যাডজেসেন্সি লিস্ট ধারণ করার অ্যারে পয়েন্টার
void Topo_Sort(int x, bool vstd[], stack &Stack); // Topol_Sort দ্বারা ব্যবহৃত হেল্পার ফাংশন
public:
grph(int ver); // কনস্ট্রাক্টর
void Insert_Edge(int x, int y); // গ্রাফে এজ ইনসার্ট
void Topol_Sort(); // পুরো গ্রাফের টপোলজিক্যাল সোর্ট প্রিন্ট
};
grph::grph(int ver) {
this->ver = ver;
a = new list[ver];
}
void grph::Insert_Edge(int x, int y) {
a[x].push_back(y); // x-এর লিস্টে y যোগ
}
// Topol_Sort দ্বারা ব্যবহৃত রিকারসিভ ফাংশন
void grph::Topo_Sort(int x, bool vstd[], stack &Stack) {
vstd[x] = true; // করেন্ট নোড ভিজিটেড মার্ক
list::iterator i;
for (i = a[x].begin(); i != a[x].end(); ++i)
if (!vstd[*i])
Topo_Sort(*i, vstd, Stack);
// রেজাল্ট স্টোর করার স্টকে করেন্ট ভার্টেক্স পুশ
Stack.push(x);
}
void grph::Topol_Sort() {
stack Stack;
// সব ভার্টেক্স আনভিজিটেড হিসেবে মার্ক
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); // উপরের ডায়াগ্রাম অনুযায়ী গ্রাফ তৈরি
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
