C# 图遍历
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/615202/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
C# Graph Traversal
提问by blu
This algorithm does a great job of traversing the nodes in a graph.
该算法在遍历图中的节点方面做得很好。
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);
}
}
}
I can use this to find a target node in the graph. The worklist dequeues (or pops) the items as the worklist is processed. Once I find the target how can I return the full path to the node?
我可以使用它来查找图中的目标节点。工作列表在处理工作列表时出列（或弹出）项目。一旦找到目标，如何返回节点的完整路径？
UpdateI am trying to figure out how to reverse the path to the root. The method is called on the root node, after that, children may have two parents, so it isn't as simple as calling the parent property on each node and traversing back up.
更新我试图弄清楚如何反转到根的路径。在根节点上调用该方法，之后子节点可能有两个父节点，所以不是在每个节点上调用父节点属性并向上遍历那么简单。
The goal of the method is to find the path, not to iterate all nodes, or to check if a node does exist.
该方法的目标是找到路径，而不是迭代所有节点，或者检查节点是否确实存在。
采纳答案by Konrad Rudolph
Keep track of the predecessor nodes. In the easiest implementation, this is a dictionary, and usually denoted as π in pseudo-codes:
跟踪前驱节点。在最简单的实现中，这是一个字典，通常在伪代码中表示为 π：
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);
}
}
}
Then you can iterate through these predecessors to backtrack the path from any node, say e:
然后您可以遍历这些前辈以从任何节点回溯路径，例如e：
while (π[e] != null) {
Console.WriteLine(e);
e = π[e];
}
回答by Lasse V. Karlsen
Is "this", that is, the current instance, the "root" of the graph, if there is such a thing?
“这个”，即当前实例，是图的“根”，如果有这样的东西？
Is the graph cyclic or acyclic? I'm afraid I don't know all the terms for graph theory.
图是循环的还是非循环的？恐怕我不知道图论的所有术语。
Here's what I really wonder about:
这是我真正想知道的：
A -> B -> C ------> F
B -> D -> E -> F
Here are my questions:
以下是我的问题：
- Will this occur?
- Can "this" in your code ever start at B?
- What will the path to F be?
- 这会发生吗？
- 代码中的“this”可以从 B 开始吗？
- 通向 F 的路径是什么？
If the graph never joins back together when it has split up, doesn't contain cycles, and "this" will always be the root/start of the graph, a simple dictionary will handle the path.
如果图在分裂时永远不会重新连接在一起，不包含循环，并且“this”将始终是图的根/起点，则一个简单的字典将处理路径。
Dictionary<Node, Node> PreNodes = new Dictionary<Node, Node>();
for each node you visit, add the neighbouring node as key, and the node it was a neighbour of as the value. This will allow you to, once you've find the target node, to backtrack back to get the reversed path.
对于您访问的每个节点，将相邻节点添加为键，并将其作为邻居的节点添加为值。这将允许您在找到目标节点后回溯以获取反向路径。
In other words, the dictionary for the graph above, after a full traversal would be:
换句话说，在完全遍历之后，上图的字典将是：
B: A
C: B
D: B
E: D
F: C (or E, or both?)
To find the path to the E-node, simply backtrack:
要找到 E 节点的路径，只需回溯：
E -> D -> B -> A
Which gives you the path:
这为您提供了路径：
A -> B -> D -> E
回答by Peter Lillevold
Since you're not tracking the path to the "current" node at all times you will have to construct that when you have found the target. If your Node class have a Parent property you could easily backtrack up the tree to construct the full path.
由于您不会一直跟踪“当前”节点的路径，因此您必须在找到目标时构建它。如果您的 Node 类具有 Parent 属性，您可以轻松地回溯树以构建完整路径。
回答by Jason Punyon
Peter is almost correct. I don't think you can store a link to the parent vertex in the node class, because it changes depending on the vertex at which you start your breadth first search. You need to create a Parent Dictionary with the keys being nodes and the values being parent nodes. As you visit each vertex (but before processing) you add the parents to the dictionary. Then you can walk up the parent path back to the root vertex.
彼得几乎是正确的。我认为您不能在节点类中存储指向父顶点的链接，因为它会根据您开始广度优先搜索的顶点而变化。您需要创建一个父字典，键是节点，值是父节点。当您访问每个顶点时（但在处理之前），您将父母添加到字典中。然后你可以沿着父路径走回到根顶点。
回答by MCunha98
I tried use this snippet to get the alternative paths from to vertex (vertices in my code), using source and destiny, but simply dont work...
我尝试使用这个片段来获取从到顶点（我代码中的顶点）的替代路径，使用源和命运，但根本不起作用......
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 the operation is get all marked edges (Selecionado = true) and verify again if is necessary continue selected...
基本上操作是获取所有标记的边缘（Selecionado = true）并再次验证是否有必要继续选择...
In this sample, I want get the shortest path from vertext 'N' to vertex 'Q':
在此示例中，我想获得从顶点“N”到顶点“Q”的最短路径：
See a preview image here:
在此处查看预览图像：
