17 August 2017

Graph-Depth First Search Algorithm

Depth First Search Algorithm with Adjacency List:


Depth First Search algorithm is used to traverse the  Graph. 
We can find the solution with time complexity of O (V+E).
V is number of vertices
E is number of Edges

This algorithm can be used to find if there is an edge between two vertices.

Algorithm:

1. Visit the source Vertex. Mark it as visited and push it to Stack. 
2. Pop the vertex from stack and get all adjacent vertices. 
    For all vertices, do step 3. 
3. If a vertex is not visited then only visit that vertex and push it to stack. Mark that vertex as      visited. 
4. Continue step 2 till stackis empty.

Implementation in Java:

Graph data preparation with Adjacency List:

Class GraphData is the Graph with adjacency list.

package become.java9pro.graph;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

public class GraphData {
    private Map<String, LinkedList<String>> adj;

    GraphData(HashMap<String, LinkedList<String>> m) {
        adj = m;
    }

    public Map<String, LinkedList<String>> getAdj() {
        return adj;
    }
}




Depth First Search Class







Graph_DFS
















package become.java9pro.graph;

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Stack;

public class DFS {
    public  static void main(String args[]){
        depthFirstTraversal("E");
    }

    static void depthFirstTraversal(String source){

        HashMap<String,LinkedList<String>> map = new HashMap<String,LinkedList<String>>();
        map.put("A",new LinkedList<String>(){{add("B");add("C");}});
        map.put("B",new LinkedList<String>(){{add("A");add("B");add("D");}});
        map.put("C",new LinkedList<String>(){{add("A");add("E");}});
        map.put("D",new LinkedList<String>(){{add("C");add("E");;add("B");}});
        map.put("E",new LinkedList<String>(){{add("B");add("D");}});
        GraphData gd = new  GraphData(map);

        HashSet<String> visted = new HashSet<String>();

        Stack<String> stack = new Stack<String>();
        stack.push(source);

        visted.add(source);
        while(!stack.isEmpty()){
            String  next = stack.pop();
            for(String s: gd.getAdj().get(next)) {
                if (!visted.contains(s)) {
                    System.out.println("visted Vertex "+s);
                    stack.push(s);
                    visted.add(s);
                }
            }}
    }
}






Output with E as source vertex:

visted Vertex B
visted Vertex D
visted Vertex C
visted Vertex A



Advantages and Disadvantages of DFS












By



at