BFS for Connected Components 🎯

Welcome to our comprehensive guide on BFS (Breadth-First Search) for Connected Components! This lesson is designed for both beginners and intermediate learners, and we'll walk you through this fascinating topic step-by-step. Let's dive in!

Understanding Connected Components 📝

In graph theory, a connected graph is one in which there is a path between every pair of vertices. A graph that is not connected can be divided into disjoint subgraphs, each of which is connected. These subgraphs are called the connected components of the graph.

Introduction to BFS 💡

BFS is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node in the number of trees) and explores all of the neighbor nodes at the present depth prior to moving on to nodes at the next depth level.

Implementing BFS for Connected Components 🎯

Step 1: Initialize

Create an adjacency list (or matrix) to represent the graph.
Create a visited array to keep track of nodes that have been visited.
Initialize a queue to store the nodes that need to be processed.

Step 2: Traversal

Start from an unvisited node, mark it as visited, and add it to the queue.
Dequeue a node from the queue.
For each neighbor of the dequeued node that is not visited, mark it as visited and add it to the queue.
Repeat step 2 until the queue is empty.

Code Example 1: BFS for Connected Components (Python)

python

def connected_components(graph, visited=None):
    if not visited:
        visited = [False] * len(graph)

    def bfs(node):
        visited[node] = True
        queue.append(node)
        while queue:
            current = queue.pop(0)
            for neighbor in graph[current]:
                if not visited[neighbor]:
                    visited[neighbor] = True
                    queue.append(neighbor)

    for i in range(len(graph)):
        if not visited[i]:
            bfs(i)
    return visited.count(True)

Code Example 2: BFS for Connected Components (JavaScript)

javascript

function connectedComponents(graph, visited = new Array(graph.length).fill(false)) {
    function bfs(node) {
        visited[node] = true;
        queue.push(node);
        while (queue.length > 0) {
            const current = queue.shift();
            for (let neighbor of graph[current]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.push(neighbor);
                }
            }
        }
    }

    for (let i = 0; i < graph.length; i++) {
        if (!visited[i]) {
            bfs(i);
        }
    }
    return visited.reduce((count, val) => count + val);
}

Quiz Time! 💡

By now, you should have a good understanding of how BFS can be used to find the connected components in a graph. Keep practicing, and happy coding! 🚀💻🎉