1. Artificial Intelligence
  2. DFS

* Depth first search is a widely used graph traversal algorithm
* It explores as far as possible along each branch before backtracking
* So it does not need pointers unlike BFS
* Thus it is memory friendly
* Time complexity of traversing a graph with DFS is O(V+E)
* It has several applications: Topological ordering or Kosaraju algorithm or detecting cycles (DAG)

Depth First Search traversal is shown:



Codes of the Java files included in the program are given below:

Vertex.java

In [ ]:
package dfs;
/**
 *
 * @author ANIRUDDHA
 */

import java.util.ArrayList;
import java.util.List;

public class Vertex {
    
    private String name; //The name of the vertex
    private boolean visited; //Visited vertices
    private List<Vertex> adjacenciesList; //List of all adjacent neighbours
    private Vertex predecessors; //List of previous vertex

	//Constructor
    public Vertex(String name){
        this.name = name;
        this.adjacenciesList = new ArrayList<Vertex>();
    }
    
    public void addNeighbour(Vertex vertex){
        this.adjacenciesList.add(vertex);
    }

	//Getters and Setters
    public boolean isVisited() {
        return visited;
    }

    public void setVisited(boolean visited) {
        this.visited = visited;
    }

    public List<Vertex> getAdjacenciesList() {
        return adjacenciesList;
    }

    public Vertex getPredecessors() {
        return predecessors;
    }

    public void setPredecessors(Vertex predecessors) {
        this.predecessors = predecessors;
    }

	//Override the toString method to return the traversal path 
    public String toString(){
        return this.name;
    }
}

DFS.java

In [ ]:
package dfs;

import java.util.Stack;

/**
 *
 * @author ANIRUDDHA
 */

// DFS algo using Stack
public class DFS {

	//We use the stack data structure for DFS to store the vertices
    private Stack<Vertex> stack;
    
    public DFS(){
        this.stack = new Stack<>();
    }
    
	// DFS Algorithm
    public void dfsalgo(Vertex root){
        
        stack.add(root);
        root.setVisited(true);
        
		// Iterate until stack is empty
        while(!stack.isEmpty()){
            
            //Pop the actual vertices for display
            Vertex actualVertex = stack.pop();
            System.out.print(actualVertex+"-");
            
            //Visit all neighbours and add them to visited.
            for(Vertex v: actualVertex.getAdjacenciesList()){
                if(!v.isVisited()){
                    v.setVisited(true);
                    v.setPredecessors(actualVertex);
                    stack.push(v);
                }
            }
        }
    }
	
	/*
	//Recursive DFS using the stack of your host Operating System
	public void dfsalgo(Vertex vertex){
		
		System.out.print(vertex+" ");
		
		for(Vertex v: vertex.getAdjacenciesList()){
			if(!v.isVisited()){
				v.setVisited(true);
				v.setPredecessors(vertex);
				dfs(v);
			}
		}
	}
	*/
}

Main.java

In [ ]:
package dfs;

/**
 *
 * @author ANIRUDDHA
 */
public class Main {

    public static void main(String[] args) {
        
        DFS dfs = new DFS();
        
        // Create vertices
        Vertex vertexA = new Vertex("A");
        Vertex vertexB = new Vertex("B");
        Vertex vertexC = new Vertex("C");
        Vertex vertexD = new Vertex("D");
        Vertex vertexE = new Vertex("E");
        
        //Add neighbours to vertices
        vertexA.addNeighbour(vertexB);
        vertexA.addNeighbour(vertexC);
        
        vertexB.addNeighbour(vertexD);
        vertexB.addNeighbour(vertexE);
        
        // Start the DFS with the root here vertex1
        dfs.dfsalgo(vertexA);
    }
    
}

Output of the program is : 

A-C-B-E-D-

You can download the complete source code here : Source Code