मैं तर्जन के एल्गोरिदम कैसे सीखूं?

Question

मैं अब 3 घंटे के लिए विकिपीडिया से तारजन के एल्गोरिदम सीखने की कोशिश कर रहा हूं, लेकिन मैं इसका सिर या पूंछ नहीं बना सकता। :(

http://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm#cite_note-1

ऐसा क्यों है डीएफएस पेड़ की एक सबट्री है? (वास्तव में डीएफएस एक जंगल? O_O पैदा करता है) और क्यों v.lowlink=v.index मतलब है कि v एक जड़ है करता है?

किसी कृपया समझा सकते हैं यह मेरे लिए/इस एल्गोरिदम के पीछे अंतर्ज्ञान या प्रेरणा देता है?

Answer 1

विचार यह है: जब पेड़ को पार करते समय, हर बार जब आप एक शाखा के माध्यम से खोज करते हैं और बैकट्रैकिंग करते हैं, तो आप जांचते हैं कि क्या आपको किनारे का सामना करना पड़ा है या नहीं पेड़ में 'ऊपरी' नोड।

• आप नहीं किया है (if (v.lowlink = v.index)), तो आप सिर्फ एक एस सी सी पूरा कर दिया है - यह वर्तमान नोड और ढेर पर सभी नोड्स के होते हैं। यह वास्तव में पूरा होने वाले एससीसी में नोड्स को छोड़कर डीएफएस पेड़ का एक उप-हिस्सा है।

• यदि आपने किया, तो आप इस जानकारी को 'ऊपरी' नोड्स (v.lowlink := min(v.lowlink, w.lowlink)) पर प्रसारित करते हैं, क्योंकि डीएफएस पेड़ में पथ के साथ संयुक्त किनारे एक 'ऊपर की ओर' पथ बनाता है।

डीएफएस जंगल का उत्पादन करता है, लेकिन आप हमेशा एक पेड़ को एक समय पर विचार करते हैं। एक एससीसी हमेशा एक डीएफएस पेड़ में शामिल होता है, अन्यथा (एक एससीसी होने के नाते) प्रश्न में दोनों (सभी) पेड़ों के बीच दोनों दिशाओं में एक पथ होगा - यह एक विरोधाभास है।

Answer 2

बस pjotr के उत्तर में जोड़ना: v.lowlink मूल रूप से पेड़ में पाए गए सबसे ऊपर नोड का सूचकांक है। ध्यान रखें कि इस संदर्भ में सबसे अधिक मतलब है कि जब आप नीचे चलते हैं तो आप सूचकांक में वृद्धि करते रहते हैं।

1. v.lowlink < v.index:: अब अपने सभी उत्तराधिकारियों संसाधित करने के बाद, वहाँ मूल रूप से तीन मामलों है यह इंगित करता है कि आप एक वापस बढ़त मिल गई है। ध्यान दें कि हमारे पास नहीं है, बस किसी भी पिछली किनारे पर पाया गया है, लेकिन वह एक जो नोड को इंगित करता है जो वर्तमान "ऊपर" है। यही v.lowlink < v.index का तात्पर्य है।

2. v.lowlink = v.index: हम इस मामले में क्या जानते हैं कि वर्तमान नोड के ऊपर कुछ भी संदर्भ नहीं है। इस नोड के पीछे एक पिछला किनारा हो सकता है (जिसका अर्थ है कि आपके उत्तराधिकारी नोड्स में से एक में कम लिंक है जैसे w.lowlink = v.lowlink = v.index)। यह भी हो सकता है कि वर्तमान नोड के नीचे कुछ का जिक्र करने वाला बैक एज था, जिसका अर्थ है कि वर्तमान नोड के नीचे एक दृढ़ता से जुड़े घटक थे जो पहले से ही मुद्रित किए गए हैं। वर्तमान नोड, हालांकि, निश्चित रूप से दृढ़ता से जुड़े घटक की जड़ भी है।

3. v.lowlink> v.index: यह वास्तव में संभव नहीं है। मैं सिर्फ पूर्णता के लिए इसे सूचीबद्ध कर रहा हूं। ;)

उम्मीद है कि यह मदद करता है!

Answer 3

Tarjan के एल्गोरिथ्म के बारे में कुछ अंतर्ज्ञान:

• डीएफएस के दौरान, जब हम शिखर वी से एक वापस किनारे सामना करते हैं, हम अपने न्यूनतम पहुंच योग्य पूर्वज यानी हम का मान अपडेट अद्यतन कम [V]

• अब जब एक कशेरुक के सभी आउटगोइंग किनारों को संसाधित किया जाता है यानी हम वर्टेक्स वी के लिए डीएफएस कॉल से बाहर निकलने वाले हैं, तो हम कम [v] के मान की जांच करते हैं, चाहे कम [v] == v (नीचे स्पष्टीकरण) । यदि इसका मतलब यह नहीं है कि वी एससीसी की जड़ नहीं है और अब हम माता-पिता के सबसे कम पहुंच योग्य पूर्वजों के माता-पिता को लाभ देते हैं [v] अब कम हो गया है [v]।

यह तार्किक लगता है, तो यद्यपि वहाँ माता पिता [V] वी के पूर्वज से कोई सीधा वापस किनारे है, लेकिन वहाँ एक रास्ता (V + v की ओर बढ़त के पीछे किनारे) जो माता पिता के माध्यम से है के रूप में [v] अभी भी v। के पूर्वजों तक पहुंच सकता है इस प्रकार हमने यहां निम्न [मूल [v]] को भी अपडेट किया है। इसलिए, हम इस श्रृंखला को अपडेट करना जारी रखेंगे और कम [v] सभी वी अपडेट होने तक जारी रहेगा, हम पूर्वजों तक पहुंचेंगे (बैकट्रैकिंग के माध्यम से)। इस पूर्वजों के लिए कम [v] v के बराबर होगा। और इस प्रकार यह एससीसी की जड़ के रूप में कार्य करेगा।

आशा है कि यह