टार्जन का एल्गोरिदम एक निर्देशित ग्राफ के दृढ़ता से जुड़े घटकों को खोजने के लिए उपयोग किया जाता है। इस एल्गोरिदम को लागू करने के लिए केवल एक 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 को स्टैक में पुश करें stackItemFalg[u] := सच u के साथ आसन्न सभी शीर्ष v के लिए, करें यदि v खोजा नहीं गया है, तो fincComponent(v, disc, low, stack, stackItemFalg) low[u] = low[u] और low[v] का न्यूनतम अन्यथा यदि stackItemFalg[v] सच है, तो low[u] := low[u] और disc[v] का न्यूनतम किया poppedItem := 0 यदि low[u] = disc[u], तो जब तक u स्टैक के शीर्ष पर नहीं है, करें poppedItem := स्टैक का शीर्ष poppedItem प्रदर्शित करें stackItemFlag[poppedItem] := गलत स्टैक से आइटम पॉप करें किया poppedItem := स्टैक का शीर्ष poppedItem प्रदर्शित करें stackItemFlag[poppedItem] := गलत स्टैक से आइटम पॉप करें अंत
strongConComponent(graph)
इनपुट: दिया गया ग्राफ।
आउटपुट: सभी दृढ़ता से जुड़े घटक।
शुरू प्रारंभ में disc सरणी में सभी आइटम्स को अनखोजा सेट करें low में सभी तत्वों को φ और चिह्नित करें कि कोई आइटम स्टैक में संग्रहीत नहीं है ग्राफ में सभी नोड i के लिए, करें यदि disc[i] अनखोजा है, तो findComponent(i, disc, low, stack, stackItemFlag) अंत
उदाहरण
#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
आउटपुट
4 3 1 2 0
