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-Breadth First Search Algorithm

Breadth First Search Algorithm with Adjacency List:

Breadth 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 Queue. 

2. Dequeue the vertex from queue 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 queue. Mark that vertex as      visited. 

4. Continue step 2 till queue is 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;
    }
}

Breadth First Search Class

import java.util.*;

public class BFS {

    public  static void main(String args[]){
        breadthFirstTraversal("E");
    }

    static void breadthFirstTraversal(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>();

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

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

Output with E as source vertex:
visted Vertex B
visted Vertex D
visted Vertex A
visted Vertex C


Advantages and Disadvantages of BFS