Graph Data Structures in JavaScript — Part 2: Graph Traversals

This post covers Graph Traversals, I’ve covered Graphs Basics and its implementation in Part 1 — Graph Data Structures in JavaScript — Part 1: Graph Basics

There are two algorithms that can be used to traverse a graph, called depth-first search (DFS) and breadth-first search(BFS). Traversing can be used to find a specific vertex, path between two vertices or to check whether the graph is connected, or it contains a cycle, etc.

Depth-First Search

In the depth-first search algorithm, we first visit the starting vertex, then we follow the path until the last vertex of the path is visited and then we backtrack and follow the next path. i.e. if the starting vertex is A, we first visit A and then a neighbor of A and then neighbor of a neighbor of A and so on. After coming to the last vertex of the path(dead end) we backtrack on the path and follow the next path.

image source — geeksforgeeks

Here, let say the starting vertex is 1, we first visit 1 and then 2 and then 4 (dead end), now backtrack to 2 and then 5(dead end) and then backtrack to 1 and then the last 3(dead end).

The DFS Order will be —

1 → 2 → 4 → 5 → 3

DFS Implementation

For implementing depth-first search we use stack as an auxiliary data structure to hold vertices for future processing, and an object to store the visited vertices to avoid visiting twice.

Here we have initialized a stack with starting vertex at first index, object called visited and an empty array called result to store the order.

We will be iterating over the stack until it is empty and in each iteration we will pop out the last vertex from the stack and check if the vertex is visited or not. If the vertex is unvisited then we will add it in the visited objectand to the result array. And last we will add all the neighbors of this vertex in the stack for future processing.

Breadth-First Search

In the breadth-first search algorithm, we first visit the starting vertex and then its neighbours and then their neighbors and so on. i.e. if the starting vertex is A, then we visit all the neighbors of A and then visit all the neighbors of the neighbors of A and so on.

image source — geeksforgeeks

Here, let say the starting vertex is 1, we first visit 1 and then 2 and 3 and then 4 and 5

The BFS order will be —

1 → 2 → 3 → 4 → 5

BFS Implementation

For implementing breadth-first search we use queue as an auxiliary data structure to hold vertices for future processing, and an object to store the visited vertices to avoid visiting twice.

Here we have initialized a queue with starting vertex at first index, object called visited and an empty array called result to store the order.

We will be iterating over the queue until it is empty and in each iteration we will pop out the first vertex from the queue and check if the vertex is visited or not. If the vertex is unvisited then we will add it in the visited objectand to the result array. And last we will add all the neighbors of this vertex in the queue for future processing.

The Github link for the Adjacency List with both DFS and BFS traversal methods.

karan1205/javascript-things

Don’t miss — Graph Data Structures in JavaScript — Part 1: Graph Basics