ডirected Acyclic Graph (DAG) এর টপোলজিক্যাল সর্টিং হল একটি রৈখিক ক্রম যাতে প্রতিটি ডিরেক্টেড এজ uv-এর জন্য, ভের্টেক্স u ক্রমে v-এর আগে থাকে। যদি গ্রাফটি DAG না হয়, তবে গ্রাফের জন্য টপোলজিক্যাল সর্টিং সম্ভব নয়।
ফাংশন ও সিউডোকোড
শুরু ফাংশন topologicalSort(): ক) বর্তমান নোডকে ভিজিটেড হিসেবে চিহ্নিত করুন। খ) এই ভের্টেক্সের সাথে সংযুক্ত সব ভের্টেক্সের জন্য পুনরাবৃত্তি করুন। গ) বর্তমান ভের্টেক্সকে স্টকে পুশ করুন যা ফলাফল সংরক্ষণ করে। শেষ শুরু ফাংশন topoSort() যা রিকার্সিভ topologicalSort() ফাংশন ব্যবহার করে: ক) ভিজিট না করা সব ভের্টেক্স চিহ্নিত করুন। খ) topologicalSort() ফাংশনটি কল করুন। গ) বিষয়বস্তু প্রিন্ট করুন। শেষ
উদাহরণ
#include<iostream> #include <list> #include <stack> using namespace std; class G { int n; list<int> *adj; //ফাংশনগুলোর ঘোষণা void topologicalSort(int v, bool visited[], stack<int> &Stack); public: G(int n); //কনস্ট্রাক্টর void addEd(int v, int w); void topoSort(); }; G::G(int n) { this->n = n; adj = new list<int> [n]; } void G::addEd(int v, int w) // গ্রাফে এজ যোগ করুন। { adj[v].push_back(w); //w'কে v-এর লিস্টে যোগ করুন } void G::topologicalSort(int v, bool visited[], stack<int> &Stack) { visited[v] = true; //বর্তমান নোডকে ভিজিটেড হিসেবে চিহ্নিত করুন list<int>::iterator i; //এই ভের্টেক্সের সাথে সংযুক্ত সব ভের্টেক্সের জন্য পুনরাবৃত্তি করুন। for (i = adj[v].begin(); i != adj[v].end(); ++i) if (!visited[*i]) topologicalSort(*i, visited, Stack); Stack.push(v); } void G::topoSort() { stack<int> Stack; bool *visited = new bool[n]; //ভিজিট না করা সব ভের্টেক্স চিহ্নিত করুন। for (int i = 0; i < n; i++) visited[i] = false; for (int i = 0; i < n; i++) if (visited[i] == false) //topologicalSort() ফাংশনটি কল করুন। topologicalSort(i, visited, Stack); while (Stack.empty() == false) { cout << Stack.top() << " "; //এলিমেন্ট প্রিন্ট করুন Stack.pop(); } } int main() { G g(6); g.addEd(4, 2); g.addEd(5, 1); g.addEd(4, 0); g.addEd(3, 1); g.addEd(1, 3); g.addEd(3, 2); cout << " Topological Sort of the given graph \n"; g.topoSort(); return 0; }
আউটপুট
দেওয়া গ্রাফের টপোলজিক্যাল সর্ট 5 4 1 3 2 0
