দৃঢ়ভাবে সংযুক্ত উপাদানগুলির জন্য টারজানের অ্যালগরিদম

টারজানের অ্যালগরিদম একটি নির্দেশিত গ্রাফের দৃঢ়ভাবে সংযুক্ত উপাদানগুলি খুঁজে পেতে ব্যবহৃত হয়৷ এই অ্যালগরিদম বাস্তবায়নের জন্য শুধুমাত্র একটি DFS ট্রাভার্সাল প্রয়োজন৷

DFS ট্রাভার্সাল ব্যবহার করে আমরা বনের DFS গাছ খুঁজে পেতে পারি। DFS গাছ থেকে, দৃঢ়ভাবে সংযুক্ত উপাদান পাওয়া যায়। এই ধরনের সাব-ট্রির মূল পাওয়া গেলে আমরা পুরো সাব-ট্রি প্রদর্শন করতে পারি। সেই সাবট্রি হল একটি দৃঢ়ভাবে সংযুক্ত উপাদান৷

ইনপুট এবং আউটপুট

ইনপুট:গ্রাফের অ্যাডজাসেন্সি ম্যাট্রিক্স। 0 0 1 1 01 0 0 0 0 00 1 0 0 00 0 0 0 10 0 0 0 0 আউটপুট:দৃঢ়ভাবে সংযুক্ত উপাদানগুলি:431 2 0 

অ্যালগরিদম

কম্পোনেন্ট খুঁজুন(u, disc, low, stack, stackItemFlag)

ইনপুট: স্টার্ট নোড, আবিষ্কারের সময়, কম, ডিস্কটি শীর্ষবিন্দুর আবিষ্কারের সময় ধরে রাখবে, এবং লো সাবট্রি সম্পর্কে তথ্য ধারণ করবে। শীর্ষবিন্দু ধরে রাখার স্ট্যাক এবং স্ট্যাকের মধ্যে কোন নোড আছে তা ট্র্যাক করার জন্য আরেকটি ফ্ল্যাগ অ্যারে।

আউটপুট: SCC প্রদর্শন করুন৷

 সময় শুরু :=0 // সময়ের মান পরবর্তী ফাংশন কল সেট ডিস্কের জন্য আরম্ভ করা হবে না in stack stackItemFalg[u] :=u এর সাথে সংলগ্ন সকল শীর্ষবিন্দু v এর জন্য সত্য, যদি v আবিষ্কৃত না হয়, তাহলে ফিঙ্ককম্পোনেন্ট(v, ডিস্ক, লো, স্ট্যাক, স্ট্যাকআইটেমফাল্গ) low[u] =সর্বনিম্ন কম[u] এবং নিম্ন আপনি স্ট্যাকের শীর্ষে নেই, poppedItem করুন :=স্ট্যাক ডিসপ্লে poppedItem stackItemFlag[poppedItem] :=স্ট্যাক থেকে মিথ্যা পপ আইটেম সম্পন্ন poppedItem :=স্ট্যাক ডিসপ্লে poppedItem stackItemFlag[poppedItem] :=stackEnd থেকে মিথ্যা পপ আইটেম প্রাক> 

 কনকম্পোনেন্ট(গ্রাফ) 
 

 ইনপুট &,মাইনাস;  প্রদত্ত গ্রাফ।
 

 আউটপুট - সমস্ত দৃঢ়ভাবে সংযুক্ত উপাদান।
 
প্রাথমিকভাবে ডিস্ক অ্যারের সমস্ত আইটেমগুলিকে নিম্ন থেকে φ পর্যন্ত সমস্ত উপাদানের জন্য আনডিসকভারে সেট করুন এবং গ্রাফের সমস্ত নোড i-এর জন্য স্ট্যাকের মধ্যে কোনো আইটেম সংরক্ষণ করা নেই বলে চিহ্নিত করুন, যদি ডিস্ক[i] অনাবিষ্কৃত হয়, তাহলে কম্পোনেন্ট খুঁজুন( i, disc, low, stack, stackItemFlag)End
 
উদাহরণ
 
#include#include#define NODE 5 ব্যবহার করে namespace std; int গ্রাফ[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) { রিটার্ন (a&stk, bool stkItem[]) { স্ট্যাটিক int সময় =0; disc[u] =low[u] =++time; //প্রাথমিকভাবে আবিষ্কারের সময় এবং কম মান হল 1 stk.push(u); stkItem[u] =সত্য; // (int v =0; v stk; for(int i =0; i 
আউটপুট
 
431 2 0