1. Artificial Intelligence
  2. BFS
    * We visit every vertex exactly once
    * We visit each neighbour vertex then the neighbours of these new vertices
    * Running time of the algorithm is O(V+E); V is no of vertices, E is no of edges
    * It has to store a lot of pointers so it is not as efficient as depth first search
    * It construct shortest path tree: Dijkstra shortest path algorithm does a BFS if all the edge weight are equal to 1

    Breadth First Search traversal is shown:

* In AI / machine learning it can prove to be very important: robots can discover the surrounding more easily with BFS than DFS
* It is also very important in maximum flow: the Edmonds-Karp maximum flow algoritm uses BFS for finding augmenting paths
* Cheyen’s algorithm in garbage collection: similar to mark and sweep gc procedure, it helps to maintain the active references -> it uses BFS to detect all the references on the heap memory

Codes of the Java files included in the program are given below:

Vertex.java

In [ ]:
package bfs;

import java.util.ArrayList;
import java.util.List;

/**
 *
 * @author ANIRUDDHA
 */
 
public class Vertex {
    
    private int data; //The data
    private boolean visited; //Visited vertices
    private List<Vertex> neighbourList; //List of all neighbours
    
    //Constructor
	public Vertex(int data){
        this.data = data;
        this.neighbourList = new ArrayList();
    }
    
    public void addNeighbour(Vertex vertex){
        this.neighbourList.add(vertex);
    }

	//Getters and Setters
    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public boolean isVisited() {
        return visited;
    }

    public void setVisited(boolean visited) {
        this.visited = visited;
    }

    public List<Vertex> getNeighbourList() {
        return neighbourList;
    }
    
	//Override the toString method to return the traversal path 
    public String toString(){
        return "-"+this.data;
    }
    
}

BFS.java

In [ ]:
package bfs;

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

/**
 *
 * @author ANIRUDDHA
 */

public class BFS {
    // BFS Algorithm
    public void bfsalgo(Vertex root){
        
        //We use a Queue data structure for BFS
		Queue<Vertex> queue = new LinkedList<>();
		//Polymorphism: LinkedList implements Queue data structure
        root.setVisited(true);
        queue.add(root);
    
        // Iterate until queue is empty
        while(!queue.isEmpty()){
            
            //Pop the actual vertices
            Vertex actualVertex = queue.remove();
            System.out.print(actualVertex+"-");
            
            //Visit all neighbours and add them to visited.
            for(Vertex v: actualVertex.getNeighbourList()){
                if(!v.isVisited()){
                    v.setVisited(true);
                    queue.add(v);
                }
            }
        }
    }
    
}

Main.java

In [ ]:
package bfs;

/**
 *
 * @author ANIRUDDHA
 */
public class Main {
    
    public static void main(String[] args){
        
        BFS bfs = new BFS();
        
        // Create vertices
        Vertex vertex1 = new Vertex(1);
        Vertex vertex2 = new Vertex(2);
        Vertex vertex3 = new Vertex(3);
        Vertex vertex4 = new Vertex(4);
        Vertex vertex5 = new Vertex(5);
        
        //Add neighbours to vertices
        vertex1.addNeighbour(vertex2);
        vertex1.addNeighbour(vertex4);
        vertex4.addNeighbour(vertex5);
        vertex2.addNeighbour(vertex3);
        
        // Start the BFS with the root as vertex1
        bfs.bfsalgo(vertex1);
        
        
    }
}

Output of the program is : 

-1--2--4--3--5-

You can download the complete source code here : Source Code