Graph Traversal is one of the most important topics in the Graph series. It is also one of the most popular interview questions one might expect, because of the ton of real-world applications there are! As discussed in the last blog, we understood different methods of adding and removing edges and vertex.
In this blog we will discuss methods that we can employ in order to search, visit or update each vertex in a graph, their implementation with JavaScript, time complexity, and differences.
Why Graph Traversal Methods are Important?
Before moving forward with the article, one may ask why should we care. So here are some real-world applications which are based on the graph traversal method we extensively use,
- Peer to Peer networking
- Web Crawlers
- Suggesting movies or video matches/recommendations
- GPS navigation
- Finding the shortest path between two points
Also read, Simple Explanation on Sorting Algorithms with JavaScript | Part 1
Problems with Graph Traversal
When we talk about Graph traversal methods, it generally means the process of visiting, checking, or updating each node but in real-world applications where the number of nodes can be in thousands or millions, it may not be very practical. In actual practice, we generally try to find the nearest neighbors or the most similar node or shortest path from one vertex to another.
If we look into a Tree data structure, which is a special subset of a Graph, if we try to reach any specific node placed anywhere in the tree, we have only one special node that we know we can start looking from, which is known as Root node whereas, in Graph, we don’t have any such node.
During Graph traversal you may visit a node that you have already traversed and as the graph becomes denser, time complexities increase. In order to solve it, when we traverse each vertex, we either marked it a color or visitation, so that even though the node appears again during the traverse, it is ignored and the path is not further pursued.
Also read, Learning to Think Like a Computer
Types of Graph Traversal Methods
To solve the above problems we use two most popular tree-based algorithms to traverse methods:-
- Breadth-first search
- Depth-first search
Depth First Search (DFS)
Depth First Search is a tree-based traversing algorithm. In the DFS algorithm, we try to visit child vertices before visiting the sibling vertices of the current vertex. In other words, in DFS we are prioritizing visiting children of the current vertex before we visit its sibling vertices or you can say, we deepen the traversal before widening.
Implementation of Depth First Search method using JS
Recursive Method
- Create a function and name it as depthFirstSearch which accepts one argument, a starting node.
- Create a list to store the end result, to be returned at the end.
- Create an object to store all the visited vertices so that we don’t have to visit them again.
- Create a helper function and name it as dfs which accepts a vertex,
- The helper function should return early if the given vertex is empty
- The helper function should put the given vertex in the visited object, and then push that vertex into the result array.
- Loop over all the values of the adjcencyList for that vertex
- If any of the values have not been visited (added in visited object), then recursively invoke the helper function with that vertex.
- Invoke the helper function with the starting vertex
- Return the final array.
Pseudocode
DFS(vertex):
if vertex is empty:
return (this is our base case)
add vertex to result list
mark vertex as visited
for each neighbour in vertex's neighbors:
if neighbor is not viisted:
recursively calls DFS on neighbor
Code Snippet
function dfs(vertex) {
if (!vertex) {
return null;
}
visisted[vertex] = true;
result.push(vertex);
adjacencyList[vertex].forEach((neighbor) => {
if (!visisted[neighbor]) {
return dfs(neighbor);
}
});
}
function depthFirstSearch(start) {
const result = [];
const visited = {};
const adjacencyList = this.aadjacencyList;
dfs(start);
return result;
}
Also read, What is Big O Notation – Space and Time Complexity
Iterative Method
- Create a function and name it as depthFirstSearch which accepts one argument, a starting node.
- Create a stack to help users keep track of vertices.
- Create a list to store the end result, to be returned at the end.
- Create an object to store all the visited vertices so that we don’t have to visit them again.
- Add the starting vertex to the stack and mark it visited.
- While the stack has something in it,
- Pop the next vertex from the stack
- If that vertex hasn’t been visited yet then,
- Mark it as visited
- Add it to the result list
- Push all of its neighbors into the stack
- And then finally return the result array
Pseudocode
DFS(start):
let s be a stack
s.push(start)
while s is not empty
vertex = s.pop
if vertex is not labeled as discovered:
visit vertex (add to result list)
lable vertex as discovered
for each of vertex's neighbor, N do
s.push(N)
Code Snippet
function depthFirstSearch(start) {
const stack = [start];
const result = [];
const visited = {};
let currentVertex;
visited[start] = true;
while (stack.length) {
currentVertex = stack.pop();
result.push(currentVertex);
this.adjacencyList[currentVertex].forEach((neighbor) => {
if (!visited[neighbor]) {
visited[neighbor] = true;
stack.push(neighbor);
}
});
}
}
Also read, Simple Explanation of Tree traversal Operations with JavaScript
Breadth First Search (BFS)
Breadth First Search is also a tree-based traversing algorithm. In the BFS algorithm, we try to visit sibling vertices before seeing the child vertices of the current vertex. In other words, in BFS we are prioritizing seeing siblings of the current vertex before we visit its children’s vertices or you can say, we widen the traversal before deepening.
Note – BFS is implemented using a Queue data structure that traverses level by level, thus it is not easy to implement BFS through recursion but in DFS we use a Stack data structure to maintain a frontier, and recursion uses (or utilizes) a stack to maintain, well, the ‘call stack’. So implementing DFS using recursion simply means we are replacing stack with call stack but BFS does not use a stack, there is nothing we can replace with the call stack, and thus BFS implementation using recursion is hard.
Implementation of Breadth First Search method using JS
Iterative Method
- Create a function and name it as breadthFirstSearch which accepts one argument, a starting node.
- Create a queue and place the starting vertex in it.
- Create a list to store the end result, to be returned at the end.
- Create an object to store all the visited vertices so that we don’t have to visit them again.
- Mark the starting vertex as visited.
- Keep looping as long as the queue has some vertex inside it,
- Remove the first vertex and push it into the array which stores all the vertex that is already visited.
- If it is not inside the object that stores node visited, mark it as visited and enqueue that vertex.
- Once the loop is over, return the array of visited nodes.
Pseudocode
BFS(start):
let start in queue
while(queue is not empty)
vertex = queue.shift
visit vertex (add to result list)
if vertex is not labeled as discovered:
lable vertex as discovered
add vertex to queue
Also read, Understanding Array, String, and Object Data Structure with JavaScript
Code Snippet
function breadthFirstSearch(start) {
const queue = [start];
const result = [];
const visited = {};
let currentVertex;
while (queue.length) {
currentVertex = queue.shift();
result.push(currentVertex);
this.adjacencyList[currentVertex].forEach((neighbor) => {
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.push(neighbor);
}
});
}
return result;
}
Also read, Basic operations in Graph Data structure
Difference between BFS and DFS
Like everything, both traversal methods come with their own pros and cons, so here is the list of differences between BFS and DFS:-
| Depth First Search | Breadth-First Search |
|---|---|
| In DFS(Depth First Search) traversal we are prioritizing seeing children of the current vertex before we visit its sibling vertices. | In BFS(Breadth First Search) we are prioritizing seeing siblings of the current vertex before we visit its children’s vertices |
| DFS(Depth First Search) uses a Stack data structure for finding the shortest path. | BFS(Breadth First Search) uses a Queue data structure for finding the shortest path. |
| DFS is better when the target vertex is far from the source Vertex. | BFS is better when the target vertex is closer to the source Vertex. |
| DFS is fast as compared to BFS. | BFS is slow as compared to DFS. |
| DFS uses the stack and thus can be implemented using recursion too. | BFS uses the Queue and thus cannot be implemented using recursion too. |
| DFS requires less memory but it is not optimal for finding the shortest path. | BFS requires more memory but It is optimal for finding the shortest path. |
| DFS is used in solving a number of problems like checking if the graph is Bipartite or Solving puzzles. | BFS is used in solving a number of problems like Copying garbage collection, and Cheney’s algorithm or Finding the shortest path between two nodes |
Also read, Introduction to Graph Data Structure
Final Words
BFS and DFS are the most important topics while preparing for interviews, it might look overwhelming at first, but with practice, you will surely be able to master them.
I hope you like the article, please comment and share with your friends and bookmark this website, and also do check our detailed articles on Data structure, Javascript, and programming.
Leave a Reply