দৃঢ়ভাবে সংযুক্ত গ্রাফ

একটি নির্দেশিত গ্রাফে শক্তিশালীভাবে সংযুক্ত বলা হয়, যখন একটি উপাদানের প্রতিটি জোড়া শীর্ষবিন্দুর মধ্যে একটি পথ থাকে৷

এই অ্যালগরিদমটি সমাধান করার জন্য, প্রথমত, প্রতিটি শীর্ষবিন্দুর সমাপ্তির সময় পেতে DFS অ্যালগরিদম ব্যবহার করা হয়, এখন স্থানান্তরিত গ্রাফের সমাপ্তির সময় বের করুন, তারপর শীর্ষবিন্দুগুলিকে টপোলজিকাল সাজানোর দ্বারা অবতরণ ক্রমে সাজানো হয়।

ইনপুট এবং আউটপুট

Input:
Adjacency matrix of the graph.
0 0 1 1 0
1 0 0 0 0
0 1 0 0 0
0 0 0 0 1
0 0 0 0 0

Output:
Following are strongly connected components in given graph:
0 1 2
3
4

অ্যালগরিদম

ট্র্যাভার্স (গ্রাফ, শুরু, পরিদর্শন করা)

ইনপুট: গ্রাফ যা অতিক্রম করা হবে, প্রারম্ভিক শীর্ষবিন্দু এবং পরিদর্শন করা নোডগুলির পতাকা৷

আউটপুট: DFS কৌশলে প্রতিটি নোডের মধ্য দিয়ে যান এবং নোড প্রদর্শন করুন।

Begin
   mark start as visited
   for all vertices v connected with start, do
      if v is not visited, then
         traverse(graph, v, visited)
   done
End

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

ইনপুট - স্টার্ট নোড, পরিদর্শন করা শীর্ষবিন্দুর জন্য পতাকা, স্ট্যাক।

আউটপুট - গ্রাফ সাজানোর সময় স্ট্যাক পূরণ করুন।

Begin
   mark u as visited
   for all node v, connected with u, do
      if v is not visited, then
         topoSort(v, visited, stack)
   done
   push u into the stack
End

getStrongConComponents(গ্রাফ)

ইনপুট: প্রদত্ত গ্রাফ।

আউটপুট - সমস্ত দৃঢ়ভাবে সংযুক্ত উপাদান।

Begin
   initially all nodes are unvisited
   for all vertex i in the graph, do
      if i is not visited, then
         topoSort(i, vis, stack)
   done

   make all nodes unvisited again
   transGraph := transpose of given graph

   while stack is not empty, do
      pop node from stack and take into v
      if v is not visited, then
         traverse(transGraph, v, visited)
   done
End

উদাহরণ

#include <iostream>
#include <stack>
#define NODE 5
using namespace std;

int graph[NODE][NODE] = {
   {0, 0, 1, 1, 0},
   {1, 0, 0, 0, 0},
   {0, 1, 0, 0, 0},
   {0, 0, 0, 0, 1},
   {0, 0, 0, 0, 0}
};
                               
int transGraph[NODE][NODE];

void transpose() {    //transpose the graph and store to transGraph
   for(int i = 0; i<NODE; i++)
      for(int j = 0; j<NODE; j++)
         transGraph[i][j] = graph[j][i];
}    
         
void traverse(int g[NODE][NODE], int u, bool visited[]) {
   visited[u] = true;    //mark v as visited
   cout << u << " ";

   for(int v = 0; v<NODE; v++) {
      if(g[u][v]) {
         if(!visited[v])
            traverse(g, v, visited);
      }
   }
}  
                                               
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 getStrongConComponents() {
   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);
   
   for(int i = 0; i<NODE; i++)
      vis[i] = false;    //make all nodes are unvisited for traversal  
   transpose();    //make reversed graph
   
   while(!stk.empty()) {    //when stack contains element, process in topological order
      int v = stk.top(); stk.pop();
      if(!vis[v]) {
         traverse(transGraph, v, vis);
         cout << endl;
      }
   }
}

int main() {
   cout << "Following are strongly connected components in given graph: "<<endl;
   getStrongConComponents();
}

আউটপুট

Following are strongly connected components in given graph:
0 1 2
3
4