C＃图遍历 [英] C# Graph Traversal

问题描述

  Dictionary< Node，bool>这个算法在遍历图中的节点方面做得很好。 visited = new Dictionary< Node，bool>（）; 
 
队列< Node> worklist = new Queue< Node>（）; 
 
 visited.Add（this，false）; 
 
 worklist.Enqueue（this）; $（b）
 $ b while（worklist.Count！= 0）
 {
 Node node = worklist.Dequeue（）; 
 $ b $ foreach（节点邻居在node.Neighbors中）
 {
 if（！visited.ContainsKey（neighbor））
 {
 visited.Add（neighbor ，假）; 
 worklist.Enqueue（neighbor）; 
} 
} 
} 
  

我可以用它来查找图中的目标节点。工作清单在处理工作清单时使项目出列（或弹出）。一旦找到目标，我该如何返回节点的完整路径？

更新
我想弄清楚如何反转到根的路径。该方法在根节点上调用，之后，子节点可能有两个父节点，所以它不像调用每个节点上的父节点属性那样简单并遍历备份。

该方法的目标是找到路径，而不是迭代所有节点，或检查节点是否存在。

解决方案

跟踪前驱节点。在最简单的实现中，这是一个字典，通常在伪代码中表示为π：

  Dictionary< Node，bool> visited = new Dictionary< Node，bool>（）; 
 Dictionary< Node，Node> π= new Dictionary< Node，Node>（）; 
 
队列< Node> worklist = new Queue< Node>（）; 
 
 visited.Add（this，false）; 
 
 worklist.Enqueue（this）; $（b）
 $ b while（worklist.Count！= 0）
 {
 Node node = worklist.Dequeue（）; 
 $ b $ foreach（节点邻居在node.Neighbors中）
 {
 if（！visited.ContainsKey（neighbor））
 {
 visited.Add（neighbor ，假）; 
π.Add（neighbor，node）; 
 worklist.Enqueue（neighbor）; 
 
 
 
 $ / code $ / pre 
 
然后你可以遍历这些先行者从任何节点回溯路径，例如 e ：
  while （π[e]！= null）{
 Console.WriteLine（e）; 
 e =π[e]; 
} 
  
 
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?  

Update
I 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.    
解决方案
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:
while (π[e] != null) {
    Console.WriteLine(e);
    e = π[e];
}


                        
这篇关于C＃图遍历的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！