Given an undirected graph represented as an adjacency list, implement a function to find the number of connected components in the graph.

A connected component in an undirected graph is a subgraph where any two vertices within the subgraph are connected by an undirected path, and there are no connections between vertices in different connected components.

Example: Consider the following undirected graph:

0 -- 1    3    5
 \        |    |
  2       4    6

In this graph, there are three connected components:

  • Connected Component 1: {0, 1, 2}
  • Connected Component 2: {3, 4}
  • Connected Component 3: {5, 6}

Function Signature:

from typing import List, Dict

def count_connected_components(graph: Dict[int, List[int]]) -> int:
    """
    Find the number of connected components in an undirected graph.

    Parameters:
    - graph: An adjacency list representing the undirected graph.

    Returns:
    - int: The number of connected components.
    """
    # Your code here

Example:

graph1 = {0: [1, 2], 1: [0], 2: [0], 3: [4], 4: [3], 5: [6], 6: [5]}
result1 = count_connected_components(graph1)
print(result1)
assert result1 == 3
# Explanation: The graph has three connected components: {0, 1, 2}, {3, 4} and {5, 6}.

graph2 = {0: [1, 2], 1: [0], 2: [0], 3: [4, 5], 4: [3], 5: [3]}
result2 = count_connected_components(graph2)
print(result2)
assert result2 == 2
# Explanation: The graph has two connected components: {0, 1, 2} and {3, 4, 5}.

graph3 = {0: [1, 2], 1: [0], 2: [0], 3: [], 4: [5], 5: [4]}
result3 = count_connected_components(graph3)
print(result3)
assert result3 == 3
# Explanation: The graph has three connected components: {0, 1, 2}, {3}, and {4, 5}.

Note:

  • The graph is represented as an adjacency list, where each key-value pair represents a vertex and its neighbors.
  • The vertices are labeled with integers.
  • The graph is undirected, meaning if there is an edge from vertex A to vertex B, there is also an edge from vertex B to vertex A.

Instructions:

  • Write the count_connected_components function to solve the problem.
  • Implement your solution in Python.
  • Provide clear comments in your code.
  • Discuss the time and space complexity of your solution.

Additional Note:

  • Finding connected components is a fundamental operation in graph analysis and is often used to identify groups or clusters of related entities within a larger network. The identification of connected components can provide insights into the structure and connectivity of the graph.

As always, we’ll share our solution to this problem tomorrow. Stay tuned 😊