कोसाराजू का एल्गोरिद्म एक डायरेक्टेड ग्राफ के स्ट्रॉन्गली कनेक्टेड कंपोनेंट्स (SCCs) ढूंढता है। एक SCC वर्टिसेस का ऐसा समूह है जहाँ हर वर्टेक्स बाकी सभी तक पहुँच सकता है। यह एल्गोरिद्म दो डेप्थ-फर्स्ट सर्च चलाता है: पहली बार में वर्टिसेस के खत्म होने का क्रम रिकॉर्ड होता है, और दूसरी बार में हर एज को उलटकर बने ग्राफ पर, वर्टिसेस को उल्टे फिनिश ऑर्डर में लेते हुए सर्च चलती है। दूसरी सर्च का हर ट्री एक SCC होता है। यह O(V + E) समय में चलता है।
अगर आप हर SCC को एक ही नोड में दबा दें, तो जो बचता है वह बिना किसी साइकल वाला डायरेक्टेड ग्राफ होता है। इसीलिए SCCs डिपेंडेंसी एनालिसिस, डेडलॉक डिटेक्शन, 2-SAT, और हर उस समस्या में काम आते हैं जहाँ साइकल्स को पहले खत्म करना पड़ता है।
दोनों पास, एक-एक कदम
- पूरे ग्राफ पर DFS चलाएँ। जब कोई वर्टेक्स खत्म होता है (उसके सारे आउटगोइंग पड़ोसी हो चुके हों), तो उसे एक लिस्ट में डाल दें।
- हर एज को उलटकर ट्रांसपोज़ ग्राफ बनाएँ।
- फिनिश लिस्ट को आखिर से शुरू तक देखें। हर उस वर्टेक्स के लिए जो अभी तक विज़िट नहीं हुआ, ट्रांसपोज़ ग्राफ पर DFS चलाएँ। उस सर्च में जो कुछ भी आता है, वह एक SCC होता है।
दोनों लूप हर बिना विज़िट वाले वर्टेक्स से शुरू होने चाहिए, सिर्फ वर्टेक्स 0 से नहीं, क्योंकि ग्राफ कनेक्टेड नहीं भी हो सकता है।
एक हल किया हुआ उदाहरण
8 वर्टिसेस और ये एज लें:
0 → 1, 1 → 2, 2 → 0 (cycle A: 0, 1, 2)
2 → 3
3 → 4, 4 → 5, 5 → 3 (cycle B: 3, 4, 5)
6 → 5
6 → 7, 7 → 6 (cycle C: 6, 7)
SCCs होने चाहिए 2, 5, और 7।
पहला पास
DFS को 0 से शुरू करें और 0 → 1 → 2 → 3 → 4 → 5 चलें। वर्टेक्स 5 के पास जाने के लिए कोई नई जगह नहीं है, तो वह सबसे पहले खत्म होता है, फिर 4, फिर 3। 2 पर वापस आने पर कुछ बचा नहीं है, तो 2, 1, और 0 खत्म हो जाते हैं। वर्टेक्स 6 अभी तक विज़िट नहीं हुआ, तो वहाँ से शुरू करें: 5 तो पहले ही हो चुका है, तो 7 पर जाएँ, जो खत्म होता है, फिर 6। फिनिश ऑर्डर है:
5, 4, 3, 2, 1, 0, 7, 6
दूसरा पास
हर एज को उलटें और वर्टिसेस को उस लिस्ट के आखिर से प्रोसेस करें: पहले 6। उलटे ग्राफ में, 6 सिर्फ 7 तक पहुँच सकता है, तो 7 पहला SCC है। अगला बिना विज़िट वाला 0 है, जो उलटे ग्राफ में 2 और 1 तक पहुँचता है, जिससे 2 मिलता है। एज 2 → 3 अब 3 → 2 की ओर इशारा करता है, लेकिन 2 तो पहले ही असाइन हो चुका है, तो सर्च वहीं रुक जाती है। आखिर में, 3, 5 और 4 तक पहुँचता है, जिससे 5 मिलता है।
यह क्यों काम करता है
SCCs के ग्राफ के बारे में सोचें (हर कंपोनेंट एक नोड में दबा हुआ), जिसमें कोई साइकल नहीं होती। पहले पास में, जो वर्टेक्स सबसे आखिर में खत्म होता है वह हमेशा एक "सोर्स" कंपोनेंट से होता है, यानी ऐसा कंपोनेंट जिसमें बाकी बिना असाइन कंपोनेंट्स से कोई एज नहीं आती। एज को उलटने से वह सोर्स एक सिंक बन जाता है, तो वहाँ से शुरू हुई DFS अपने कंपोनेंट से बाहर नहीं जा सकती। एक बार वह कंपोनेंट हट जाए, तो वही तर्क अगले पर लागू होता है।
इंटरव्यू में, आमतौर पर इसी स्तर का प्रमाण अपेक्षित होता है: फिनिश ऑर्डर एक सुरक्षित शुरुआती कंपोनेंट चुन लेता है, और एज उलटने से दूसरी सर्च बाकी कंपोनेंट्स में नहीं फैलती।
Python इम्प्लीमेंटेशन
यह वर्शन इटरेटिव DFS इस्तेमाल करता है, तो गहरे ग्राफ पर Python की रिकर्शन लिमिट नहीं टकराएगी।
from collections import defaultdict
def kosaraju(n, edges):
graph = defaultdict(list)
reverse = defaultdict(list)
for u, v in edges:
graph[u].append(v)
reverse[v].append(u)
# Pass 1: record vertices in the order they finish (iterative DFS)
visited = [False] * n
order = []
for start in range(n):
if visited[start]:
continue
visited[start] = True
stack = [(start, iter(graph[start]))]
while stack:
node, neighbors = stack[-1]
for nxt in neighbors:
if not visited[nxt]:
visited[nxt] = True
stack.append((nxt, iter(graph[nxt])))
break
else:
stack.pop()
order.append(node)
# Pass 2: DFS on the reversed graph, latest finish time first
visited = [False] * n
components = []
for start in reversed(order):
if visited[start]:
continue
visited[start] = True
component = []
stack = [start]
while stack:
node = stack.pop()
component.append(node)
for nxt in reverse[node]:
if not visited[nxt]:
visited[nxt] = True
stack.append(nxt)
components.append(component)
return components
edges = [(0, 1), (1, 2), (2, 0), (2, 3), (3, 4), (4, 5), (5, 3), (6, 5), (6, 7), (7, 6)]
print(kosaraju(8, edges)) # [[6, 7], [0, 2, 1], [3, 5, 4]]
हर कंपोनेंट के अंदर वर्टिसेस का क्रम ट्रैवर्सल पर निर्भर करता है, तो अपने टेस्ट में कंपोनेंट्स की तुलना सेट्स की तरह करें। हमने इस इम्प्लीमेंटेशन को 2,000 रैंडम ग्राफ पर ब्रूट-फोर्स रीचेबिलिटी चेक से मिलाया।
कॉम्प्लेक्सिटी
| स्टेप | समय |
|---|---|
| पहली DFS | O(V + E) |
| उलटा ग्राफ बनाना | O(V + E) |
| दूसरी DFS | O(V + E) |
| कुल | O(V + E) |
स्पेस दो एडजेसेंसी लिस्ट्स के लिए O(V + E) है, साथ में विज़िटेड एरे, फिनिश ऑर्डर, और स्टैक के लिए O(V)।
वे गलतियाँ जो इसे तोड़ देती हैं
सबसे आम बग यह है कि वर्टिसेस को तब रिकॉर्ड कर लिया जाए जब DFS पहली बार उन तक पहुँचे, बजाय तब जब वे खत्म हों। बाकी गलतियाँ हैं: दूसरे पास के लिए फिनिश ऑर्डर उलटना भूल जाना, दूसरा पास उलटे ग्राफ की जगह ओरिजिनल ग्राफ पर चला देना, दोनों पास के बीच विज़िटेड एरे क्लियर न करना, और सिर्फ वर्टेक्स 0 से शुरू करना जिससे डिसकनेक्टेड हिस्से छूट जाते हैं। रिकर्सिव DFS लंबी चेन पर स्टैक भी ओवरफ्लो कर सकती है, इसीलिए ऊपर का कोड इटरेटिव है।
अच्छे टेस्ट केस: एक अकेला वर्टेक्स, सेल्फ-लूप वाला वर्टेक्स, एक बड़ी साइकल, एक वन-वे चेन (हर वर्टेक्स अपना ही SCC), एक एज से जुड़ी दो साइकल्स, और एक डिसकनेक्टेड ग्राफ।
कोसाराजू बनाम टार्जन
दोनों O(V + E) में चलते हैं। कोसाराजू दो पास लेता है और उलटा ग्राफ बनाता है, जिससे इसे समझाना और सही करना आसान होता है। टार्जन का एल्गोरिद्म इसे एक ही पास में, बिना उलटे ग्राफ के करता है, लेकिन डिस्कवरी इंडेक्स और लो-लिंक वैल्यूज़ को स्टैक पर ट्रैक करता है, जो संभालने के लिए ज़्यादा स्टेट है। इंटरव्यू में, जो भी आप सही से इम्प्लीमेंट और समझा सकें, वही इस्तेमाल करें। अगर इंटरव्यूअर सिंगल पास माँगे, तो वह टार्जन का इशारा है।
ग्राफ समस्याओं की प्रैक्टिस
कोड लिखने से पहले ऊपर का उदाहरण एक बार हाथ से ट्रेस करें; ज़्यादातर बग गलत फिनिश ऑर्डर के रूप में दिखते हैं। जुड़ी गाइड्स: Floyd–Warshall ऑल-पेयर्स शॉर्टेस्ट पाथ्स के लिए, Bellman–Ford नेगेटिव एज वाले ग्राफ के लिए, और हमारी Big O चीट शीट। अगर आप कोडिंग प्रैक्टिस में YesToTheOffer इस्तेमाल करते हैं, तो इसकी स्क्रीनशॉट कोडिंग हेल्प आपके अप्रोच को चेक कर सकती है, और सेशन ट्रांसक्रिप्ट दिखाता है कि आपने अपनी सोच साफ़-साफ़ समझाई या नहीं।
प्रतिक्रिया के साथ कोडिंग साक्षात्कार का अभ्यास करें
स्क्रीनशॉट कोडिंग सहायता और आपके अभ्यास सत्र का प्रतिलेख। 30 मुफ्त मिनट।
