निर्देशित ग्राफ को जांचने के लिए एल्गोरिदम

Question

मुझे यह जांचने की आवश्यकता है कि एक निर्देशित ग्राफ दृढ़ता से से जुड़ा हुआ है, या दूसरे शब्दों में, यदि सभी नोड्स किसी भी अन्य नोड (सीधे किनारे के माध्यम से नहीं) तक पहुंचा जा सकता है।

ऐसा करने का एक तरीका प्रत्येक नोड पर एक डीएफएस और बीएफएस चला रहा है और सभी अन्य अभी भी पहुंच योग्य हैं।

क्या ऐसा करने के लिए कोई बेहतर तरीका है?

Answer 1

Tarjan's दृढ़ता से जुड़े घटक एल्गोरिदम (या Gabow's भिन्नता) निश्चित रूप से पर्याप्त होंगे; अगर केवल एक दृढ़ता से जुड़े घटक हैं, तो ग्राफ दृढ़ता से जुड़ा हुआ है।

दोनों रैखिक समय हैं।

सामान्य गहराई की पहली खोज के साथ, आप प्रत्येक नोड की स्थिति को ट्रैक करते हैं: नया, देखा गया लेकिन अभी भी खुला है (यह कॉल स्टैक में है), और देखा और समाप्त हुआ। इसके अतिरिक्त, जब आप पहली बार नोड तक पहुंचते हैं तो गहराई को स्टोर करते हैं, और निम्नतम गहराई जो नोड से पहुंच योग्य है (आप इसे नोड खत्म करने के बाद जानते हैं)। एक नोड एक दृढ़ता से जुड़े घटक की जड़ है यदि सबसे कम पहुंच योग्य गहराई अपनी गहराई के बराबर है। यह तब भी काम करता है जब आप जिस गहराई से रूट से नोड तक पहुंचते हैं, वह न्यूनतम संभव नहीं है।

यह देखने के लिए कि क्या संपूर्ण ग्राफ एक एकल एससीसी है, किसी भी एकल नोड से डीएफएस शुरू करें, और जब आप समाप्त कर लें, तो सबसे कम पहुंचने योग्य गहराई 0 है, और प्रत्येक नोड का दौरा किया गया था, तो संपूर्ण ग्राफ दृढ़ता से जुड़ा हुआ है।

Answer 2

आप All-Pairs Shortest Path की गणना कर सकते हैं और देख सकते हैं कि कोई भी अनंत है।

Answer 3

ऐसा करने का एक तरीका ग्राफ के लिए Laplacian matrix उत्पन्न करना होगा, फिर eigenvalues ​​की गणना करें, और अंत में शून्य की संख्या गिनें। ग्राफ केवल दृढ़ता से कनेक्शन है यदि केवल एक शून्य eigenvalue मौजूद है।

नोट: निर्देशित ग्राफ के लिए लैपलाशियन मैट्रिक्स बनाने के लिए थोड़ा अलग विधि पर ध्यान दें।

Answer 4

तारजन के एल्गोरिदम का पहले से ही उल्लेख किया गया है। लेकिन मुझे आमतौर पर Kosaraju's Algorithm का पालन करना आसान लगता है, भले ही इसे ग्राफ के दो ट्रैवर्सल की आवश्यकता हो। आईआईआरसी, यह सीएलआरएस में भी अच्छी तरह से समझाया गया है।

Answer 5

test-connected(G) 
{ 
    choose a vertex x 
    make a list L of vertices reachable from x, 
    and another list K of vertices to be explored. 
    initially, L = K = x. 

    while K is nonempty 
    find and remove some vertex y in K 
    for each edge (y, z) 
    if (z is not in L) 
    add z to both L and K 

    if L has fewer than n items 
    return disconnected 
    else return connected 
} 

Answer 6

निम्नलिखित एल्गोरिदम पर विचार करें।

---

1. प्रारंभ ग्राफ G के एक यादृच्छिक शिखर v पर, और एक DFS(G, v) चलाते हैं।

   • DFS(G, v) ग्राफ G में हर दूसरे शिखर तक पहुंचने के लिए विफल रहता है, तो वहाँ कुछ शीर्ष u, है कोई निर्देशित पथ v से u है ऐसा है कि, और इस तरह Gप्रभावशाली तरीके से कनेक्ट नहीं है।

   • यदि यह प्रत्येक चरम पर पहुंचता है, तो v से ग्राफ़ G में प्रत्येक अन्य कशेरुक के लिए एक निर्देशित पथ है।

2. निर्देशित ग्राफ G में सभी किनारों की दिशा रिवर्स ।

3. से DFS पर फिर से चलाएं।

   • डीएफएस हर शिखर तक पहुंचने के लिए विफल रहता है, तो वहाँ कुछ शीर्ष u, मूल ग्राफ में कोई निर्देश दिया पथ u से v लिए है कि वहाँ है इस तरह के।

   • दूसरी ओर, अगर यह हर शिखर तक पहुँचने करता है, तो मूल ग्राफ में वहाँ v के लिए हर शिखर u से एक निर्देशित मार्ग है।

इस प्रकार, यदि जी "गुजरता" दोनों DFSS, यह दृढ़ता से जुड़ा हुआ है। इसके अलावा, चूंकि एक डीएफएस O(n + m) समय में चलता है, इसलिए यह एल्गोरिदम O(2(n + m)) = O(n + m) समय में चलता है, क्योंकि इसे 2 डीएफएस ट्रैवर्सल की आवश्यकता होती है।