C＃圖形遍歷

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

是「this」，即當前實例，圖的「根」，如果有這樣的事情？

圖表是循環還是非循環？恐怕我不知道圖論的所有術語。

這就是我真正想知道：

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

這裏是我的問題：

• 會發生這種情況？
• 你的代碼中的「this」是否可以從B開始？
• F的路徑是什麼？

如果圖形在拆分時不再連接在一起，不包含循環，並且「this」將始終是圖形的根/起點，則簡單字典將處理該路徑。

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

對於您訪問的每個節點，添加相鄰節點作爲關鍵字，並將它作爲鄰居的節點作爲值。這樣，一旦找到目標節點，就可以回溯到反向路徑。

換句話說，在字典上圖，一個完整的穿越後會：

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

要查找路徑E-節點，只需回溯：

E -> D -> B -> A 

哪給你的路徑：

A -> B -> D -> E 

Answer 3

由於你沒有跟蹤任何時候「當前」節點的路徑，你會當你找到目標時必須建立這個目標。如果你的Node類有一個Parent屬性，你可以很容易地回溯到樹上來構建完整的路徑。

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; 

Basicly操作讓所有標記邊緣（Selecionado =真），如果沒有必要繼續選擇再次驗證...

在此示例中，我想從vertext「N」頂點「Q」獲得的最短路徑：

看到預覽圖像，這裏：