एक डीएजी

Question

में हैमिल्टन पथ खोजने के लिए एल्गोरिदम मैं एल्गोरिदम पर स्कीएनना की पुस्तक का जिक्र कर रहा हूं।

परीक्षण की समस्या है कि क्या एक ग्राफ G एक Hamiltonian path शामिल NP-hard, जहां एक Hamiltonian पथ P एक रास्ता है कि प्रत्येक शिखर ठीक एक बार दौरा किया है। हैमिल्टनियन चक्र की समस्या के विपरीत, पी के प्रारंभिक चरम पर अंत में चरम से जी में किनारे नहीं होना चाहिए।

एक निर्देशित विश्वकोश ग्राफ जी (DAG) को देखते हुए, O(n + m) समय एल्गोरिदम दें ताकि परीक्षण किया जा सके कि इसमें हैमिल्टनियन पथ है या नहीं।

मेरे दृष्टिकोण,

मैं DFS और Topological sorting उपयोग करने के लिए योजना बना रहा हूँ। लेकिन मुझे नहीं पता था कि समस्या को हल करने में दो अवधारणाओं को कैसे जोड़ा जाए। समाधान निर्धारित करने के लिए एक स्थलीय प्रकार का उपयोग कैसे किया जा सकता है।

कोई सुझाव?

Answer 1

आप पहली बार ओ (एन + एम) में डीएजी (प्रत्येक डीएजी को टोपोलॉजिकल सॉर्ट किया जा सकता है) को क्रमबद्ध रूप से सॉर्ट कर सकते हैं।

एक बार यह हो जाने के बाद, आप जानते हैं कि किनारे निचले सूचकांक शिखर से उच्च तक जाते हैं। इसका मतलब है कि एक हैमिल्टनियन पथ मौजूद है यदि केवल और यदि लगातार शिखर के बीच किनारे हैं, उदा।

(1,2), (2,3), ..., (n-1,n). 

(इसका कारण यह है एक Hamiltonian पथ में आप नहीं "वापस जाएं 'कर सकते हैं और अभी तक आप सभी का दौरा करने के लिए है, तो एक ही तरीका है" को छोड़ नहीं "करने के लिए है)

आप इस जाँच कर सकते हैं ओ (एन) में हालत।

इस प्रकार, समग्र जटिलता ओ (एम + एन) है।

Answer 2

मुझे नहीं लगता कि @agassaa का बयान पूरी तरह से सही है। सरल उदाहरण पर विचार करें जहां तीन नोड्स "ए", "बी", "सी" हैं, और किनारों ए-> बी, बी-> सी, ए-> सी। जबकि ए में दो बच्चे हैं और सी में दो माता-पिता हैं, ए-> बी-> सी एक हैमिल्टनियन मार्ग बनाता है। हैमिल्टनियन होने के मार्ग के लिए आपको ग्राफ़ में हर किनारे को पार करने की आवश्यकता नहीं है।

A DAG that has Hamiltonian cycle