सी # ग्राफ ट्रैवर्सल

Question

यह एल्गोरिदम ग्राफ़ में नोड्स को घुमाने का एक अच्छा काम करता है।

Dictionary<Node, bool> visited = new Dictionary<Node, bool>(); 

Queue<Node> worklist = new Queue<Node>(); 

visited.Add(this, false); 

worklist.Enqueue(this); 

while (worklist.Count != 0) 
{ 
    Node node = worklist.Dequeue(); 

    foreach (Node neighbor in node.Neighbors) 
    { 
     if (!visited.ContainsKey(neighbor)) 
     { 
      visited.Add(neighbor, false); 
      worklist.Enqueue(neighbor); 
     } 
    } 
} 

मैं ग्राफ में लक्ष्य नोड खोजने के लिए इसका उपयोग कर सकता हूं। कार्यसूची को कार्यसूची के रूप में कार्यरत (या पॉप) आइटम को हटा दिया जाता है। एक बार जब मैं लक्ष्य प्राप्त कर लेता हूं तो मैं नोड को पूरा पथ कैसे वापस कर सकता हूं?

अद्यतन मैं यह समझने की कोशिश कर रहा हूं कि रूट के पथ को कैसे उलटया जाए। इस विधि को रूट नोड पर बुलाया जाता है, उसके बाद, बच्चों के दो माता-पिता हो सकते हैं, इसलिए यह प्रत्येक नोड पर मूल संपत्ति को कॉल करने और बैक अप लेने के समान आसान नहीं है।

विधि का लक्ष्य पथ खोजने के लिए है, सभी नोड्स को फिर से नहीं, या यह जांचने के लिए कि कोई नोड मौजूद है या नहीं।

Answer 1

पूर्ववर्ती नोड्स का ट्रैक रखें।सबसे आसान कार्यान्वयन में, यह एक शब्दकोश है, और आमतौर पर छद्म कोड में π के रूप में निरूपित:

Dictionary<Node, bool> visited = new Dictionary<Node, bool>(); 
Dictionary<Node, Node> π = new Dictionary<Node, Node>(); 

Queue<Node> worklist = new Queue<Node>(); 

visited.Add(this, false); 

worklist.Enqueue(this); 

while (worklist.Count != 0) 
{ 
    Node node = worklist.Dequeue(); 

    foreach (Node neighbor in node.Neighbors) 
    { 
     if (!visited.ContainsKey(neighbor)) 
     { 
      visited.Add(neighbor, false); 
      π.Add(neighbor, node); 
      worklist.Enqueue(neighbor); 
     } 
    } 
} 

तो फिर तुम किसी भी नोड से पथ पीछे इन पूर्ववर्तियों के माध्यम से पुनरावृति कर सकते हैं, का कहना है कि e:

while (π[e] != null) { 
    Console.WriteLine(e); 
    e = π[e]; 
} 

Answer 2

क्या यह "वर्तमान" है, यानी वर्तमान उदाहरण, ग्राफ की "रूट", यदि ऐसी कोई चीज़ है?

ग्राफ चक्रीय या विश्वकोश है? मुझे डर है कि मैं ग्राफ सिद्धांत के लिए सभी शर्तों को नहीं जानता।

A -> B -> C ------> F 
    B -> D -> E -> F 

यहाँ मेरी सवाल कर रहे हैं:

• यह घटित होगा

  यहाँ क्या मैं वास्तव में के बारे में चिंता है?

• क्या आपके कोड में "यह" कभी भी बी से शुरू हो सकता है?
• एफ का मार्ग क्या होगा?

यदि ग्राफ विभाजित होने पर कभी भी एक साथ वापस नहीं जुड़ता है, इसमें चक्र नहीं होते हैं, और "यह" हमेशा ग्राफ़ की रूट/प्रारंभ होगी, एक साधारण शब्दकोश पथ को संभालेगा।

Dictionary<Node, Node> PreNodes = new Dictionary<Node, Node>(); 

प्रत्येक नोड पर जाते हैं वहां कुंजी के रूप में पड़ोसी नोड जोड़ने के लिए, और नोड के लिए

यह मूल्य के रूप में के एक पड़ोसी था। रिवर्स किए गए पथ को पाने के लिए बैकट्रैक करने के लिए, आपको लक्षित नोड खोजने के बाद, यह आपको अनुमति देगा।

दूसरे शब्दों में, ऊपर ग्राफ के लिए शब्दकोश, एक पूर्ण ट्रेवर्सल के बाद होगा:

B: A 
C: B 
D: B 
E: D 
F: C (or E, or both?) 

ई नोड के लिए पथ खोजने के लिए, पीछे:

E -> D -> B -> A 

कौन सा आपको पथ देता है:

A -> B -> D -> E 

Answer 3

चूंकि आप "वर्तमान" नोड के रास्ते को हर समय ट्रैक नहीं कर रहे हैं जब आपको लक्ष्य मिल गया है तो उसे बनाना होगा। यदि आपके नोड वर्ग में एक अभिभावक संपत्ति है तो आप पूर्ण पथ बनाने के लिए आसानी से पेड़ को पीछे हट सकते हैं।

Answer 4

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

Answer 5

मैं उपयोग इस स्निपेट की कोशिश की (मेरे कोड में कोने), स्रोत और भाग्य का उपयोग कर शिखर से वैकल्पिक रास्तों प्राप्त करने के लिए, लेकिन बस काम न ...

public String EncontrarMenorCaminho(Vertice o, Vertice d) 
     { 
      Dictionary<Vertice, bool> visited = new Dictionary<Vertice, bool>(); 
      Dictionary<Vertice, Vertice> previous = new Dictionary<Vertice, Vertice>(); 
      Queue<Vertice> worklist = new Queue<Vertice>(); 
      String operacao = "Registro de operações realizadas:\r\n\r\n"; 

      visited.Add(o, false); 
      worklist.Enqueue(o); 
      while (worklist.Count != 0) 
      { 
       Vertice v = worklist.Dequeue(); 
       foreach (Vertice neighbor in EncontrarVizinhos(v)) 
       { 
        if (!visited.ContainsKey(neighbor)) 
        { 
         visited.Add(neighbor, false); 
         previous.Add(neighbor, v); 
         worklist.Enqueue(neighbor); 
        } 
       } 
      } 

      if (previous.Count > 0) 
      { 
       for (int p = 0; p < previous.Count; p++) 
       { 
        Vertice v1 = previous.ElementAt(p).Key; 
        Vertice v2 = previous.ElementAt(p).Value; 
        EncontrarAresta(v1, v2).Selecionado = true; 
        EncontrarAresta(v2, v1).Selecionado = true; 
        operacao += v1.Info.ToString() + "x" + v2.Info.ToString() + "\r\n"; 
       } 
      } 

      List<Vertice> grupos = new List<Vertice>(); 

      foreach (Aresta a in ArestasSelecionadas()) 
      { 
       if (!grupos.Contains(a.Origem)) grupos.Add(a.Origem); 
      } 

      foreach (Vertice v in grupos) 
      { 
       int menorpeso = this.infinito; 
       foreach(Vertice vz in EncontrarVizinhos(v)) 
       { 
        Aresta tmp = EncontrarAresta(v,vz); 
        if (tmp.Selecionado == true && tmp.Peso < menorpeso) 
        { 
         menorpeso = tmp.Peso; 
        } 
        else 
        { 
         tmp.Selecionado = false; 
        } 
       } 

      } 




      DesenharMapa(); 

      return operacao; 

मूल रूप से संचालन सभी चिह्नित हो जाता है

एक पूर्वावलोकन छवि देखें: किनारों (Selecionado = सच) और पुनः सत्यापन यदि आवश्यक हो तो जारी चयनित है ...

इस नमूने में, मैं vertext शीर्ष करने के लिए 'एन' 'क्यू' से कम से कम पथ मिल चाहते हैं यहां: