Connected Components

In graph theory, a Connected Component (or simply a component) of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the supergraph. Think of them as isolated islands within an archipelago.

         Real-World Application:
        Finding connected components is fundamental in cluster analysis, computer vision (detecting
        distinct objects in an image), and network reliability (checking if a network has been split
        into disconnected subnetworks due to node failures).
      

The Algorithm Principle

To identify all connected components, we can use a standard graph traversal algorithm like Breadth-First Search (BFS) or Depth-First Search (DFS). The logic is as follows:

Iterate through every node in the graph.
If the node has not been visited yet, it means we have found a new, unmapped "island" (a new component).
Assign a new Component ID (and a specific color) to this node.
Launch a BFS/DFS starting from this node to discover all other nodes connected to it, assigning them the same Component ID.
Continue the iteration until all nodes in the graph have been visited.

Algorithm Walkthrough

In the script below, we use a BFS approach to map out each component, coloring them distinctively to easily visualize the disconnected subgraphs.

def connected_components():
    all_nodes = get_all_nodes()
    visited = set()
    component_id = 0
    
    for node in all_nodes:
        if node not in visited:
            component_id += 1
            
            # Start mapping a new component using BFS
            queue = [node]
            visited.add(node)
            
            while len(queue) > 0:
                current = queue.pop(0)
                color_node(current, get_color(component_id), f"Belongs to Component {component_id}")
                
                for neighbor in get_undirected_neighbors(current):
                    if neighbor not in visited:
                        visited.add(neighbor)
                        queue.append(neighbor)

connected_components()

Complexity

Metric	Complexity	Explanation
Time Complexity	$O(V + E)$	Where $V$ is the number of vertices and $E$ is the number of edges. We visit every vertex exactly once and traverse each edge a constant number of times during the BFS phase.
Space Complexity	$O(V)$	The space is mainly determined by the `visited` set and the BFS `queue`, both of which will store up to $V$ vertices in the worst-case scenario.