একটি DAG-এর জন্য র‍্যান্ডম লিনিয়ার এক্সটেনশন তৈরি করতে C++ প্রোগ্রাম

এখানে আমরা দেখব কিভাবে ডাইরেক্টেড অ্যাসাইক্লিক গ্রাফ (DAG) এর র্যান্ডম লিনিয়ার এক্সটেনশন তৈরি করা যায়। লিনিয়ার এক্সটেনশনটি মূলত DAG-এর টপোলজিকাল বাছাই। গ্রাফটি নিচের মত বিবেচনা করা যাক −

নির্দেশিত অ্যাসাইক্লিক গ্রাফের টপোলজিকাল বাছাই হল শীর্ষবিন্দুর রৈখিক ক্রম। নির্দেশিত গ্রাফের প্রতিটি প্রান্ত u-v-এর জন্য, ক্রমানুসারে শীর্ষবিন্দু v এর আগে শীর্ষবিন্দু u আসবে।

যেহেতু আমরা জানি যে উত্স শীর্ষবিন্দুটি গন্তব্য শীর্ষস্থানের পরে আসবে, তাই আমাদের পূর্ববর্তী উপাদানগুলি সংরক্ষণ করতে একটি স্ট্যাক ব্যবহার করতে হবে। সমস্ত নোড সম্পূর্ণ করার পরে, আমরা কেবল স্ট্যাক থেকে তাদের প্রদর্শন করতে পারি।

ইনপুট

আউটপুট

টপোলজিক্যাল সাজানো ক্রম − 5 4 2 3 1 0

অ্যালগরিদম

topoSort(u, পরিদর্শন করা, স্ট্যাক)

ইনপুট − শুরুর শীর্ষবিন্দু u, কোন নোডটি পরিদর্শন করা হয়েছে বা না তা ট্র্যাক করার জন্য একটি অ্যারে। নোড স্টোর করার জন্য একটি স্ট্যাক।

আউটপুট − স্ট্যাকের মধ্যে শীর্ষবিন্দুগুলিকে টপোলজিক্যাল সিকোয়েন্সে সাজানো।

Begin
   mark u as visited
   for all vertices v which is adjacent with u, do
      if v is not visited, then
         topoSort(c, visited, stack)
      done
      push u into stack
End

পারফর্ম টপোলজিক্যাল সর্টিং(গ্রাফ)

ইনপুট - প্রদত্ত নির্দেশিত অ্যাসাইক্লিক গ্রাফ।

আউটপুট − নোডের ক্রম।

Begin
   initially mark all nodes as unvisited
   for all nodes v of the graph, do
      if v is not visited, then
         topoSort(i, visited, stack)
      done
      pop and print all elements from the stack
End

উদাহরণ

#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; //set as the node v is visited
   for(int v = 0; v<NODE; v++) {
      if(graph[u][v]){ //for allvertices v adjacent to u
         if(!visited[v])
            topoSort(v, visited, stk);
      }
   }
   stk.push(u); //push starting vertex into the stack
}
void performTopologicalSort() {
   stack<int> stk;
   bool vis[NODE];
   for(int i = 0; i<NODE; i++)
      vis[i] = false; //initially all nodes are unvisited
   for(int i = 0; i<NODE; i++)
      if(!vis[i]) //when node is not visited
         topoSort(i, vis, stk);
   while(!stk.empty()) {
      cout << stk.top() << " ";
      stk.pop();
   }
}
main() {
   cout << "Nodes after topological sorted order: ";
   performTopologicalSort();
}

আউটপুট

Nodes after topological sorted order: 5 4 2 3 1 0