एक निर्देशित ग्राफ जी = (वी, ई) में एक माई वर्टेक्स एक वर्टेक्स वी है जैसे कि अन्य सभी वर्टिसेस जी कोसे निर्देशित पथ से पहुंचा जा सकता है, यह जांचने के लिए ओ (एन + एम) एल्गोरिदम दें या नहीं जी में एक मातृभाषा है।ओ (एन + एम) में एक निर्देशित ग्राफ में मां vertex कैसे खोजें?
(ग) Skiena मैनुअल
से मिले केवल O (n (n + m)) जिस तरह से
जब googling मैं वास्तव में इस सवाल का जवाब here पाया। यदि यह होमवर्क है, तो आपको peeking से पहले दो बार सोचना चाहिए :)
मैंने समाधान देखा। मुझे नहीं लगता कि हमें एससीसी खोजने की जरूरत है। बस एक यादृच्छिक वर्टेक्स से एक डीएफएस करें और फिर अंतिम खत्म समय के साथ कशेरुक से डीएफएस करें। यदि कोई मां कशेरुक है तो यह होना चाहिए।
चरण 1। निर्देशित ग्राफ के शिखर के स्थलीय क्रमबद्ध करें।
चरण 2। अब यह देखना होगा कि हम 1.
एक चरण 2 करने के लिए, फिर से सरणी की खोज की [i] गलत पर प्रारंभ कदम में सांस्थितिकी अनुसार क्रमबद्ध कोने की पहली शिखर से सभी कोने तक पहुँचने और सांस्थितिकी के पहले नोड से startin DFS कर सकते हैं क्रमबद्ध शिखर।
यदि सभी शिखर तक पहुंचा जा सकता है, तो ग्राफ़ में मातृभाषा है, और मां वर्टेक्स टोपोलॉजिकल सॉर्ट किए गए शिखर के पूर्व होंगे।
समय जटिलता: step1 O(n + m) लेता है, चरण 2 O(n + m) तो कुल O(n+m) + O(n+m) = O(n+m)
एल्गोरिथ्म ::
क) क्या डीएफएस/BFS ग्राफ के और रखने के आखिरी समाप्त शिखर पर नज़र लेता है 'एक्स' ।
बी) यदि कोई मां वर्टेक्स मौजूद है, तो 'एक्स' उनमें से एक है। जांचें कि 'x' डीएफएस/बीएफएस वर्टेक्स 'एक्स' से कर रही है।
समय जटिलता O (n + m) + O (n + m) = ओ (n + m)
होगा निम्नलिखित ग्राफ के लिए इस काम है, अगर मैं बी से के रूप में यादृच्छिक शिखर शुरू? ए-> बी बी-> ए-> सी ए-> डी – learner