Count connected components in graph

Question

Given an undirected graph represented as an adjacency list, write a function to count the number of connected components in the graph. A connected component is a subset of the graph where there is a path between any two vertices in that subset. The function should return an integer representing the number of connected components.

Codemia · Accepted Answer

To solve the problem of counting connected components in an undirected graph, we can utilize a graph traversal technique such as Depth-First Search (DFS) or Breadth-First Search (BFS). The reason we choose graph traversal here is that it allows us to explore all the vertices in a connected component starting from any vertex. By performing a traversal for each unvisited vertex, we can identify and count the distinct connected components. The traversal will mark all reachable vertices, enabling us to recognize when we have fully explored one component.

1. **Initialize a visited set** to keep track of visited vertices.
2. **Iterate through each vertex** in the graph's adjacency list:
   - If the vertex has not been visited:
     - Increment the connected component count.
     - Use DFS (or BFS) to traverse from this vertex, marking all reachable vertices as visited.
3. **Return the count of connected components** at the end.

**Example:** For a graph represented as `[{1}, {0, 2}, {1}, {4}, {3}]`, the graph has 2 connected components:
- Component 1: {0, 1, 2}
- Component 2: {3, 4}
Here, starting from 0, we visit 1 and then 2, marking all of them. Next, we find 3 which leads to 4, marking them as another component.

```python
def count_connected_components(graph):
    visited = set()
    component_count = 0

def dfs(vertex):
        stack = [vertex]
        while stack:
            node = stack.pop()
            if node not in visited:
                visited.add(node)
                stack.extend(graph[node])  # Add adjacent vertices to stack

for v in range(len(graph)):
        if v not in visited:
            component_count += 1
            dfs(v)

return component_count
```

The time complexity of this solution is O(V + E), where V is the number of vertices and E is the number of edges in the graph. This is because each vertex and edge will be processed at most once during the DFS traversal. The space complexity is O(V) as well, primarily for the visited set and the recursion stack (or stack used for DFS). Given the constraints, this approach efficiently handles the graph's structure.

1. **Empty Graph:** If the input graph is an empty list (`[]`), the function should return 0, as there are no vertices and hence no components.
2. **Single Vertex:** For a graph with one vertex (`[[]]`), the function should return 1, as that single vertex forms a connected component by itself.
3. **Disconnected Vertices:** If the graph contains multiple disconnected vertices, like `[[1], [0], [], []]`, the output should account for each isolated vertex, resulting in a count equal to the number of vertices.

Count connected components in graph

Neon

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Neon Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string