একটি ডায়রেক্টেড অসাইক্লিক গ্রাফ (DAG) এর জন্য টপোলজিক্যাল সোর্টিং হলো ভার্টেক্সের একটি লিনিয়ার অর্ডারিং। একটি ডায়রেক্টেড গ্রাফের প্রতিটি এজ U-V এর জন্য, ভার্টেক্স u, ভার্টেক্স v-র আগে অর্ডারিং-এ আসবে।
যেহেতু সোর্স ভার্টেক্স ডেস্টিনেশন ভার্টেক্সের পরে আসে, তাই আমাদের একটি স্ট্যাক ব্যবহার করতে হবে পূর্বের এলিমেন্টগুলো স্টোর করতে। সব নোড পুরা হলে, আমরা সিম্পলি স্ট্যাক থেকে সেগুলো প্রদর্শন করতে পারি।
ইনপুট এবং আউটপুট
ইনপুট: 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 আউটপুট: টপোলজিক্যালি সর্টেড অর্ডারে নোডগুলো: 5 4 2 3 1 0
এলগরিদম
topoSort(u, visited, stack)
ইনপুট: শুরুর ভার্টেক্স u, কোন নোড ভিজিটেড হয়েছে কিনা তা ট্র্যাক রাখতে একটি অ্যারে। নোড স্টোর করতে একটি স্ট্যাক।
আউটপুট: স্ট্যাকে টপোলজিক্যাল সিকোয়েন্সে ভার্টেক্স সর্ট করা।
শুরু
u কে ভিজিটেড চিহ্নিত করুন
u-র সাথে সন্নিহিত সব ভার্টেক্স v এর জন্য, করুন
যদি v ভিজিটেড না থাকে, তবে
topoSort(v, visited, stack)
শেষ লুপ
u কে একটি স্ট্যাকে পুশ করুন
শেষ
performTopologicalSorting(Graph)
ইনপুট: প্রদত্ত ডায়রেক্টেড অসাইক্লিক গ্রাফ।
আউটপুট: নোডের সিকোয়েন্স।
শুরু
প্রাথমিকভাবে সব নোডকে অনভিজিটেড চিহ্নিত করুন
গ্রাফের সব নোড v এর জন্য, করুন
যদি v ভিজিটেড না থাকে, তবে
topoSort(v, visited, stack)
শেষ লুপ
স্ট্যাক থেকে সব এলিমেন্ট পপ করুন এবং প্রিন্ট করুন
শেষ।
উদাহরণ (C++ কোড)
#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; // নোড v কে ভিজিটেড হিসেবে সেট করুন
for(int v = 0; v < NODE; v++) {
if(graph[u][v]) { // 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();
}
আউটপুট
Nodes after topological sorted order: 5 4 2 3 1 0
