मुझे बीएफएस द्वारा प्राप्त वास्तविक पथ कैसे मिल सकता है?

Question

जिस समस्या को मैं हल करने की कोशिश कर रहा हूं वह एमआरटी प्रणाली के पेड़ से संबंधित है।

प्रत्येक नोड को अधिकतम 4 बिंदुओं से जोड़ा जा सकता है, जो बहुत से चीजों को सरल बनाते हैं। मेरा विचार यहाँ है।

struct stop { 
    int path, id; 
    stop* a; 
    stop* b; 
    stop* c; 
    stop* d; 
}; 

मैं सभी जानकारी BFS सभी बिंदुओं के लिए खोज करने के लिए की आवश्यकता को बचाने के लिए कोड लिख सकते हैं, लेकिन मेरी मुख्य चिंता यह है कि, भले ही BFS बिंदु ठीक से पाता है, मैं कैसे अपने रास्ते पता कर सकते हैं?

बीएफएस प्रत्येक स्तर की खोज करेगा, और जब यह मेरे गंतव्य तक पहुंच जाएगा, तो यह रन लूप से बाहर निकल जाएगा, और फिर, मुझे एक विज़िट कतार और एक अनदेखी कतार मिलेगी, मैं उपयोगकर्ता को कैसे बताना चाहता हूं बीएफएस की खोज की गई प्रत्येक नोड्स के साथ आने वाली कतार भरने पर उसे क्या रोकना पड़ता है?

Answer 1

ऐसा करने के लिए, आप एक map:V->V [कोने से कोने करने के लिए], जो प्रत्येक नोड v, शिखर u कि "खोजा" v से मैप कर देंगे स्टोर करने के लिए की जरूरत है।

आप इस मानचित्र को बीएफएस के पुनरावृत्तियों के दौरान पॉप्युलेट करेंगे।

बाद - आप बस लक्ष्य नोड [नक्शे में] से जा रहा द्वारा पथ को फिर से संगठित कर सकते हैं - जब तक आप स्रोत के लिए वापस पाने के लिए, और यह yor पथ [उलट, बेशक ...]

है

ध्यान दें कि यदि आप कोनेक्ट का आकलन करते हैं, तो यह मानचित्र सरणी के रूप में कार्यान्वित किया जा सकता है।