Graph

Depth First Search

Pinterest LinkedIn Tumblr

Data structure Description

Depth First Search algorithm is an algorithm to search node from tree or graph. DFS algorithm starts traversing from the root. It traverses each branch before backtracking. DFS takes less memory compared than Breadth first search and not necessary to store all of the child pointers at each level.

The major drawback in depth-First Search is not guaranteed to find the solution. If it finds the solution, it may not be minimal solution.

Write a program to implement depth first search using the graph?

Algorithm Explanation

Build graph and pass to the utility function.
Create array of vertex, create a two-dimensional array of adjustment vertices. Create stack for storing visited nodes.
Display the vertex and push the root node to stack. Get adjustment unvisited vertices. If the there is no vertex, pop from the stack.
Otherwise, march node as visited and display the vertices. Add visited node to stack, and visited as false.
Display all the vertices from source to destination.

Source Code

package com.dsacode.DataStructre.graph;
 
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

1 Comment

  1. Hi Dear, are you really visiting this website regularly, if so afterward you will without doubt take pleasant knowledge.

Write A Comment