টারজান'স অ্যালগরিদম ব্যবহার করা হয় একটি ডায়রেক্টেড গ্রাফের স্ট্রংলি কানেক্টেড কম্পোনেন্ট (SCC) খুঁজে বের করতে। এটি শুধু একটি DFS ট্রাভার্সাল দিয়ে ইমপ্লিমেন্ট করা যায়।
DFS ট্রাভার্সাল ব্যবহার করে আমরা গ্রাফের DFS ট্রি বা ফরেস্ট পেতে পারি। DFS ট্রি থেকে, স্ট্রংলি কানেক্টেড কম্পোনেন্টগুলো খুঁজে বের করা হয়। যখন এমন সাব-ট্রির রুট পাওয়া যায়, তখন আমরা পুরো সাব-ট্রিটি প্রদর্শন করতে পারি। সেই সাব-ট্রিটি একটি স্ট্রংলি কানেক্টেড কম্পোনেন্ট।
ইনপুট এবং আউটপুট
ইনপুট: গ্রাফের অ্যাডজেসেন্সি ম্যাট্রিক্স। 0 0 1 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 আউটপুট: স্ট্রংলি কানেক্টেড কম্পোনেন্টগুলো: 4 3 1 2 0
এলগরিদম
findComponent(u, disc, low, stack, stackItemFlag)
ইনপুট: শুরুর নোড, ডিসকভারি টাইম, low, disc হোল্ড করবে ভার্টেক্সের ডিসকভারি টাইম, এবং low হোল্ড করবে সাব-ট্রি সম্পর্কে তথ্য। স্ট্যাক ভার্টেক্স হোল্ড করবে এবং আরেকটি ফ্ল্যাগ অ্যারে ট্র্যাক করবে কোন নোড স্ট্যাকে আছে।
আউটপুট: SCC প্রদর্শন করুন।
শুরু
time := 0
// time-এর মান পরবর্তী ফাংশন কলের জন্য ইনিশিয়ালাইজ হবে না
disc[u] := time+1 এবং low[u] := time + 1 সেট করুন
time := time + 1
u কে স্ট্যাকে পুশ করুন
stackItemFlag[u] := true
u-র সাথে সন্নিহিত সব ভার্টেক্স v এর জন্য, করুন
যদি v ডিসকভার না করা থাকে, তবে
findComponent(v, disc, low, stack, stackItemFlag)
low[u] = low[u] এবং low[v]-এর ন্যূনতম
অন্যথায় যদি stackItemFlag[v] true হয়, তবে
low[u] := low[u] এবং disc[v]-এর ন্যূনতম
শেষ লুপ
poppedItem := 0
যদি low[u] = disc[u], তবে
যতক্ষণ u স্ট্যাকের টপে নয়, করুন
poppedItem := স্ট্যাকের টপ
poppedItem প্রদর্শন করুন
stackItemFlag[poppedItem] := false
স্ট্যাক থেকে আইটেম পপ করুন
শেষ লুপ
poppedItem := স্ট্যাকের টপ
poppedItem প্রদর্শন করুন
stackItemFlag[poppedItem] := false
স্ট্যাক থেকে আইটেম পপ করুন
শর্ত শেষ
শেষ
strongConComponent(graph)
ইনপুট: প্রদত্ত গ্রাফ।
আউটপুট: সব স্ট্রংলি কানেক্টেড কম্পোনেন্ট।
শুরু
প্রাথমিকভাবে disc অ্যারের সব আইটেমকে অনডিসকভার্ড সেট করুন
low-এ সব এলিমেন্টকে φ এবং
কোনো আইটেম স্ট্যাকে স্টোর করা নেই এমনভাবে চিহ্নিত করুন
গ্রাফের সব নোড i এর জন্য, করুন
যদি disc[i] অনডিসকভার্ড থাকে, তবে
findComponent(i, disc, low, stack, stackItemFlag)
শেষ
উদাহরণ (C++ কোড)
#include <iostream>
#include <stack>
#define NODE 5
using namespace std;
int graph[NODE][NODE] = {
{0, 0, 1, 1, 0},
{1, 0, 0, 0, 0},
{0, 1, 0, 0, 0},
{0, 0, 0, 0, 1},
{0, 0, 0, 0, 0}
};
int min(int a, int b) {
return (a < b) ? a : b;
}
void findComponent(int u, int disc[], int low[], stack<int> &stk, bool stkItem[]) {
static int time = 0;
disc[u] = low[u] = ++time; // প্রাথমিকভাবে ডিসকভারি টাইম এবং low ভ্যালু ১
stk.push(u);
stkItem[u] = true; // u স্ট্যাকে আছে বলে ফ্ল্যাগ করুন
for(int v = 0; v < NODE; v++) {
if(graph[u][v]) {
if(disc[v] == -1) { // যখন v ভিজিটেড নয়
findComponent(v, disc, low, stk, stkItem);
low[u] = min(low[u], low[v]);
} else if(stkItem[v]) // যখন v স্ট্যাকে আছে, u-র জন্য low আপডেট করুন
low[u] = min(low[u], disc[v]);
}
}
int poppedItem = 0;
if(low[u] == disc[u]) {
while(stk.top() != u) {
poppedItem = stk.top();
cout << poppedItem << " ";
stkItem[poppedItem] = false; // আইটেম পপ করা হয়েছে বলে চিহ্নিত করুন
stk.pop();
}
poppedItem = stk.top();
cout << poppedItem << endl;
stkItem[poppedItem] = false;
stk.pop();
}
}
void strongConComponent() {
int disc[NODE], low[NODE];
bool stkItem[NODE];
stack<int> stk;
for(int i = 0; i < NODE; i++) {
// সব এলিমেন্ট ইনিশিয়ালাইজ করুন
disc[i] = low[i] = -1;
stkItem[i] = false;
}
for(int i = 0; i < NODE; i++) // সব এলিমেন্ট ইনিশিয়ালাইজ করুন
if(disc[i] == -1)
findComponent(i, disc, low, stk, stkItem);
}
int main() {
strongConComponent();
}
আউটপুট
4 3 1 2 0
