Depth-first recursive search in a tree

Graph and tree nodes can be traversed using the backtracking technique. Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. DFS takes less memory compare than Breadth-first search and not necessary to store all of the child pointers at each level.

DFS technique used in web-crawling, Finding connected components, Topological sorting, Finding the bridges of a graph, Finding strongly connected components, Solving puzzles with only one solution, such as mazes, maze generation may use a randomized depth-first search, Finding connectivity in graphs.

source Code

package com.dsacode.Algorithm.backtracking;
 
import java.util.Stack;
 
class Vertex{
    public char label;       
    public boolean wasVisited;
 
    public Vertex(char lab){
       label = lab;
       wasVisited = false;
       }
}
 
public class DepthFirstSearch {
      private final int MAX_VERTS = 20;
       private Vertex vertexList[];
       private int adjMat[][];     
       private int nVerts;         
       private Stack < Integer > theStack;
 
        
       public DepthFirstSearch() {
            
          vertexList = new Vertex[MAX_VERTS];
          adjMat = new int[MAX_VERTS][MAX_VERTS];
          nVerts = 0;
          for(int y = 0; y < MAX_VERTS; y++)     
             for(int x = 0; x < MAX_VERTS; x++)  
                adjMat[x][y] = 0;
          theStack = new Stack < Integer >();
          } 
 
       public void addVertex(char lab) {
          vertexList[nVerts++] = new Vertex(lab);
          }
 
       public void addEdge(int start, int end)   {
          adjMat[start][end] = 1;
          adjMat[end][start] = 1;
          }
 
       public void displayVertex(int v) {
          System.out.print(vertexList[v].label+"->");
          }
        
       public void dfs() {
          vertexList[0].wasVisited = true; 
          displayVertex(0);                
          theStack.push(0);                
 
          while( !theStack.isEmpty() ) {
             int v = getAdjUnvisitedVertex( theStack.peek() );
             if(v == -1)                   
                theStack.pop();
             else {
                vertexList[v].wasVisited = true; 
                displayVertex(v);                
                theStack.push(v);                
                }
             } 
 
 
          for(int j=0; j < nVerts; j++)         
             vertexList[j].wasVisited = false;
          } 
 
       public int getAdjUnvisitedVertex(Integer v) {
          for(int j=0; j < nVerts; j++)
             if(adjMat[v][j]==1 && vertexList[j].wasVisited==false)
                return j;
          return -1;
          } 
 
        public static void main(String[] args) {
            DepthFirstSearch theGraph = new DepthFirstSearch();
            theGraph.addVertex('A');   
            theGraph.addVertex('B');   
            theGraph.addVertex('C');   
            theGraph.addVertex('D');   
            theGraph.addVertex('E');   
 
            theGraph.addEdge(0, 1);    
            theGraph.addEdge(1, 2);    
            theGraph.addEdge(0, 3);    
            theGraph.addEdge(3, 4);    
 
            System.out.print("Visits from source to destination using DFS: ");
            theGraph.dfs();           
            System.out.println();
        }
 
}

Output

Visits from source to destination using DFS: A->B->C->D->E

Algorithm Explanation

	Use a stack to store vertex.
	Graphs may contain cycles, to avoid processing a node more than once use a Boolean visited array.
	Pop each element from the stack. peek the element from the stack and find all vertexes.
	If v is -1 pop the stack. otherwise, mark as visited node and push to the stack. Repeat the above steps for all the vertex.

Reference

1. https://en.wikipedia.org/wiki/Depth-first_search
2. https://en.wikipedia.org/wiki/Tree_traversal
3. http://www.cs.yale.edu/homes/aspnes/pinewiki/DepthFirstSearch.html
4. https://www.cs.usfca.edu/~galles/visualization/DFS.html