CODEWITHSUNDEEP
c#graphtraversal
blu
blu

Reputation: 13185

C# Graph Traversal

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.

Upvotes: 12

Views: 14215

Answers (4)

Konrad Rudolph
Konrad Rudolph

Reputation: 546025

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

Upvotes: 11

user6212
user6212

Reputation:

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.

Upvotes: 0

Peter Lillevold
Peter Lillevold

Reputation: 33940

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.

Upvotes: 0

Lasse V. Karlsen
Lasse V. Karlsen

Reputation: 391604

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?

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.

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 -> D -> B -> A

Which gives you the path:

A -> B -> D -> E

Upvotes: 0

Related Questions