এক অনির্দেশিত গ্রাফে একটি এজকে ব্রিজ বলা হয়, যদি এবং কেবল যদি সেটি রিমুভ করলে গ্রাফ ডিসকানেক্টেড হয়, বা গ্রাফের ভিন্ন কম্পোনেন্ট তৈরি হয়।
বাস্তব জীবনে, যদি কোনো নেটওয়ার্কে ব্রিজ থাকে, এবং ব্রিজের কানেকশন ভাঙলে, পুরো নেটওয়ার্ক ভেঙে যেতে পারে।
ইনপুট এবং আউটপুট
ইনপুট: গ্রাফের এডজেসেন্সি ম্যাট্রিক্স। 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 আউটপুট: Bridges in given graph: Bridge 3--4 Bridge 0--3
অ্যালগরিদম
bridgeFind(start, visited, disc, low, parent)
ইনপুট - শুরুর ভার্টেক্স, ভিজিটেড অ্যারে নোড ভিজিটেড কিনা মার্ক করতে, disc ভার্টেক্সের ডিসকভারি টাইম ধারণ করবে, এবং low সাবট্রি সম্পর্কে ইনফরমেশন রাখবে। parent কারেন্ট ভার্টেক্সের পেরেন্ট ধারণ করবে।
আউটপুট - যদি কোনো ব্রিজ পাওয়া যায় প্রিন্ট করুন।
শুরু
time := 0
//time-এর ভ্যালু নেক্সট ফাংশন কলের জন্য ইনিশিয়ালাইজ হবে না
start কে ভিজিটেড মার্ক করুন
disc[start] := time+1 এবং low[start] := time + 1 সেট করুন
time := time + 1
গ্রাফ G-তে সব ভার্টেক্স v-এর জন্য করুন
যদি (start, v) এর মধ্যে এজ থাকে, তবে
যদি v ভিজিটেড হয়, তবে
parent[v] := start
bridgeFind(v, visited, disc, low, parent)
low[start] := minimum of low[start] and low[v]
যদি low[v] > disc[start], তবে
start থেকে v পর্যন্ত ব্রিজ ডিসপ্লে করুন
অন্যথায় যদি v start-এর পেরেন্ট নয়, তবে
low[start] := minimum of low[start] and disc[v]
শেষ
শেষ
উদাহরণ
#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 disc[start]) cout << "Bridge " << start << "--"<<v<<endl; } else if(v != parent[start]) //পূর্বের কলের জন্য start-এর low আপডেট করুন 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
