Write an algorithm to find all the connected components of a graph. Also give the time analysis of your algorithm.

Algorithm

To find all the connected components of a graph, we can use the following algorithm:

1. Initialization:

   • Assign each vertex to its own connected component.
   • Initialize an empty list of connected components.

2. For each vertex v in the graph:

   • If v is not in any connected component,
     • Create a new connected component and add v to it.
   • Otherwise,
     • Find the connected component that v is in.
     • Add v to that connected component.

3. Return the list of connected components.

Time Analysis

The time complexity of this algorithm is O(V + E), where V is the number of vertices and E is the number of edges in the graph. This is because we visit each vertex and each edge once in the worst case.

Python Implementation

def connected_components(graph):
    """
    Find all the connected components of a graph.

    Parameters:
    graph: A dictionary representing the graph, where the keys are the vertices and the values are the list of adjacent vertices.

    Returns:
    A list of connected components, where each connected component is a set of vertices.
    """

    # Initialize the connected components.
    connected_components = []

    # For each vertex in the graph.
    for vertex in graph:
        # If the vertex is not in any connected component.
        if vertex not in connected_components:
            # Create a new connected component and add the vertex to it.
            connected_components.append({vertex})

            # Perform a depth-first search to find all the vertices in the same connected component.
            stack = [vertex]
            while stack:
                current_vertex = stack.pop()
                for adjacent_vertex in graph[current_vertex]:
                    if adjacent_vertex not in connected_components[-1]:
                        connected_components[-1].add(adjacent_vertex)
                        stack.append(adjacent_vertex)

    # Return the list of connected components.
    return connected_components