একটি গ্রাফে সেতু

একটি অনির্দেশিত গ্রাফের একটি প্রান্তকে একটি সেতু বলা হয়, যদি এবং শুধুমাত্র যদি এটি অপসারণ করে, গ্রাফটি সংযোগ বিচ্ছিন্ন করে বা গ্রাফের বিভিন্ন উপাদান তৈরি করে৷

একটি ব্যবহারিক পদ্ধতিতে, ব্রিজগুলির সংযোগ বিচ্ছিন্ন হওয়ার সময় যদি কিছু ব্রিজ একটি নেটওয়ার্কে উপস্থিত থাকে, তাহলে এটি পুরো নেটওয়ার্ককে ভেঙে দিতে পারে৷

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

Input:
The adjacency matrix of the graph.

0 1 1 1 0
1 0 1 0 0
1 1 0 0 0
1 0 0 0 1
0 0 0 1 0

Output:
Bridges in given graph:
Bridge 3--4
Bridge 0--3

অ্যালগরিদম

bridgeFind(start, visited, disc, low, parent)

ইনপুট - প্রারম্ভিক শীর্ষবিন্দু, একটি নোড পরিদর্শন করা হলে চিহ্নিত করার জন্য পরিদর্শন করা অ্যারে, ডিস্কটি শীর্ষবিন্দুর আবিষ্কারের সময় ধরে রাখবে এবং নিম্নে সাবট্রি সম্পর্কে তথ্য থাকবে। অভিভাবক বর্তমান শীর্ষবিন্দুর অভিভাবককে ধরে রাখবে৷

আউটপুট - কোনো সেতু পাওয়া গেলে প্রিন্ট করুন।

Begin
   time := 0       //the value of time will not be initialized for next function calls
   mark start as visited
   set disc[start] := time+1 and low[start] := time + 1
   time := time + 1

   for all vertex v in the graph G, do
      if there is an edge between (start, v), then
         if v is visited, then
            parent[v] := start
            bridgeFind(v, visited, disc, low, parent)
            low[start] := minimum of low[start] and low[v]

            if low[v] > disc[start], then
               display bridges from start to v
         else if v is not the parent of start, then
            low[start] := minimum of low[start] and disc[v]
   done
End

উদাহরণ

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

int graph[NODE][NODE] = {
   {0, 1, 1, 1, 0},
   {1, 0, 1, 0, 0},
   {1, 1, 0, 0, 0},
   {1, 0, 0, 0, 1},
   {0, 0, 0, 1, 0}
};
                               
int min(int a, int b) {
   return (a<b)?a:b;
}
                               
void bridgeFind(int start, bool visited[], int disc[], int low[], int parent[]) {
   static int time = 0;
   visited[start] = true;               //make the first vertex is visited
   disc[start] = low[start] = ++time;  //initialize discovery time and the low time

   for(int v = 0; v<NODE; v++) {
      if(graph[start][v]) {   //for all vertex v, which is connected with start
         if(!visited[v]) {
            parent[v] = start;    //make start node as parent
            bridgeFind(v, visited, disc, low, parent);
                   
            low[start] = min(low[start], low[v]);    //when subtree from v is connected to one of parent of start node
            if(low[v] > disc[start])
               cout << "Bridge " << start << "--"<<v<<endl;
         } else if(v != parent[start])    //update low of start for previous call
            low[start] = min(low[start], disc[v]);
      }
   }
}

bool bridges() {
   bool *vis = new bool[NODE];
   int *disc = new int[NODE];
   int *low = new int[NODE];
   int *parent = new int[NODE];
   
   for(int i = 0; i<NODE; i++) {
      vis[i] = false;    //no node is visited
      parent[i] = -1;    //initially there is no parent for any node
   }
   
   for(int i = 0; i<NODE; i++)
      if(!vis[i])    //if any node is unvisited, the graph is not connected
         bridgeFind(i, vis, disc, low, parent);
}

int main() {
   cout << "Bridges in given graph:"<<endl;
   bridges();
}

আউটপুট

Bridges in given graph:
Bridge 3--4
Bridge 0--3