हैलो, मैं यह पता लगाने की कोशिश कर रहा हूं कि इस समस्या को कैसे हल किया जाए।
आपको एक अप्रत्यक्ष ग्राफ G दिया जाता है, आप स्रोत s से शुरू करते हैं। और लक्ष्य यह है कि एक ही किनारे को दो बार कवर न करते हुए कुछ कोने तक जाएं और एक लूप में वापस आएं।
ध्यान दें कि यह संभव है कि ऐसा कोई लूप मौजूद न हो। तो हम सबसे छोटा चक्र कैसे खोजते हैं जिसमें मूल शामिल है?
उदाहरण के लिए
s-----o
| \ |
| \ |
| \ |
o----\o
सबसे छोटा चक्र या तो ऊपरी त्रिभुज होगा या निचला त्रिभुज
मुझे लगता है कि बीएफएस के साथ इसे हल करने का एक तरीका है। लेकिन मुझे यकीन नहीं है कि आप चक्र का मार्ग कैसे ढूंढते हैं?
1 उत्तर
इसे आज़माएं, जब आप बीएफएस शुरू करते हैं तो सभी नोड्स ओह डेप्थ 1 (मूल बच्चे) को एक अलग आईडी (जैसे। 0, 1, 2, ... आदि) के साथ चिह्नित करते हैं, तो उसके बाद आने वाले सभी नोड्स में उसकी मूल आईडी होगी। जैसा कि एल्गोरिथ्म चलता है, आपको यह जांचना होगा कि क्या अलग-अलग आईडी वाले दो नोड्स जुड़े हुए हैं, पहली बार ऐसा होने पर आपको सबसे छोटा चक्र दिखाई देगा जिसमें मूल (जो कि किनारे है जो अलग-अलग आईडी के उन दो नोड्स को जोड़ता है (उन्हें नाम दें v1 और v2) प्लस v1 से मूल तक के सभी पथ और v2 से मूल तक के सभी पथ)
उदा. मान लीजिए कि आप इस ग्राफ में एल्गोरिथम चला रहे हैं:
S ----- v1 ----- v2
| | |
v3 ---- v4 ----- v5
- सबसे पहले आप मूल स्थान से शुरू करें
S - फिर सभी
sबच्चे (v1औरv3) को कतार में जोड़ दिया जाता है (इस पल में आप उनकी आईडी असाइन करते हैं)। इस मामले में मान लेते हैंv1.id = 0औरv2.id = 1। - अब आप
Sको हटा दें औरv1कोcurrentके रूप में लें v1में टो बच्चे हैं ताकि आप उन्हें कतार में जोड़ दें (और उन्हें वही आईडी दें जो वे माता-पिता:v2.id = current.idऔरv4.id = current.id)- अब आप
v1को हटा दें और कतार में newx नोड लें जोv3currentके रूप में है v3के दो बच्चे हैं, उनमें से एक मूल है जो एक विशेष मामला है, और दूसराv4है। लेकिनv4को पहले ही देखा जा चुका है और इसकी आईडीv3से अलग है (यहाँ एल्गोरिथम रुक जाता है क्योंकि आपको वह चक्र मिल गया है:S - v1 - v4 - v3 - S
संबंधित सवाल
नए सवाल
algorithm
एक एल्गोरिथ्म अच्छी तरह से परिभाषित चरणों का एक क्रम है जो एक समस्या के सार समाधान को परिभाषित करता है। जब आपकी समस्या एल्गोरिथम डिज़ाइन से संबंधित हो तो इस टैग का उपयोग करें।