क्या तारजन का एससीसी एल्गोरिदम एससीसी का एक स्थलीय प्रकार देता है?

Question

मैं उनके बारे में एससीसी और एल्गोरिदम का अध्ययन कर रहा हूं, और मैंने देखा है कि लोग लगभग हमेशा उल्लेख करते हैं कि कोसारजु के एल्गोरिदम को एससीसी मिलती है और उन्हें एक (उल्टा) स्थलीय प्रकार में भी आदेश दिया जाता है।

मेरा सवाल है: क्या Tarjan के एल्गोरिदम को एक (उल्टा) स्थलीय प्रकार भी नहीं मिलता है? मैंने पाया है कि इसका उल्लेख नहीं किया गया है (कम से कम जहां से मैंने पढ़ा है, विकिपीडिया को छोड़कर)।

मैं इसके बारे में सोच रहा हूं और सही समझ में हूं। जब आपको कुछ नोड पर tarjans_dfs कहा जाता है, तो आपके द्वारा पहुंचने योग्य सभी एससीसी आपके एससीसी से पहले पाए जाएंगे। क्या मै गलत हु?

विकिपीडिया कहते हैं कि यह वास्तव में यह मिल रहा है:

"जबकि वहाँ भीतर नोड्स एक प्रभावशाली तरीके से कनेक्ट घटक के आदेश के बारे में कुछ खास नहीं है, एल्गोरिथ्म में से एक उपयोगी संपत्ति है कि कोई सशक्त रूप से जुड़े घटक है इसके किसी भी उत्तराधिकारी से पहले की पहचान की जाएगी। इसलिए, जिस क्रम में दृढ़ता से जुड़े घटकों की पहचान की गई है, दृढ़ता से जुड़े घटकों द्वारा गठित डीएजी के स्थलीय प्रकार का गठन किया गया है। "

क्या यह मेरा विचार है, या क्या यह अधिक ज्ञात है कि कोसारजु के एल्गोरिदम को इस तथ्य की तुलना में स्थलीय आदेश मिल गया है कि तारजन भी ऐसा करता है?

Answer 1

ऐसा करता है, मैं इसका उपयोग कर रहा हूं और वही प्रश्न मेरे दिमाग में आया है।

मेरे पास वास्तव में इसका प्रदर्शन करने का समय नहीं है लेकिन हर टेस्ट केस (हजारों) हमेशा एक स्थलीय सॉर्ट किए गए संघनित ग्राफ को लौटाता है।

Answer 2

हाँ, यह करता है। तारजन का एससीसी एल्गोरिदम एक ग्राफ पर एक डीएफएस प्रदर्शन करके और एससीसी के जड़ों को एक ढेर पर ट्रैक करके काम करता है। एक स्थलीय प्रकार खोजने का एक तरीका ग्राफ पर डीएफएस कर रहा है और निकास आदेश का ट्रैक रख रहा है। तारजन के एससीसी एल्गोरिदम में इन नोड्स का निकास आदेश एक स्थलीय प्रकार प्रदान करता है।

डोनाल्ड नुथ भी उल्लेख है यह in an interview जब Tarjan के एस सी सी एल्गोरिथ्म, जो वे कहते हैं के बारे में बात अपने पसंदीदा में से एक है:

डेटा संरचनाओं है कि वह इस समस्या के लिए एक आश्चर्यजनक सुंदर तरीके से एक साथ फिट तैयार है, तो निर्देशित ग्राफ की खोज करते समय आपको जिस मात्रा को देखने की आवश्यकता है वह हमेशा आपकी उंगलियों पर जादुई रूप से होती है। और उसका एल्गोरिदम भी उपज के रूप में टोपोलॉजिकल सॉर्टिंग करता है।

Answer 3

हां। जैसा कि तारजन गहराई की पहली खोज पर आधारित है, आपको केवल एक सूची के शीर्ष पर कशेरुक जोड़ना है जब प्रत्येक चरम सीमा "बंद" स्थिति तक पहुंच जाती है। (यानी इसका डीएफएस/टैरजन कॉल उस कशेरुक के लिए समाप्त होता है)

यहां एक सी/सी ++/छद्म कोड है उदाहरण:

void tarjan(int u) { 
    visited[u] = true; 
    closed[u] = false; 
    //dfs + tarjan processing 
    for (vi v = G[u].begin(); v != G[u].end(); v++) { 
     if (!visited[*v]) { 
      dfs(*v); 
     } else if (!closed[*v]) { 
      // has Cycle 
     } 
    } 
    closed[u] = true; 
    //add u to the top of your list here 
}