C# Graph Traversal

Question

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.

Answer 1

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