ग्राफ

Question

में 2 नोड्स के बीच के सभी पथ मुझे एक अनौपचारिक खोज (ब्रेडथ-फर्स्ट-सर्च) प्रोग्राम बनाना है जो दो नोड्स लेता है और उनके बीच के सभी पथ लौटाता है।

public void BFS(Nod start, Nod end) { 
      Queue<Nod> queue = new Queue<Nod>(); 
      queue.Enqueue(start); 
      while (queue.Count != 0) 
      { 
       Nod u = queue.Dequeue(); 
       if (u == end) break; 
       else 
       { 
        u.data = "Visited"; 
        foreach (Edge edge in u.getChildren()) 
        { 
         if (edge.getEnd().data == "") 
         { 
          edge.getEnd().data = "Visited"; 
          if (edge.getEnd() != end) 
          { 
           edge.getEnd().setParent(u); 
          } 
          else 
          { 
           edge.getEnd().setParent(u); 
           cost = 0; 
           PrintPath(edge.getEnd(), true); 
           edge.getEnd().data = ""; 
           //return; 
          } 
         } 
         queue.Enqueue(edge.getEnd()); 
        } 
       } 
      } 
     } 

मेरे समस्या यह है कि मैं केवल सब के बजाय दो रास्ते हो और मैं क्या मेरी कोड में संपादित करने के लिए उन सब को प्राप्त करने के लिए पता नहीं है है। मेरी समस्या का इनपुट इस मानचित्र पर आधारित है:

Answer 1

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

Answer 2

होमवर्क की तरह लगता है। लेकिन मजेदार तरह।

निम्नलिखित, स्यूडोकोड है गहराई सांस पहले (ताकि एक क़तार प्रकार एल्गोरिथ्म करने के लिए परिवर्तित किया जाना चाहिए के बजाय पहले है, और बग हो सकते हैं, लेकिन सामान्य jist स्पष्ट किया जाना चाहिए

class Node{ 
    Vector[Link] connections; 
    String name; 
} 

class Link{ 
    Node destination; 
    int distance; 
} 

Vector[Vector[Node]] paths(Node source, Node end_dest, Vector[Vector[Node]] routes){ 
    for each route in routes{ 
    bool has_next = false; 
    for each connection in source.connections{ 
     if !connection.destination in route { 
     has_next = true; 
     route.push(destination); 
     if (!connection.destination == end_dest){ 
      paths(destination, end_dest, routes); 
     } 
     } 
    } 
    if !has_next { 
     routes.remove(route) //watch out here, might mess up the iteration 
    } 
    } 
    return routes; 
} 

संपादित करें:। है यह वास्तव में उस प्रश्न का उत्तर है जिसे आप ढूंढ रहे हैं? या क्या आप वास्तव में सबसे छोटा रास्ता खोजना चाहते हैं? यदि यह बाद वाला है, तो डिज्कास्ट्रा के एल्गोरिदम का उपयोग करें: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Answer 3

ब्रेडथ पहली खोज सभी संभावित पथ उत्पन्न करने का एक अजीब तरीका है निम्न कारण: आपको ट्रैक रखने की आवश्यकता होगी कि प्रत्येक व्यक्तिगत पथ में क्या है बीएफएस ने नोड को पार किया था, न कि यह बिल्कुल पार हो गया था।

एक सरल उदाहरण

1----2 
\ \ 
    3--- 4----5 

ले लो हम, 2 और 3 1 से 5 के लिए सभी रास्ते चाहते हैं हम 1 अप कतार है, तो फिर 4, तो 5. हम इस तथ्य को खो दिया है देखते हैं कि दो 4 से 5 के माध्यम से पथ

मैं डीएफएस के साथ ऐसा करने का प्रयास करने का सुझाव दूंगा, हालांकि यह कुछ सोच के साथ बीएफएस के लिए तय किया जा सकता है। कतार वाली प्रत्येक चीज एक पथ होगी, न कि एक नोड, इसलिए कोई भी देख सकता है कि वह पथ प्रत्येक नोड का दौरा किया था या नहीं। यह अपर्याप्त स्मृति बुद्धिमान है, आप

Answer 4

एक पथ शिखर का अनुक्रम है जहां कोई वर्टेक्स एक से अधिक बार दोहराया नहीं जाता है। इस परिभाषा को देखते हुए, आप एक रिकर्सिव एल्गोरिदम लिख सकते हैं जो निम्नानुसार काम करेगा: फ़ंक्शन में चार पैरामीटर पास करें, इसे F(u, v, intermediate_list, no_of_vertices) पर कॉल करें, जहां u वर्तमान स्रोत है (जो हम रिकर्स करते हैं) में बदल जाएगा, v गंतव्य है, intermediate_list एक है उन शिखरों की सूची जो प्रारंभ में खाली होंगी, और हर बार जब हम वर्टेक्स का उपयोग करते हैं, तो हम इसे हमारे पथ में एक से अधिक बार एक कशेरुक का उपयोग करने से बचने के लिए सूची में जोड़ देंगे, और no_of_vertices उस पथ की लंबाई है जिसे हम करना चाहते हैं ढूंढें, जो 2 से कम हो जाएगा, और ऊपरी भाग V, कोने की संख्या से घिरा हुआ होगा। अनिवार्य रूप से, फ़ंक्शन उन पथों की एक सूची लौटाएगा जिनके स्रोत u हैं, गंतव्य v है, और प्रत्येक पथ की लंबाई no_of_vertices है। प्रारंभिक रिक्त सूची बनाएं और F(u, v, {}, 2), F(u, v, {}, 3), ..., F(u, v, {}, V) पर कॉल करें, प्रत्येक बार उस सूची के साथ F के आउटपुट को विलय कर दें जहां हम सभी पथों को स्टोर करना चाहते हैं। इसे लागू करने का प्रयास करें, और यदि आपको अभी भी परेशानी का सामना करना पड़ता है, तो मैं आपके लिए छद्म कोड लिखूंगा।

संपादित करें: बीएफएस का उपयोग कर उपर्युक्त समस्या को हल करना: ब्रेड पहली खोज एक एल्गोरिदम है जिसे ग्राफ के सभी राज्यों का पता लगाने के लिए उपयोग किया जा सकता है। आप बीएफएस का उपयोग करके दिए गए ग्राफ के सभी पथों के ग्राफ का पता लगा सकते हैं, और इच्छित पथों का चयन कर सकते हैं। प्रत्येक vertex v के लिए, निम्नलिखित राज्यों को कतार में जोड़ें: (v, {v}, {v}), जहां प्रत्येक राज्य को परिभाषित किया गया है: (current_vertex, list_of_vertices_already_visited, current_path)।अब, जबकि कतार खाली नहीं है, कतार में शीर्ष तत्व बंद पॉप, में से प्रत्येक के किनारे e के लिए, अगर पूंछ शिखर x पहले से ही list_of_vertices_already_visited में मौजूद नहीं है, कतार में नए राज्य (x, list_of_vertices_already_visited + {x}, current_path -> x) धक्का, और जब आप इसे कतार से पॉप करते हैं तो प्रत्येक पथ को संसाधित करें। इस तरह आप ग्राफ़ के लिए पथ के पूरे ग्राफ को खोज सकते हैं, चाहे निर्देशित हों या अप्रत्यक्ष हों।