Breadth First Search

In this you visit each layer of node Horizontally and then visit to each child node horizontally and then next child node Horizontally and so on .

What's the Buzz !! 

This comes to rescue when looking out for shortest path ( weighted or unweighted Graph).

Understanding through an example 


Consider above Directed Graph where we have nodes from 1 to 9, 9 nodes & 12 edges.

Let's consider each edge has a weight of 6. 
Let's try to find out minimal distance of each node from a starting node (starting node can be an input).

Inputs:
<<No of Nodes >>  <<No of Edges>>

<<Edge1NodeStart>> <<Edge1NodeEnd>>
<<Edge2NodeStart>> <<Edge2NodeEnd>>
.....
.....
<<EdgeNNodeStart>> <<EdgeNNodeEnd>>
<<StartNode>>
<<Edge_Weight>>

For example , for above graph , input would be :
9 12 
1 2
2 3
4 5
5 6
7 8
8 9
1 4
2 5
3 6
4 7
5 8
6 9
1
6

Explanation : 9 12 are no of nodes & edges respectively. 
After that we have 12 lines for 12 edges, see graph above.
We have specified 1 as starting node and 6 as weight of each node.

Let's write Code :


public class BfsSolution {

private static final Scanner scanner = new Scanner(System.in);

public static void main(String[] args) throws IOException {

scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

String[] nm = scanner.nextLine().split(" ");

int n = Integer.parseInt(nm[0]);

int m = Integer.parseInt(nm[1]);

int[][] edges = new int[m][2];

for (int i = 0; i < m; i++) {
String[] edgesRowItems = scanner.nextLine().split(" ");
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

for (int j = 0; j < 2; j++) {
int edgesItem = Integer.parseInt(edgesRowItems[j]);
edges[i][j] = edgesItem;
}
}

int s = scanner.nextInt();

int weight = scanner.nextInt();

Map<Integer, Integer> result = bfs(n, m, edges, s, weight);
result.forEach(
(key, value) -> System.out.println(" Distance of Node " + key + " from  Node " + s + " is " + value));
scanner.close();

}

static Map<Integer, Integer> bfs(int n, int m, int[][] edges, int s, int weight) {

Map<Integer, Integer> distanceFromRoot = new TreeMap<Integer, Integer>();
distanceFromRoot.put(s, 0);
boolean[] visited = new boolean[n];
execute(n, m, edges, s, distanceFromRoot, visited, weight);
return distanceFromRoot;
}

static void execute(int n, int m, int[][] edges, int s, Map<Integer, Integer> distanceFromRoot, boolean[] visited,
int weight) {
Queue<Integer> queue = new LinkedList<Integer>();
queue.add(s);
visited[s - 1] = true;
while (queue.peek() != null) {
Integer nextElement = queue.poll();
for (int i = 0; i < m; i++) {
if (edges[i][0] == nextElement && !visited[edges[i][1] - 1]) {
Integer distance = distanceFromRoot.get(edges[i][0]) + weight;
distanceFromRoot.put(edges[i][1], distance);
queue.add(edges[i][1]);
visited[edges[i][1] - 1] = true;
} else if (edges[i][1] == nextElement && !visited[edges[i][0] - 1]) {
Integer distance = distanceFromRoot.get(edges[i][1]) + weight;
distanceFromRoot.put(edges[i][0], distance);
queue.add(edges[i][0]);
visited[edges[i][0] - 1] = true;
}
}
}

}

}
Output from Above Code :

 Distance of Node 1 from  Node 1 is 0

 Distance of Node 2 from  Node 1 is 6
 Distance of Node 3 from  Node 1 is 12
 Distance of Node 4 from  Node 1 is 6
 Distance of Node 5 from  Node 1 is 12
 Distance of Node 6 from  Node 1 is 18
 Distance of Node 7 from  Node 1 is 12
 Distance of Node 8 from  Node 1 is 18
 Distance of Node 9 from  Node 1 is 24

How can it help in finding shortest distance 

To understand that , let's modify our code to push minimum distance to distanceFromRoot.
For this , we are going to remove Visited flags array as we may have to visit the node from all the path :


public class BfsSolutionDiffWeigth {
private static final Scanner scanner = new Scanner(System.in);
public static void main(String[] args) throws IOException {
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
String[] nm = scanner.nextLine().split(" ");
int n = Integer.parseInt(nm[0]);
int m = Integer.parseInt(nm[1]);
int[][] edges = new int[m][3];
for (int i = 0; i < m; i++) {
String[] edgesRowItems = scanner.nextLine().split(" ");
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
for (int j = 0; j < 3; j++) {
int edgesItem = Integer.parseInt(edgesRowItems[j]);
edges[i][j] = edgesItem;
}
}
int s = scanner.nextInt();
Map<Integer, Integer> result = bfs(n, m, edges, s);
result.forEach(
(key, value) -> System.out.println(" Distance of Node " + key + " from  Node " + s + " is " + value));
scanner.close();
}
static Map<Integer, Integer> bfs(int n, int m, int[][] edges, int s) {
Map<Integer, Integer> distanceFromRoot = new TreeMap<Integer, Integer>();
distanceFromRoot.put(s, 0);
execute(n, m, edges, s, distanceFromRoot);
return distanceFromRoot;
}
static void execute(int n, int m, int[][] edges, int s, Map<Integer, Integer> distanceFromRoot) {
Queue<Integer> queue = new LinkedList<Integer>();
queue.add(s);
while (queue.peek() != null) {
Integer nextElement = queue.poll();
for (int i = 0; i < m; i++) {
if (edges[i][0] == nextElement) {
Integer distance = distanceFromRoot.get(edges[i][0]) + edges[i][2];
if (distanceFromRoot.get(edges[i][1]) == null || distanceFromRoot.get(edges[i][1]) > distance)
distanceFromRoot.put(edges[i][1], distance);
queue.add(edges[i][1]);
}
}
}
}

}

Input : 


9 12
1 2 6
2 3 6
4 5 6
5 6 6
7 8 6
8 9 6
1 4 1
2 5 6
3 6 6
4 7 6
5 8 6
6 9 6
1

Output : 

 Distance of Node 1 from  Node 1 is 0
 Distance of Node 2 from  Node 1 is 6
 Distance of Node 3 from  Node 1 is 12
 Distance of Node 4 from  Node 1 is 1
 Distance of Node 5 from  Node 1 is 7
 Distance of Node 6 from  Node 1 is 13
 Distance of Node 7 from  Node 1 is 7
 Distance of Node 8 from  Node 1 is 13
 Distance of Node 9 from  Node 1 is 19
Explanation :
As you can see, node 5 has two path 1->2->5 of distance 12 & 1->4->5 of distance 5 and this code correctly printed the shortest one.




Bug inAbove Code :

There is one bug in above code, can you identify?





Well! 
It assumes, it is uni-directed graph and not bi-directed.
Let's break the code by adding a edge that is bidirectional.
For example, let's add a edge from 5 to 4 ( we already have an edge from 4 to 5)

Input :
9 13
1 2 6
2 3 6
4 5 6
5 4 6
5 6 6
7 8 6
8 9 6
1 4 1
2 5 6
3 6 6
4 7 6
5 8 6
6 9 6
1
It loops indefinitely !!

Fix :

To fix this, we need to add visited flags but since we want to cover all paths, we will define visistededges instead of nodes.
VisitedEdges - A Set of Integer consisting of nodes
Set of <<Node1>><<Node2>>
Modified methods are :

static Map<Integer, Integer> bfs(int n, int m, int[][] edges, int s) {
Map<Integer, Integer> distanceFromRoot = new TreeMap<Integer, Integer>();
distanceFromRoot.put(s, 0);
Set<Integer> visitedEdges = new HashSet<>();
execute(n, m, edges, s, distanceFromRoot,visitedEdges);
return distanceFromRoot;
}
static void execute(int n, int m, int[][] edges, int s, Map<Integer, Integer> distanceFromRoot,Set<Integer> visitedEdges) {
Queue<Integer> queue = new LinkedList<Integer>();
queue.add(s);
while (queue.peek() != null) {
Integer nextElement = queue.poll();
for (int i = 0; i < m; i++) {
if (edges[i][0] == nextElement && !visitedEdges.contains(Integer.valueOf(String.valueOf(edges[i][0]) + String.valueOf(edges[i][1])))) {
Integer distance = distanceFromRoot.get(edges[i][0]) + edges[i][2];
if (distanceFromRoot.get(edges[i][1]) == null || distanceFromRoot.get(edges[i][1]) > distance)
distanceFromRoot.put(edges[i][1], distance);
queue.add(edges[i][1]);
visitedEdges.add(Integer.valueOf(String.valueOf(edges[i][0]) + String.valueOf(edges[i][1])));
}
}
}
}
Now execute again !

Input :

13
1 2 6
2 3 6
4 5 6
5 4 6
5 6 6
7 8 6
8 9 6
1 4 1
2 5 6
3 6 6
4 7 6
5 8 6
6 9 6

1
Output :

 Distance of Node 1 from  Node 1 is 0
 Distance of Node 2 from  Node 1 is 6
 Distance of Node 3 from  Node 1 is 12
 Distance of Node 4 from  Node 1 is 1
 Distance of Node 5 from  Node 1 is 7
 Distance of Node 6 from  Node 1 is 13
 Distance of Node 7 from  Node 1 is 7
 Distance of Node 8 from  Node 1 is 13
 Distance of Node 9 from  Node 1 is 19
Before we close, let's give it another angle, let's try to build an algorithm which calculates shortest distance between 2 nodes.
The main method will now accept an additional input , destination node d.
We will not change anything in actual logic , we will just print what we wanted. 
Here are the changes in main method :

public static void main(String[] args) throws IOException {
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
String[] nm = scanner.nextLine().split(" ");
int n = Integer.parseInt(nm[0]);
int m = Integer.parseInt(nm[1]);
int[][] edges = new int[m][3];
for (int i = 0; i < m; i++) {
String[] edgesRowItems = scanner.nextLine().split(" ");
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
for (int j = 0; j < 3; j++) {
int edgesItem = Integer.parseInt(edgesRowItems[j]);
edges[i][j] = edgesItem;
}
}
int s = scanner.nextInt();
int d = scanner.nextInt();
Map<Integer, Integer> result = bfs(n, m, edges, s);
System.out.println(" Distance of Node " + d + " from  Node " + s + " is " + result.get(d));
scanner.close();
}
Hope you enjoyed the journey of BFS !!
If you have any suggestions, why wait? Hit the Keyboard.
Code can be found at Github.