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