How to implement Depth First Search on a directed graph to visit all vertices

1
votes

How do we perform depth first search on a directed graph using an adjacency matrix in which it explores all of the vertices starting from a random vertex? I attempted to implement dfs, but its only exploring the vertices that are reachable from the starting vertex.

      public static void dfs(int [] [] adjMatrix, int startingV,int n)
      {

      boolean [] visited = new boolean[n];
      Stack<Integer> s = new Stack<Integer>();

      s.push(startingV);

      while(!s.isEmpty())
      {
          int vertex = s.pop();
          if(visited[vertex]==false)
          {
              System.out.print("\n"+(v));
              visited[vertex]=true;
          }
          for ( int i = 0; i < n; i++)
          {
              if((adjMatrix[vertex][i] == true) && (visited[i] == false))
              {
                  s.push(vertex);
                  visited[I]=true;
                  System.out.print(" " + i);
                  vertex = i;
              }
          }
      }

} }

2
javaalgorithmgraphdepth-first-searchgraph-traversal
In your case simply iterating on your vertices can be an option, since they are represented by consecutive integers (for i from 1 to n). There may not exist a vertex from which all other vertices are reachable. – m.raynal
@m.raynal Yeah in that case it works, but what if you choose a random starting vertex? – user11082882
Then you can't know what's going to happen when you start a traversal. It might traverse all vertices in the graph, it might traverse only the starting vertex, or any number of vertices. So if you need to iterate on all your vertices in a directed graph, graph traversal is not an option, you need an array of vertices or something like that. – m.raynal
The only case where you will visit all vertices from any vertex is if your graph is strongly connected. – m.raynal
"Depth first" and "traversal" apply only to, well, traversing edges. If there is no edge to a certain node, then you can't traverse to that node. Hence it's not clear what you actually want to achieve. – JimmyB

2 Answers

1
votes

  1. In a directed graph there might be no node from which you can reach all other nodes. So what do you expect in this case?

  2. If there is at least one node from which you can reach all other nodes you only do now know which one it is, you can select a random one, go against the direction of an incoming edge to find a root node from which you can reach all other nodes.

1
votes

Your code has a couple of issues, one of which is that you do a int vertex = s.pop(); and later an s.push(vertex); with the same vertex. The latter should probably be s.push(i); instead.

The easiest way to implement DF traversal is to just use recursion. Then the code decays to

function dfs(v) {
  if v not visited before {
    mark v as visited;
    for every adjacent vertex a of v do {
      dfs(a);
    }
    do something with v; // this is *after* all descendants have been visited.
  }
}

Of course, every recursive implementation can be equivalently implemented using a stack and iteration instead, but in your case that'd be somewhat more complicated because you'd not only have to store the current vertex on the stack but also the state of iteration over its descendants (loop variable i in your case).