Connected Components

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132

from typing import Dict, Set, List, Any


def find_components(graph: Dict[Any, Set[Any]]) -> List[Set[Any]]:
    """
    Find all connected components using DFS.

    Args:
        graph: Adjacency list for undirected graph {node: {neighbors}}

    Returns:
        List of sets, where each set contains vertices in one component
    """
    visited = set()
    components = []

    def _dfs(node: Any, component: Set[Any]) -> None:
        visited.add(node)
        component.add(node)

        for neighbor in graph.get(node, set()):
            if neighbor not in visited:
                _dfs(neighbor, component)

    for node in graph:
        if node not in visited:
            component: Set[Any] = set()
            _dfs(node, component)
            components.append(component)

    return components


def count_components(graph: Dict[Any, Set[Any]]) -> int:
    """
    Count the number of connected components.

    Args:
        graph: Adjacency list for undirected graph

    Returns:
        Number of connected components
    """
    return len(find_components(graph))


def are_connected(graph: Dict[Any, Set[Any]], u: Any, v: Any) -> bool:
    """
    Check if two vertices are in the same connected component.

    Args:
        graph: Adjacency list for undirected graph
        u: First vertex
        v: Second vertex

    Returns:
        True if u and v are connected, False otherwise
    """
    if u not in graph or v not in graph:
        return False

    visited = set()

    def _dfs(node: Any) -> bool:
        if node == v:
            return True
        visited.add(node)

        for neighbor in graph.get(node, set()):
            if neighbor not in visited:
                if _dfs(neighbor):
                    return True
        return False

    return _dfs(u)


def get_component(graph: Dict[Any, Set[Any]], vertex: Any) -> Set[Any]:
    """
    Get the connected component containing a specific vertex.

    Args:
        graph: Adjacency list for undirected graph
        vertex: The vertex to find the component for

    Returns:
        Set of all vertices in the same component as vertex
    """
    if vertex not in graph:
        return set()

    component: Set[Any] = set()
    visited = set()

    def _dfs(node: Any) -> None:
        visited.add(node)
        component.add(node)

        for neighbor in graph.get(node, set()):
            if neighbor not in visited:
                _dfs(neighbor)

    _dfs(vertex)
    return component


# Example usage and demonstration
if __name__ == "__main__":
    # Example graph with 3 connected components
    #
    #   Component 1:    Component 2:    Component 3:
    #   A --- B         D --- E         G
    #   |     |         |
    #   C --- F         H
    #
    example_graph = {
        "A": {"B", "C"},
        "B": {"A", "F"},
        "C": {"A", "F"},
        "F": {"B", "C"},
        "D": {"E", "H"},
        "E": {"D"},
        "H": {"D"},
        "G": set(),  # Isolated vertex
    }

    print("Connected Components (DFS):", find_components(example_graph))
    print("Number of Components:", count_components(example_graph))
    print("A and F connected?", are_connected(example_graph, "A", "F"))
    print("A and D connected?", are_connected(example_graph, "A", "D"))
    print("Component containing A:", get_component(example_graph, "A"))