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];
}