In the previous post, we discussed Depth First Search and its implementation in Java. In this post, we learn how to use Breadth First Search to find whether there exists a path between two vertices in a graph.
Again for this post also, we will create a graph for a directed unweighted graph as an adjacency list using the concepts discussed in this previous post. Then apply BFS on it.
How does Breadth First Search (BFS) work?
We have source node and a destination node in a graph. Our motive is to find a path between them. So we call BFS on our source and destination. In DFS, we traverse from node to its child, then to its grandchild and so on. In BFS we go level by level. First, we go through the first node(first layer), then it’s children (second layer) followed by its grandchildren(third layer) and so on until we reach the destination or we have traversed every node.
Here we first add the first node to a queue. Then check whether the first node in our queue is the destination. If yes, it returns true. Else remove the node from the queue. If the node is not in the visited set, add them to the visited set. Then we add the node’s children to our queue. Repeat the above process for every node in queue. If after traversing all nodes we don’t get a path, we return false.
Consider the graph in Fig 4. We have to find whether a path exists between A and H.
First, we check if start is destination ie A is a destination. It is not. So we move on to A’s children B and F and check them sequentially whether they are the destination (Orange Color). They are not, so we traverse B’s children followed by F’s children i.e., C, F (Green Color), and G(Yellow Color). Next we traverse C’s, F’s and G’s children. We continue in this way till we reach our destination node H.
Implementation
Now we code the above concept in Java. I will break down the code into few simple steps for ease in understanding
Step 1: Create a Node class, which stores the Node’s id of primitive type along with a LinkedList/ArrayList to store adjacency list of that node.
Step 2: Create a HashMap/ArrayList to store the vertices of a graph as Node objects. Here we can create a global variable to store graph or locally in methods and then pass them as parameters. Till now, we created a global variable for the graph, for the next two videos we will create a graph in a method and pass it as parameters.
Step 3: Add all the edges into the graph by updating the adjacency list of source nodes.
Step 4: Write method to find whether a path exists between source and destination using BFS.
Now we go through each step in detail:
Step 1:
Create a Node class, which stores the Node id/name/label of primitive type along with a LinkedList/ArrayList to store adjacency list of that node. For a detailed explanation refer to this post.
/**
* Node --- class to store each vertex along with its adjacent vertices
*/
static class Node{
private String id;
private LinkedList<Node> adjacent;
public Node(String id){
this.id = id;
adjacent = new LinkedList<Node>();
}
//Getter method for start vertex
public String getId(){
return id;
}
//Getter method for end vertex
public LinkedList<Node> getAdjacent(){
return adjacent;
}
//add node to the adajcent list
public void addAdjacent(Node vertex){
adjacent.add(vertex);
}
//To print Node
public String toString(){
String msg = id + " : ";
for(Node node: adjacent)
msg = msg + node.id + " ";
return msg;
}
}
Step 2:
Create a HashMap/ArrayList to store the vertices of a graph as Node objects.
In our example graph in Fig 1, we have string nodes. So our HashMap will have keys of type String and Values of type Node.
/**
* Creates a HashMap with string key and Node value
* @param input list of edges
* @return HashMap<String,Node>
*/
public static HashMap<String, Node> createGraph(String[] input){
HashMap<String, Node> graph = new HashMap<String, Node>();
Node node;
for(String s: input){
String first = String.valueOf(s.charAt(0));
String second = String.valueOf(s.charAt(1));
add(graph, first, second);
}
return graph;
}
Step 3:
Add all the edges into the graph by updating the adjacency list of source nodes.
Our input is an array of strings where each string “XY” represents an edge from X to Y. So we traverse our list and do the following three steps on each of the string values.
//Input edges of the graph.
{"AB","AE","BC","BF","CG","CD","EF","FG","GH","DH"};
Part 1: First we separate X and Y from our string “XY”. We can do that by using the String’s charAt(index) method and assign them to a first and second variable. Then add the edge to our graph by calling the add method.
public static void add(HashMap<String, Node> graph, String source, String destination){
//Get nodes corresponding to source and destination vertices.
Node s = getNode(graph, source);
Node d = getNode(graph, destination);
//add nodes to adjacent list
s.addAdjacent(d);
}
Part 2: We access the node corresponding to string X and Y in the graph. If there is no such node in our graph then we create one. This method getNode() does exactly that. It checks whether string K is present in our graph, if yes, then returns the corresponding node, else creates a new node with id K and adds it to our graph with key K.
private static Node getNode(HashMap<String, Node> graph, String id){
if(graph.containsKey(id))
return graph.get(id);
else{
Node node = new Node(id);
graph.put(id, node);
return node;
}
}
Part 3: Once we have both the nodes, we can add the destination node to source node’s adjacent list. Now our graph is created.
Step 4:
Write method to find whether a path exists between source and destination.
Here we need to traverse nodes in the order they come in. So we use a LinkedList queue of type Nodes. We add them as they come and always remove the first one in the list. To keep track of visited nodes, so that we don’t go inside an infinite loop, we use a HashSet visited.
We start by adding the first node to the queue. Then we loop over this queue until the queue becomes empty. Inside the loop, we remove the first node in the list. Then check whether the node is same as the destination. If yes, we return true. If no, we add the node to visited set if it has not been added. Next, we loop through the node’s adjacent list to add all its children to the queue. If we didn’t find destination even after traversing all nodes, we return false.
public static boolean pathExists(HashMap<String, Node> graph, String source, String destination){
//To store the children of nodes visited
LinkedList<Node> queue = new LinkedList<Node>();
//To store the visited nodes
HashSet<String> visited = new HashSet<String>();
//adding node of startId in the linkedlist
queue.add(getNode(graph, source));
while(!queue.isEmpty()){
Node parent = queue.remove();
//Check if current node is the destination node
if(parent.getId().equals(destination))
return true;
//add source to visited set
if(visited.contains(parent.getId()))
continue;
visited.add(parent.getId());
//add children to the queue
for(Node children: parent.getAdjacent())
queue.add(children);
}
return false;
}
Example
Consider the graph in Fig 1. We will apply the above BFS method on
- pathExists(graph, “A”, “H”)
- pathExists(graph, “H”, “D”)
1. pathExists(graph, “A”, “H”)
2. pathExists(graph, “H”, “D”)
The code for this post is available here.
Try BFS on a graph and experiment with different source and destination nodes. Drop your questions and thoughts in the comments below.
Thanks for stopping by. See you in the next post.