हैलो, मैं यह पता लगाने की कोशिश कर रहा हूं कि इस समस्या को कैसे हल किया जाए।

आपको एक अप्रत्यक्ष ग्राफ G दिया जाता है, आप स्रोत s से शुरू करते हैं। और लक्ष्य यह है कि एक ही किनारे को दो बार कवर न करते हुए कुछ कोने तक जाएं और एक लूप में वापस आएं।

ध्यान दें कि यह संभव है कि ऐसा कोई लूप मौजूद न हो। तो हम सबसे छोटा चक्र कैसे खोजते हैं जिसमें मूल शामिल है?

उदाहरण के लिए

s-----o
| \   |
|  \  |
|   \ |
o----\o

सबसे छोटा चक्र या तो ऊपरी त्रिभुज होगा या निचला त्रिभुज

मुझे लगता है कि बीएफएस के साथ इसे हल करने का एक तरीका है। लेकिन मुझे यकीन नहीं है कि आप चक्र का मार्ग कैसे ढूंढते हैं?

1
scholcode 29 सितंबर 2020, 06:18

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 नोड लें जो v3 current के रूप में है
  • v3 के दो बच्चे हैं, उनमें से एक मूल है जो एक विशेष मामला है, और दूसरा v4 है। लेकिन v4 को पहले ही देखा जा चुका है और इसकी आईडी v3 से अलग है (यहाँ एल्गोरिथम रुक जाता है क्योंकि आपको वह चक्र मिल गया है: S - v1 - v4 - v3 - S
1
Jorge Morgado 29 सितंबर 2020, 07:49