Java Program to Traverse a Graph using BFS and DFS..

What is the difference between BFS and DFS?

• BFS Stands for “Breadth First Search”, where as DFS stands for “Depth First Search”.
• BFS starts traversal from the root node and then explore the search in the level by level manner i.e. as close as possible from the root node. DFS starts the traversal from the root node and explore the search as far as possible from the root node i.e. depth wise.
• Breadth First Search can be done with the help of queue i.e. FIFO implementation. Depth First Search can be done with the help of Stack i.e. LIFO implementations.
• BFS algorithm works in single stage. The visited vertices are removed from the queue and then displayed at once. DFS algorithm works in two stages – in the first stage the visited vertices are pushed onto the stack and later on when there is no vertex further to visit those are popped-off.
• BFS is slower than DFS
• BFS requires more memory compare to DFS.
  
  




• BFS is useful in finding shortest path.BFS can be used to find the shortest distance between some starting node and the remaining nodes of the graph. Where as    DFS in not so useful in finding shortest path. It is used to perform a traversal of a general graph and the idea of DFS is to make a path as long as possible, and then go back (backtrack) to add branches also as long as possible.

  

  Breadth First Search

  
  

  

  Depth First Search

Graphs, BFS,DFS, Dijkstra Algorithm, Bellman-Ford Algorithm

package com.graph;
public class GraphNode {    
/*Graph is a collection of linked nodes and values.
 *Each GraphNode has reference to each of its neighbouring nodes.
 *We also store reference of the node’s value and whether or not we’ve visited the node before.*/
    public GraphNode[] neighbours;
    public String val;
    public boolean visited;
    public GraphNode(String value) {
        this.val = value;
        this.visited = false;
    }
}

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class MainDriver {
    public static void main(String[] args) {
        GraphNode a = new GraphNode("a");
        GraphNode b = new GraphNode("b");
        GraphNode c = new GraphNode("c");
        GraphNode d = new GraphNode("d");
        GraphNode e = new GraphNode("e");
        GraphNode f = new GraphNode("f");
        a.neighbours=new GraphNode[] { b, c };
        b.neighbours=new GraphNode[] { a, d };
        d.neighbours=new GraphNode[] { b};       
        c.neighbours=new GraphNode[] { a, e, f };
        e.neighbours=new GraphNode[] { c};
        f.neighbours=new GraphNode[] { c };
        BFS(a);
        DFS(a);
    }
   
    /*
    STEPS:
    1). Create a new Java Queue of type GraphNode
    2). Mark our root GraphNode as discovered and print it out
    3). Add the root GraphNode into the Queue
    4). Loop through the Queue infinitely until it is empty
        4.1). Poll the head of the Queue for the GraphNode
        4.2). Loop through all GraphNode neighbours of the polled head
        4.3). If the neighbour has not been discovered, mark it as discovered and add it into the Queue
     */
    public static void BFS(GraphNode node) {       
        Queue queue = new LinkedList();
        node.visited = true;
        queue.add(node);   
        System.out.println(node.val);   
        while(!queue.isEmpty()) {
            GraphNode v = queue.poll();
            for(GraphNode w : v.neighbours) {
                if(!w.visited) {
                    System.out.println(w.val);
                    w.visited = true;
                    queue.add(w);
                }
            }
        }   
    }
   
    /*
     STEPS:
     1). Create a Java Stack and push the root node to it
     2). Loop until the GraphNode stack is empty
        2.1). Pop the top GraphNode off the stack
        2.2). If the node has not been visited, mark it so and loop through all GraphNode neighbours in reverse
            2.2.1). Push each neighbour into the stack
     * */
    public static void DFS(GraphNode node) {       
        Stack stack = new Stack();
        stack.push(node);   
        while(!stack.isEmpty()) {
            GraphNode v = stack.pop();
            if(!v.visited) {
                System.out.println(v.val);
                v.visited = true;
                for(int i = v.neighbours.length - 1; i >= 0; i--) {
                    stack.push(v.neighbours[i]);
                }
            }
        }   
    }
}