एक ग्राफ में पुल

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

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

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

इनपुट:ग्राफ का आसन्न मैट्रिक्स।0 1 1 1 01 0 1 0 01 1 0 0 01 0 0 0 10 0 0 1 0आउटपुट:दिए गए ग्राफ में पुल:ब्रिज 3--4ब्रिज 0--3 
एल्गोरिदम
 
ब्रिजफाइंड (शुरू करें, विज़िट करें, डिस्क, कम, पैरेंट)
 

 इनपुट -  प्रारंभ शीर्ष, किसी नोड का दौरा करने पर चिह्नित करने के लिए विज़िट किया गया सरणी, डिस्क शीर्ष के खोज समय को बनाए रखेगा, और निम्न उप-प्रकारों के बारे में जानकारी रखेगा। पैरेंट वर्तमान शीर्ष के पैरेंट को धारण करेगा।
 

 आउटपुट - अगर कोई पुल मिलता है तो प्रिंट करें।
 
प्रारंभ समय:=0//अगले फ़ंक्शन कॉल के लिए समय का मान प्रारंभ नहीं किया जाएगा, विज़िट किए गए सेट डिस्क के रूप में प्रारंभ करें [प्रारंभ]:=समय + 1 और निम्न [प्रारंभ]:=समय + 1 समय:=समय + 1 ग्राफ जी में सभी शीर्ष वी के लिए, यदि (प्रारंभ, वी) के बीच एक किनारा है, तो अगर वी का दौरा किया जाता है, तो माता-पिता [वी]:=ब्रिज शुरू करें ढूंढें (वी, विज़िट, डिस्क, कम, माता-पिता) कम [शुरू]:=कम से कम [शुरू] और कम [वी] अगर कम [वी]> डिस्क [शुरू], तो शुरू से वी तक पुलों को प्रदर्शित करें यदि वी शुरुआत के माता-पिता नहीं है, तो कम [शुरू] :=कम से कम [शुरू] और डिस्क [v] किया गयाअंत
 
उदाहरण
 
#शामिल करें#नेमस्पेस एसटीडी का उपयोग करके नोड 5 परिभाषित करें;इंट ग्राफ[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}}; इंट मिन (इंट ए, इंट बी) {रिटर्न (ए <बी)? ए:बी;} शून्य ब्रिजफाइंड (इंट स्टार्ट, बूल विज़िट किया गया [], इंट डिस्क [], इंट लो [], इंट पैरेंट []) {स्थिर इंट टाइम =0; दौरा किया [शुरू] =सच; // पहले शीर्ष पर डिस्क का दौरा किया जाता है [शुरू] =कम [शुरू] =++ समय; // खोज समय और कम समय शुरू करें (int v =0; v  डिस्क [स्टार्ट]) cout <<"ब्रिज" <<प्रारंभ <<"-"< 
आउटपुट
 
दिए गए ग्राफ़ में पुल:पुल 3--4पुल 0--3