Graph search or finding whether one vertex is reachable from another vertex in a graph is one of the operations we can apply on graphs. There are two basic methods for this:
- Depth First Search
- Breadth First Search
In this post, we will study Depth First Search. We will create a graph for a directed unweighted graph as an adjacency list using the concepts discussed in this previous post. Then apply DFS on it.
What does reachability mean?
One vertex is reachable from another vertex if and only if there exists a path between them. For example in the directed graph given below, there exists a path between 1 and 6 but not between 3 and 4.
We can either go directly from node 1 to node 6 or go from node 1 to node 5 and then to node 6. The blue color highlights the path. And the gray color highlights the lack of path between 3 and 4 in the above graph.
How does Depth First Search (DFS) work?
We have source node and a destination node in a graph. Our motive is to find a path between them. So we call DFS on our source and destination. DFS then checks whether there is a path from any of the node’s children to the destination. If there is a path it returns true. Else it continues on the current node’s children until either we reach the destination (return true) or we reach a node already traversed ( return false).
The following example will clarify this more.
Fig 2 shows a directed unweighted graph along with adjacency list of each node. Suppose we want to find whether a path exists between 3 and 4. As per DFS, we check whether a path exists between 3’s child i.e. 6 and 4. Which further checks whether a path exists between 6’s child i.e. 2 and 4. This then checks whether a path exists between 2’s child i.e. 3 and 4. 3 is our node already traversed and so we return false. Let’s look at an example where a path exists.
Suppose we want to find whether a path exists between 1 and 6. Again, we start with 1’s child i.e 2 and call our method pathExists on 2 and 6. Then again we call method pathExists method on 2’s child i.e. 3 and 6 and then finally on 6 and 6 which returns true. This True goes all the way back to our first call and we return the final result ie True.
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 DFS.
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 4, 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.
String[] input = {"AB","BC","BE","CF","DE","EF"};
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.
We know that path exists between source and destination when the source becomes equal to the destination while traversing the graph. And we also know that if we encounter a node already visited while searching the destination then we don’t have a path between source and destination. So we need to keep track of the nodes visited so far. We do that using a HashSet visited.
We create an empty HashSet in our helper method and pass it and the source and the destination node to our main recursive method. We can get the nodes from the hashmap using getNode() method described above.
Once we are on a node, we check whether that node exists in our visited set. If it exists, we return false (no path between source and destination). If it doesn’t exist in visited, we add the node to the visited set.
Then we check whether the current node is equal to our destination. If yes, we have found a path, so we return true. Else we traverse the adjacent list of the current node and check if a path exists between its children and the destination node. If a path does exist we return true, else we return false.
/**
* Helper method for pathExists recursive method
* @param HashMap<String, Node> graph
* @param source start index
* @param destinations end index
* @return true or false
*/
public static boolean pathExists(HashMap<String, Node> graph, String source, String destination){
HashSet<Node> visited = new HashSet<Node>();
return pathExists(getNode(graph, source), getNode(graph, destination), visited);
}
/**
* pathExists recursive method to find path between source and destination
* @param source start index
* @param destinations end index
* @param visited set to store visited nodes
* @return true or false
*/
public static boolean pathExists(Node source, Node destination, HashSet<Node> visited){
if(visited.contains(source))
return false;
visited.add(source);
if(source == destination)
return true;
for(Node neighbor : source.getAdjacent()){
if(pathExists(neighbor, destination, visited))
return true;
}
return false;
}
Example
We see recursive calls on two examples for the graph in Fig 4.
- pathExists(graph, “A”, “F”)
- pathExists(graph, “A”, “D”)
The adjacency list of all nodes in the graph of Fig 4 is:
1. pathExists(graph, “A”, “F”)
2. pathExists(graph, “A”, “D”)
The code for this post is available here.
Try DFS 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.