फ्लेरी के एल्गोरिदम की समय जटिलता

Question

क्या आप कृपया फ्लेरी 'एल्गोरिदम की समय जटिलता का पता लगाने में मदद कर सकते हैं (जिसे यूलेरियन सर्किट प्राप्त करने के लिए उपयोग किया जाता है)?

Answer 1

यहां: http://roticv.rantx.com/book/Eulerianpathandcircuit.pdf आप अन्य चीजों के साथ पढ़ सकते हैं, यह ओ (ई), रैखिक धार गणना है।

Answer 2

फ्लेरी का एल्गोरिदम वास्तव में तब तक पूरा नहीं होता जब तक आप यह निर्दिष्ट न करें कि पुल किनारों की पहचान कैसे की जाती है। तर्जन ने सभी पुलों की पहचान करने के लिए एक रैखिक-समय एल्गोरिदम दिया (http://en.wikipedia.org/wiki/Bridge_(graph_theory) देखें), इसलिए एक निष्पक्ष कार्यान्वयन जो प्रत्येक हटाए गए किनारे के बाद तारजन के एल्गोरिदम को फिर से चलाता है ओ (ई^2) होगा। पुलों के सेट को पुन: सम्मिलित करने के शायद बेहतर तरीके हैं, लेकिन एक बेहतर ओ (ई) एल्गोरिदम भी है। (http://www.algorithmist.com/index.php/Euler_tour#Fleury.27s_algorithm देखें; नहीं मेरी साइट :))

Answer 3

Fleury एल्गोरिथ्म निम्नलिखित चरण शामिल हैं:

1. यकीन ग्राफ या तो 0 या 2 अजीब कोने है बनाओ।

2. यदि 0 विषम शिखर हैं, तो कहीं भी शुरू करें। यदि 2 विषम शिखर हैं, तो उनमें से एक पर शुरू करें।

3. एक समय में किनारों का पालन करें। यदि आपके पास पुल और गैर-पुल के बीच कोई विकल्प है, तो हमेशा गैर-पुल चुनें।

4. जब आप किनारों से बाहर निकलते हैं तो रोकें।

पुलों Tarjan एल्गोरिथ्म द्वारा पता चला रहे हैं और इन पुलों एक निकटता मैट्रिक्स में जमा हो जाती है तो हम Tarjan एल्गोरिथ्म बढ़त एक पुल है या नहीं की जाँच करने के लिए हर बार चलाने की जरूरत नहीं है। हम इसे अन्य सभी पुल प्रश्नों के लिए ओ (1) समय में देख सकते हैं। इस प्रकार फ्लूरी की एल्गोरिदम समय जटिलता को ओ (वी + ई) में घटाया जा सकता है {क्योंकि यह एक डीएफएस} है लेकिन पुल को स्टोर करने के लिए इस विधि को ओ (वी 2) अतिरिक्त जगह की आवश्यकता है।