Advantages and disadvantages of DFS and BFS

Advantages of Breadth First Search:

1. Used to find the shortest path between vertices
2. Always finds optimal solutions.
3. There is nothing like useless path in BFS,since it searches level by level.
4. Finds the closest goal in less time

Disadvantages of BFS:

1. All of the connected vertices must be stored in memory. So consumes more memory

Advantages of Depth First Search:

1. Consumes less memory
2. Finds the larger distant element(from source vertex) in less time.

Disadvantages of BFS:

1. May not find optimal solution to the problem.
2. May get trapped in searching useless path.

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

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