C＃图遍历

该算法在遍历图中的节点方面做得很好。

Dictionary visited = new Dictionary(); Queue worklist = new Queue(); 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 visited = new Dictionary(); Dictionary π = new Dictionary(); Queue worklist = new Queue(); 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

我尝试使用这个片段来获取替代路径从顶点（我的代码中的顶点），使用源和命运，但只是不工作…

 public String EncontrarMenorCaminho(Vertice o, Vertice d) { Dictionary visited = new Dictionary(); Dictionary previous = new Dictionary(); Queue worklist = new Queue(); 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 grupos = new List(); 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 = true）并再次validation是否必要继续选择...

在这个例子中，我想得到从vertext'N'到顶点'Q'的最短路径：

在此处查看预览图像：

Answer 3

是“这个”，即当前实例，图的“根”，如果有这样的事情？

图形是循环的还是非循环的？ 我担心我不知道图论的所有术语。

这就是我真正想知道的：

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

这是我的问题：

• 这会发生吗？
• 您的代码中的“this”可以从B开始吗？
• F的路径是什么？

如果图形在拆分时从不连接在一起，不包含循环，并且“this”将始终是图形的根/起点，则简单的字典将处理路径。

 Dictionary PreNodes = new Dictionary(); 

对于您访问的每个节点，将相邻节点添加为密钥，将其作为邻居的节点添加为值。 一旦找到目标节点，这将允许您回溯以获得反向路径。

换句话说，在完整遍历之后，上图的字典将是：

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

要查找E节点的路径，只需回溯：

 E -> D -> B -> A 

这给你的路径：

 A -> B -> D -> E 

Answer 4

由于您没有始终跟踪“当前”节点的路径，因此在找到目标时必须构建该路径。 如果您的Node类具有Parent属性，则可以轻松地回溯树以构建完整路径。

Answer 5

彼得几乎是正确的。 我不认为您可以在节点类中存储指向父顶点的链接，因为它会根据您开始广度优先搜索的顶点而更改。 您需要创建父词典，其中键是节点，值是父节点。 当您访问每个顶点时（但在处理之前），您将父项添加到字典中。 然后，您可以将父路径向上移回根顶点。