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 :
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.
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 :
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
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.
No comments:
Post a Comment