Number of Connected Components in an Undirected Graph

 

1. Clarify the problem: Before diving into solving the problem, let's clarify the requirements:

  • We are given an undirected graph represented by an adjacency list.
  • We need to find the number of connected components in the graph.

2. Analyze the problem: To solve this problem, we can use a depth-first search (DFS) or breadth-first search (BFS) approach to explore the graph and count the number of connected components.

3. Design an algorithm: Here is the algorithm to solve the problem using DFS:

  1. Create a set visited to keep track of visited nodes.
  2. Initialize a variable count to 0 to store the number of connected components.
  3. For each node in the graph:
    • If the node has not been visited:
      • Increment count by 1.
      • Perform DFS starting from the current node and mark all visited nodes.
  4. Return the value of count, which represents the number of connected components.

4. Explain your approach: The approach involves using a depth-first search (DFS) to explore the graph. We start from each unvisited node and perform DFS, marking all visited nodes. Each DFS traversal represents a connected component. We increment the count by 1 for each connected component found. Finally, we return the count, which represents the total number of connected components in the graph.

5. Write clean and readable code:

python
def countComponents(n: int, edges: List[List[int]]) -> int:
    def dfs(node):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                dfs(neighbor)

    graph = {i: [] for i in range(n)}
    visited = set()
    count = 0

    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    for i in range(n):
        if i not in visited:
            count += 1
            dfs(i)

    return count

# Test case
n = 5
edges = [[0, 1], [1, 2], [3, 4]]
print(countComponents(n, edges))  # Expected output: 2

6. Test your code: Let's test the code with the given test case:

  • Test case: n = 5, edges = [[0, 1], [1, 2], [3, 4]].
    • The expected output is 2 because there are two connected components in the graph: {0, 1, 2} and {3, 4}.

7. Optimize if necessary: The current solution has a time complexity of O(V + E), where V is the number of nodes (vertices) and E is the number of edges in the graph. We perform a DFS traversal starting from each unvisited node. The space complexity is O(V) since we use a set to store visited nodes.

8. Handle error cases: The code assumes that the input n is a non-negative integer and edges is a list of lists representing the edges between nodes. If the inputs are not valid (e.g., None, float, or string), the code may raise a TypeError.

9. Discuss complexity analysis:

  • The time complexity of the solution is O(V + E), where V is the number of nodes (vertices) and E is the number of edges in the graph. We perform a DFS traversal starting from each unvisited node.
  • The space complexity is O(V) since we use a set to store visited nodes.
Next Post Previous Post