Quick Expense Manger. Your free expense manager. Lots of features. The application is also ad free.

Generic Breadth First Search in Java

Posted on April 19, 2018
When I ask a candidate to code a Breadth First Search in Java, he does it using array of nodes and assuming that nodes are always integer. But when I go deeper and ask them to generalize the Graph where the nodes can be any object like Integer, String or any Custom object which is basically a Generic Graph and ask them to code the BFS for the same, they struggle a lot.

When I ask a candidate to code a Breadth First Search in Java, he does it using array of nodes and assuming that nodes are always integer. But when I go deeper and ask them to generalize the Graph where the nodes can be any object like Integer, String or any Custom object which is basically a Generic Graph and ask them to code the BFS for the same, they struggle a lot.


But basically it is the same question with the Generic twist. Here I would explain or basically give you the code for the Breadth First Search in a Generic Graph in Java.


The code is pretty self explanatory and if you find any difficulty in any step, please leave your queries in the comment section.


import java.util.*;

class Graph<T>{

class Node{
private T v;
private int layer;
private boolean marked;

private Node(T v){
this.v = v;
}

@Override
public int hashCode(){
return v.hashCode();
}

@Override
public boolean equals(Object object){
Node n = (Node )object;
return v.equals(n);
}
}

private int layer;
private Map<Node,List<Node>> adjList;
private Map<T,Node> nodeMap;
private Queue<Node> q = new LinkedList<Node>();

public Graph(){
adjList = new HashMap<Node,List<Node>>();
nodeMap = new HashMap<>();
}

private void addEdge(T u,T v){

Optional<T> key = nodeMap.keySet().stream().filter(n->n.equals(u)).findFirst();
if(!key.isPresent()){
nodeMap.put(u,new Node(u));
}

key = nodeMap.keySet().stream().filter(n->n.equals(v)).findFirst();
if(!key.isPresent()){
nodeMap.put(v,new Node(v));
}

Node uN = nodeMap.get(u);
Node vN = nodeMap.get(v);

if(adjList.get(uN)==null){
adjList.put(uN,new ArrayList<>());
}

if(adjList.get(vN)==null){
adjList.put(vN,new ArrayList<>());
}

adjList.get(nodeMap.get(u)).add(nodeMap.get(v));
adjList.get(nodeMap.get(v)).add(nodeMap.get(u));

}

public void bfs(T v){

layer = 0;
adjList.keySet().stream().forEach(k->{k.marked=false;k.layer=0;});

Node n = nodeMap.get(v);
n.layer = 0;
n.marked = true;
q.add(n);

internalBfs();
}

private void internalBfs(){
while(!q.isEmpty()){

while(!q.isEmpty() && q.peek().layer==layer){
Node n = q.remove();
adjList.get(n).stream().filter(v->!v.marked).forEach(v->{v.marked=true;
v.layer=layer+1;q.add(v);});

System.out.print(n.v + " ");
}
layer++;
System.out.println();
}
}

public static void main(String [] args){
Graph<String> G = new Graph<>();
G.addEdge("k","b");
G.addEdge("k","c");
G.addEdge("b","c");
G.addEdge("c","d");
G.bfs("d");
}
}

Sharing is Caring!

Quick Expense Manger. Your free expense manager. Lots of features. The application is also ad free.

GET FREE UPDATES


RECOMMENDED POSTS FOR YOU


profile image

Kaushik Baruah


ABOUT

My name is Kaushik Baruah and I am the chief blogger on this Blog. I have developed this Blog from scratch using Django as the backend and here I like to share my experience as software engineer and research engineer with my online readers. I will try to focus on career planning, latest emerging technologies and tutorials on various computer science subjects. You can follow me on Twitter, Facebook and Google+

GET FREE UPDATES

POPULAR POSTS

Copyright © 2018
About Us

My name is Kaushik Baruah and I am the chief blogger on this Blog. I have developed this Blog from scratch using Django as the backend and here I like to share my experience as software engineer and research engineer with my online readers. I will try to focus on career planning, latest emerging technologies and tutorials on various computer science subjects.

Get Free Updates