Graph traversal- Depth First Search & Breadth First Search
There are two (2) major ways of traversing a graph.
- Depth first traversal
- Breadth first traversal
Depth first traversal
This is a traversal technique whereby we start at the root node, traverse down the graph on one path till the leaf node of that path before backtracking to the root node to traverse the other neighbors in a similar fashion. Let’s explore this technique with the below tree. While traversing, we mark nodes as visited to avoid more than one visitation to a node.
Lets look at two(2) ways of implementing depth first traversal for the above graph.
- Iteratively
- Recursively
1.Iteratively
This is implemented using a stack and a visited tracker, for our case we use a set. To visualize this, let’s look at the adjacency list of the above graph which is as below.
The root of the above graph is i.
The processing
1.In the first iteration, push the root to the stack, pop it mark it as visited and print it to the console.Push its neighbors j and k to the stack.Iteration output=i
The stack is as below
2.Pop the stack.We get k since it was pushed last in step 1 and is at the top of the stack.Check if k has been visited before.If already visited,skip and pop the next element from the stack.If not,mark k as visited and print it to the console.Push its neighbors i ,m and l to the stack.Iteration output =i k
The stack is as below
3.Pop the stack.We get l since it was the last to be pushed onto the stack in step 2. Check if l has been visited before.If already visited,skip and pop the next element from the stack.If not mark l as visited and print it to the console.Push its neighbors k,p and q to the stack.Iteration output = i k l
The stack is as below
4.Pop the stack.We get q since it was the last to be pushed to the stack in step 3. Check if q has been visited before.If already visited,skip and pop the next element from the stack.If not mark q as visited and print it to the console.Push its neighbor l to the stack.Iteration output = i k l q
The stack is as below
5.Pop the stack.We get l since it was the last to be pushed to the stack in step 4.We check and see that l was visited before.We proceed to pop the next element p.We see that p has not been visited before,mark it as visited and print it to the console.Push its neighbor l to the stack.Iteration output = i k l q p
The stack is as below
6.Pop the stack.We get l since it was the last element to be pushed in step 5 above.We check and see that l was visited before.We continue and pop the next element from the stack and we get k.We check and also find that k was visited before.We proceed to pop the next element from the stack and we get m.m has not been visited below,we mark it as visited and print it to the console.We push its neighbors k and n to the stack. Iteration output = i k l q p m
The stack is as below
7.Pop the stack.We get n since is was the last element to be pushed to the stack in step 6.We check and see n has not been visited before.We then mark is as visited and print it to the console.We push its neighbors m and o to the stack,Iteration output = i k l q p m n
The stack is as below
8.Pop the stack .We get o since it was the last to be pushed to the stack.It has not been visited before.We now mark it as visited and print it to the console.We push its neighbor n to the stack.Iteration output= i k l q p m n o
The stack is as below
9.Pop the stack.We get n.n has been visited before,so we pop next element m.m has been visited before so we pop next element k.k has been visited before so we pop next element i.i has been visited before so we pop next element j.j has not been visited so we mark it as visited and print it to the console.We push its neighbor i to the stack.Iteration output = i k l q p m n o j
The stack is as below
10.Pop the stack.We get i.i has been visited before.We try to pop the next element from the stack,but it’s now empty.All nodes are now visited. And our results remains as in step 9 i.e. i k l q p m n o j
The below method implemented in Java shows the implementation of the above algorithm
private static void doDepthFirstSearchTraversalIteratively(Map<String, List<String>> adjList, String start, Set<String> visited) {
Stack stk = new Stack();
stk.push(start);
while (stk.size() > 0) {
String current = (String) stk.pop();
if (visited.contains(current)) {
continue;
}
visited.add(current);
System.out.print(" " + current);
for (String neighbor :adjList.get(current)) {
stk.push(neighbor);
}
}
System.out.println();
}
2.Recursively
This approach is similar to the above approach.It also utilizes uses a visited tracker but utilizes the call stack for recursion.
The below method implemented in Java shows recursive depth first traversal of a graph.
private static void doDepthFirstSearchTraversalRecursively(Map<String, List<String>> adjList, Set<String> visited, String current) {
if (visited.contains(current)) {
return;
}
visited.add(current);
System.out.print(" " + current);
for (String neighbor : adjList.get(current)) {
doDepthFirstSearchTraversalRecursively(adjList, visited, neighbor);
}
}
Full java program implementing depth first search traversal on a graph with code for iterative and recursive approaches
package graphs;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Stack;
public class UndirectedGraphTraversal {
public static void main(String... args) {
List<List<String>> undirectedGraph = new ArrayList<>();
ArrayList<String> edge0 = new ArrayList<>();
edge0.add("i");
edge0.add("j");
ArrayList<String> edge1 = new ArrayList<>();
edge1.add("k");
edge1.add("i");
ArrayList<String> edge2 = new ArrayList<>();
edge2.add("m");
edge2.add("k");
ArrayList<String> edge3 = new ArrayList<>();
edge3.add("k");
edge3.add("l");
ArrayList<String> edge4 = new ArrayList<>();
edge4.add("l");
edge4.add("p");
ArrayList<String> edge5 = new ArrayList<>();
edge5.add("l");
edge5.add("q");
ArrayList<String> edge6 = new ArrayList<>();
edge6.add("m");
edge6.add("n");
ArrayList<String> edge7 = new ArrayList<>();
edge7.add("n");
edge7.add("o");
undirectedGraph.add(edge0);
undirectedGraph.add(edge1);
undirectedGraph.add(edge2);
undirectedGraph.add(edge3);
undirectedGraph.add(edge4);
undirectedGraph.add(edge5);
undirectedGraph.add(edge6);
undirectedGraph.add(edge7);
System.out.println("------Undirected edge list-----");
System.out.println(undirectedGraph);
Map<String, List<String>> adjList = buildAdjacencyList(undirectedGraph);
System.out.println("-----Adjacency list-----");
adjList.keySet().stream().forEach(key -> {
System.out.println(key + ":" + adjList.get(key));
});
System.out.println("---Iterative approach---");
Set<String> visitedI = new HashSet<>();
doDepthFirstSearchTraversalIteratively(adjList, "i", visitedI);
Set<String> visitedR = new HashSet<>();
System.out.println("---Recursive approach---");
doDepthFirstSearchTraversalRecursively(adjList, visitedR, "i");
System.out.println();
}
private static Map<String, List<String>> buildAdjacencyList(List<List<String>> undirectedGraph) {
Map<String, List<String>> adjacencyList = new HashMap<>();
for (List<String> connection : undirectedGraph) {
String a = connection.get(0);
String b = connection.get(1);
if (!adjacencyList.containsKey(a)) {
adjacencyList.put(a, new ArrayList<>());
}
if (!adjacencyList.containsKey(b)) {
adjacencyList.put(b, new ArrayList<>());
}
adjacencyList.get(a).add(b);
adjacencyList.get(b).add(a);
}
return adjacencyList;
}
private static void doDepthFirstSearchTraversalIteratively(Map<String, List<String>> adjList, String start, Set<String> visited) {
Stack stk = new Stack();
stk.push(start);
while (stk.size() > 0) {
String current = (String) stk.pop();
if (visited.contains(current)) {
continue;
}
visited.add(current);
System.out.print(" " + current);
for (String neighbor :adjList.get(current)) {
stk.push(neighbor);
}
}
System.out.println();
}
private static void doDepthFirstSearchTraversalRecursively(Map<String, List<String>> adjList, Set<String> visited, String current) {
if (visited.contains(current)) {
return;
}
visited.add(current);
System.out.print(" " + current);
for (String neighbor : adjList.get(current)) {
doDepthFirstSearchTraversalRecursively(adjList, visited, neighbor);
}
}
}
Output of the above program
Explanation
The output of the iterative approach varies with that of the recursive approach. This is because of the order in which the nodes’ neighbors are positioned in the adjacency list hence influencing the order in which they are pushed into the stack. However, in both approaches only 1 path is chosen and travelled to the leaf node before backtracking to the root to visit the other neighbors in a similar fashion.
Breadth first traversal
In this technique, we start at the root node, mark it as visited then move to its neighbors. All the neighbors at the same level are visited before moving to the neighbors in the level below. This is made possible by use of a queue.In a queue,elements are added to the tail of the queue but popped from the head of the queue.
Using the graph in the earlier example,when we traverse it in a breadth first fashion we get
i j k m l n p q o.
Having gone through how a stack works and given the above premise on how a queue works,you can trace the algorithm implemented in the below code to verify the output .
Below is the code to implement the functionality.
private static void doBreadthFirstSearchTraversal(Map<String, List<String>> adjList, Set<String> visited, String start) {
Queue queue = new LinkedList();
queue.add(start);
while (queue.size() > 0) {
String current = (String) queue.remove();
if (visited.contains(current)) {
continue;
}
visited.add(current);
System.out.print(" " + current);
for (String neighbor : adjList.get(current)) {
queue.add(neighbor);
}
}
System.out.println();
}
