CODEWITHSUNDEEP
javatraversaldepth-first-search
Raging Java
Raging Java

Reputation: 49

Implementing depth-first graph traversal

I have conflicting information about depth first traversal and could use some help in understanding how to build a program. Given a certain graph, I want to print a sequence of vertices. The user will input a particular node to start the traversal from. I am looking at different examples and I don't understand how the order of the depth-first traversal works. I have the following pseudocode to work with:

public DFS() {
    DFS(v)
    {   num(v) = i ++;
       for all vertices u adjacent to v
       { if num(u) is 0
            attach edge(uv) to edges;
            DFS(u);
        }
    }



depthFirstSearch()
{     for all vertices v
        num(v) = 0;
  edges = null; //vector of all edges
  i=1;
  while there is a vertex v such that num(v) is 0
         DFS(v);
  output edges;
}

Upvotes: 3

Views: 2090

Answers (1)

Carlos Daniel Gadea Omelchenko
Carlos Daniel Gadea Omelchenko

Reputation: 621

The key to both of these snippets are the following idea:

check if item found at (v)
if item not found,
   for all vertices u adjacent to v
     depth_first_search(u)

Instead of checking for the end condition at all the node's (v) children (list of u's) right away, you only check for it at the current node v. If the end condition is not met, you apply the same depth first search function starting with the first child of v, u1. Since u1 might also have children, the exact same function will be applied to u1's children before the remainder of v's children are processed, and so on. This is why it is called a depth first search, since your search will first search to the lowest possible set of children in a path before coming back to check the remaining children.

Upvotes: 2

Related Questions