Solving connected components problem (graph theory)

Photo by Alina Grubnyak on Unsplash

During your long run on the cracking coding interviews road, you will definitely face graph component problems. Which as you already noticed related to graph data structures. And probably, as you are already familiar with graph structures and algorithms for solving problems related to it. Then you also know methods which can help solve that kind of task on unweighted graphs. In our case, it is — BFS (breadth-first search) and DFS (depth-first search) algorithms. And today I would like to share my experience using them for exact tasks.

Let me start with the description of the problem (from interviewbit.com) :

Given a graph with A nodes.
The edges in graph are given in a 2D array B.
There is an undirected edge between B[i][0] and B[i][1].
Find the number of connected components in the given graph.

Problem constraints:

1 <= A <= 105
1 <= |B| <= 105
1 <= B[i][0], B[i][1] <= A

Providing here next pictures just to give an understanding of the difference between directed and undirected graphs. Since we have it mentioned in the task. Also worth saying there is weighted and unweighted graphs exist. But again — today we’re dealing with the easiest version of the graph.

Undirected graph

Directed graph

The next things that I would like to speak about — it’s both algorithms' explanation, their purposes and comparison. Want to show how to implement them and then we will choose one to solve our task.

Breadth-first search

First of all, let’s recall what is this algorithm about. BFS usually uses for finding the shortest path between graph nodes. Unlike DFS it explores all the neighbour nodes at the present depth before moving on to the next depth. It explores level by level. It uses for that queue. And from this perspective, it can use more memory (for wide graphs) as it needs to store all nodes at the current level. But it guarantees you find the shortest path between nodes in unweighted graphs. It is a widely used algorithm for such problems.

Step-by-step algorithm:
1. Choose a starting node: BFS begins by selecting a starting node as the source of the traversal. This node is added to a queue (a First-In-First-Out - FIFO data structure).
2. Mark the starting node as visited: The starting node is marked as visited, so we don't revisit it later.
3. Explore neighbours: BFS examines all the neighbours (adjacent nodes) of the current node. It processes the neighbours one by one.
4. Enqueue neighbours: For each unvisited neighbour of the current node, add it to the end of the queue. This ensures that nodes at the same level are processed before moving to the next level.
5. Dequeue the next node: Remove the front node from the queue (the node that was first inserted) and make it the new current node. This is how BFS moves to the next level.
6. Repeat steps 3 to 5: Continue the process until the queue becomes empty. When the queue is empty, it means all nodes have been visited, and the traversal is complete.

BFS Algorithm is exploring graph

And implementation with JavaScript you’ll see in the next snippet.

function bfs(graph, initialNode) {
  const queue = [initialNode]
  const visited = new Set()
  while (queue.length > 0) {
    currentNode = queue.shift()
    if (!visited.has(currentNode)) {
      visited.add(currentNode)
      
      for (const neighbour of graph[currentNode]) {
        if(!visites.has(neighbour)) {
          queue.push(neighbour)
        }
      }
    }
  }
}

// Example usage:
// (graph represented in the form of an adjacency list)
const graph = {
  0: [1, 2],
  1: [0, 2, 3],
  2: [0, 1, 3],
  3: [1, 2, 4],
  4: [3],
};

bfs(graph, 0);

Depth-first search

This one is pretty similar to the first one. The only difference it goes in-depth to put the next nodes in the queue. DFS explores as far as possible along each branch before backtracking. It goes deep into the graph before exploring the neighbours of a node. It can be implemented by recursion or a stack data structure (versus queue in BFS) to keep track of the nodes. Generally, it uses less memory to store nodes in the current path. One downside I have to mention here — it might not find the shortest path, it returns the first found path which is not guaranteed to be optimal.

Step-by-step algorithm:
1. Choose a starting node: DFS begins by selecting a starting node as the source of the traversal.
2. Mark the starting node as visited: The starting node is marked as visited, so we don’t revisit it later.
3. Explore neighbours: DFS picks an unvisited neighbour of the current node and moves to that neighbour. It continues this process of selecting an unvisited neighbour and moving to it.
4. Recursion or Stack: The way DFS keeps track of the traversal path depends on the implementation:
- Using Recursion: In the recursive approach, for each unvisited neighbour, DFS calls itself with the unvisited neighbour as the new current node. This effectively pushes the current node onto the call stack and explores its neighbours recursively.
- Using an Explicit Stack: Alternatively, DFS can use an explicit stack data structure to keep track of nodes to visit. It pushes the current node onto the stack and explores its neighbours until there are no more unvisited neighbours. If there are no unvisited neighbours, it pops the last node from the stack and moves back to its parent node to explore other unvisited neighbours.
5. Backtrack: If a node has no more unvisited neighbours (dead end), DFS backtracks to the previous node on the stack (if using a stack) or returns from the recursive call (if using recursion). This backtracking allows the algorithm to explore other branches and paths in the graph.
6. Repeat steps 3 to 5: DFS continues exploring and backtracking until all reachable nodes from the starting node are visited.

And here is just an implementation (sorry no illustration this time):

function dfs(graph, currentNode, visited) {
  if (visited.has(currentNode)) {
    return;
  }

  visited.add(currentNode);
  for (const neighbour of graph[currentNode]) {
    dfs(graph, neighbor, visited);
  }
}

// same graph could be used here 
const visited = new Set();
dfs(graph, 0, visited);

Oh, you would say it looks better and more readable because of recursion. Yes. I also think so. Recursions work really better for situations when you go in depth.

So since we have similar complexity (big O) for both I have chosen DFS. [Big O is O(V+E) for both algorithms, where V — vertices, E — edges. And as I mentioned earlier, BFS take extra space for storing queue, at the same time DFS also consumes some memory running itself recursively and using the engine’s stack.].

— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —

Taking into account the initial data format for our task we will need to do also some preparations — build adjacent nodes list. And then can apply the DFS algorithm.
That’s how the final solution will look:

function buildAdjacencyList(A, B) {
  const adjList = {};
  for (let i = 1; i <= A; i++) {
      adjList[i] = [];
  }

  for (const edge of B) {
      const [node1, node2] = edge;
      adjList[node1].push(node2);
      adjList[node2].push(node1); // Since it's an undirected graph, add both directions.
  }

  return adjList;
}

function dfs(node, adjList, visited) {
  if (visited.has(node)) {
      return;
  }

  visited.add(node);
  for (const neighbour of adjList[node]) {
      dfs(neighbour, adjList, visited);
  }
}

function countConnectedComponents(A, B) {
  const adjList = buildAdjacencyList(A, B);
  const visited = new Set();
  let connectedComponents = 0;

  for (let node = 1; node <= A; node++) {
      if (!visited.has(node)) {
          connectedComponents++;
          dfs(node, adjList, visited);
      }
  }

  return connectedComponents;
}

// Example usage:
const A = 5;
const B = [[1, 2], [3, 4], [4, 5]];
console.log(countConnectedComponents(A, B)); // Output will be 2

Providing here also links to resources I currently use for training myself:
- leetcode
- interview bit
- khan academy (a really great educational resource to refresh mathematics, algebra, geometry, or computer science also)
- not forgetting about ChatGPT of course :) which really helps overcome difficulties and navigates you faster to the solution

And of course books for learning data structures and algorithms.
Grokking Algorithms (Aditya Bhargava)
Introduction to Algorithms (Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein)
Data Structures and Algorithms with Javascript
I would really treat it a bit outdated, in terms of modern JavaScript, but it could be handy to know how to implement different data structures in an old-fashioned way. Even most of the time you can use existing data structures in JavaScript, especially after Set, Map, Symbol, and of course classes were introduced.
So you will most likely like this short video course from freecodecamp.

Thank you for reading me. Enjoy solving problems and learning. Bye!