ग्राफ में ब्रिज

एक अनडायरेक्टेड ग्राफ में एक एज को ब्रिज कहा जाता है, यदि और केवल यदि इसे हटाने से ग्राफ डिस्कनेक्ट हो जाता है, या ग्राफ के अलग-अलग घटक बन जाते हैं।

व्यावहारिक दृष्टिकोण में, यदि एक नेटवर्क में कुछ ब्रिज मौजूद हैं, जब ब्रिज का कनेक्शन टूट जाता है, तो यह पूरे नेटवर्क को तोड़ सकता है।

इनपुट और आउटपुट

इनपुट: ग्राफ का एडजेसेंसी मैट्रिक्स। 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 आउटपुट: दिए गए ग्राफ में ब्रिज: 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 #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 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

आउटपुट
Bridges in given graph: Bridge 3--4 Bridge 0--3