এক অনির্দেশিত গ্রাফকে বাইকানেক্টেড গ্রাফ বলা হয়, যদি किन्हीं দুটি ভার্টেক্সের মাঝে দুটি ভার্টেক্স-ডিসজয়েন্ট পথ উপস্থিত থাকে। অন্য কথায়, যেকোনো দুটি ভার্টেক্সের মাঝে একটি সাইকেল আছে বলে বলা যায়।
আমরা বলতে পারি যে একটি গ্রাফ G বাই-কানেক্টেড যদি সেটি কানেক্টেড হয়, এবং গ্রাফে কোনো আর্টিকুলেশন পয়েন্ট বা কাট ভার্টেক্স উপস্থিত নয়।
এই সমস্যা সমাধান করতে, আমরা DFS ট্রাভার্সাল ব্যবহার করব। DFS ব্যবহার করে, আমরা চেষ্টা করব কোনো আর্টিকুলেশন পয়েন্ট আছে কিনা খুঁজে বের করতে। আমরা চেক করব সব ভার্টেক্স DFS দিয়ে ভিজিটেড হয়েছে কিনা, যদি না হয় তবে বলতে পারি গ্রাফটি কানেক্টেড নয়।
ইনপুট এবং আউটপুট
ইনপুট: গ্রাফের এডজেসেন্সি ম্যাট্রিক্স। 0 1 1 1 0 1 0 1 0 0 1 1 0 0 1 1 0 0 0 1 0 0 1 1 0 আউটপুট: The Graph is a biconnected graph.
অ্যালগরিদম
isArticulation(start, visited, disc, low, parent)
ইনপুট: শুরুর ভার্টেক্স, ভিজিটেড অ্যারে নোড ভিজিটেড কিনা মার্ক করতে, disc ভার্টেক্সের ডিসকভারি টাইম ধারণ করবে, এবং low সাবট্রি সম্পর্কে ইনফরমেশন রাখবে। parent কারেন্ট ভার্টেক্সের পেরেন্ট ধারণ করবে।
আউটপুট - True যদি কোনো আর্টিকুলেশন পয়েন্ট পাওয়া যায়।
শুরু
time := 0
//time-এর ভ্যালু নেক্সট ফাংশন কলের জন্য ইনিশিয়ালাইজ হবে না
dfsChild := 0
start কে ভিজিটেড মার্ক করুন
disc[start] := time+1 এবং low[start] := time + 1 সেট করুন
time := time + 1
গ্রাফ G-তে সব ভার্টেক্স v-এর জন্য করুন
যদি (start, v) এর মধ্যে এজ থাকে, তবে
যদি v ভিজিটেড হয়, তবে
dfsChild বাড়ান
parent[v] := start
যদি isArticulation(v, visited, disc, low, parent) true হয়, তবে
return true
low[start] := minimum of low[start] and low[v]
যদি parent[start] is φ AND dfsChild > 1, তবে
return true
যদি parent[start] is φ AND low[v] >= disc[start], তবে
return true
অন্যথায় যদি v start-এর পেরেন্ট নয়, তবে
low[start] := minimum of low[start] and disc[v]
শেষ
return false
শেষ
isBiconnected(graph)
ইনপুট: দেওয়া গ্রাফ।
আউটপুট - True যদি গ্রাফ বাই-কানেক্টেড হয়।
শুরু
প্রাথমিকভাবে সব ভার্টেক্স আনভিজিটেড এবং প্রতিটি ভার্টেক্সের পেরেন্ট φ সেট করুন
যদি isArticulation(0, visited, disc, low, parent) = true, তবে
return false
গ্রাফের প্রতিটি নোড i-এর জন্য করুন
যদি i ভিজিটেড না হয়, তবে
return false
শেষ
return true
শেষ
উদাহরণ
#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 1) { //যখন u-র ২ বা অধিক চাইল্ড থাকে return true; } if(parent[start] != -1 && low[v]>= disc[start]) return true; } else if(v != parent[start]) //পূর্বের কলের জন্য start-এর low আপডেট করুন low[start] = min(low[start], disc[v]); } } return false; } bool isBiConnected() { 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
আউটপুট
The Graph is a biconnected graph.
