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”获得的最短路径：

看到预览图像，这里：