Connected vs Disconnected Graphs - Graph Properties — Connectivity, Cycles, Degree | OneNoughtOne

0/361

Data Structures & AlgorithmsGraph Properties

Graph Properties — Connectivity, Cycles, Degree

LevelIntermediate

Duration90 mins

TopicGraph Properties

1 / 4

Connected vs Disconnected Graphs

Why Connectivity Matters

Imagine you're building a social network and need to answer a simple question: Can information flow from any user to any other user through friend connections? Or consider a transportation engineer asking: Can a passenger travel from any city to any other city in the network? These questions—seemingly simple—are fundamentally about graph connectivity.

Connectivity is one of the most important structural properties of a graph. It determines whether a graph forms a cohesive whole or fragments into isolated pieces. Understanding connectivity is essential for:

Network reliability: Can a network continue functioning if nodes fail?
Algorithm correctness: Many algorithms assume connected graphs
Problem decomposition: Disconnected graphs can often be solved piece by piece
Real-world modeling: Physical and logical networks must account for connectivity

What You Will Learn

By the end of this page, you will understand what makes a graph connected or disconnected, how to identify and enumerate connected components, the algorithms used to determine connectivity, and how connectivity analysis applies to real-world problems. You'll also explore the deeper concepts of strongly connected components in directed graphs.

Fundamental Definitions of Connectivity

Before we can analyze connectivity, we need precise definitions. Graph theory is built on rigorous mathematical foundations, and understanding connectivity requires us to first define what we mean by paths and reachability.

What is a Path?

A path in a graph G = (V, E) is a sequence of vertices v₀, v₁, v₂, ..., vₖ where:

Each consecutive pair of vertices (vᵢ, vᵢ₊₁) is connected by an edge
No vertex appears more than once in the sequence

The length of a path is the number of edges it traverses (k in the sequence above). A path from vertex u to vertex v establishes that v is reachable from u.

Connected Graphs: The Formal Definition

An undirected graph G = (V, E) is said to be connected if and only if:

For every pair of vertices u, v ∈ V, there exists a path from u to v.

Equivalently, a graph is connected if every vertex can reach every other vertex. This is a remarkably powerful property—it means information, influence, or any quantity that flows along edges can propagate throughout the entire graph.

The Single-Vertex Case

By convention, a graph with a single vertex and no edges is considered connected. The trivial path from a vertex to itself (of length 0) satisfies the definition. Similarly, an empty graph with no vertices is vacuously connected since there are no pairs of vertices that need connecting.

Disconnected Graphs

A graph is disconnected if it is not connected—that is, there exist at least two vertices u and v such that no path connects them. In a disconnected graph, the vertex set V can be partitioned into two or more non-empty subsets where no edges cross between subsets.

The Connectivity Spectrum

Connectivity isn't just a binary property. Graphs can be:

Connected: All vertices reachable from all others
Disconnected: At least one unreachable pair exists
k-connected: Remains connected after removing any k-1 vertices (we'll touch on this advanced concept later)

For now, we focus on the fundamental binary distinction: connected vs. disconnected.

Connectivity Classification Summary
Property	Connected Graph	Disconnected Graph
Path existence	Path exists between every vertex pair	At least one vertex pair with no path
Edge requirement	At least \|V\| - 1 edges (minimum)	Can have any number of edges
Component count	Exactly 1 connected component	2 or more connected components
Traversal behavior	Single DFS/BFS visits all vertices	Multiple traversals needed
Reachability matrix	All non-diagonal entries are reachable	Some entries unreachable

Visualizing Connectivity

The difference between connected and disconnected graphs becomes immediately apparent when visualized. Let's examine both cases to build intuition.

A Connected Graph

Consider a social network where every person can eventually reach every other person through friend-of-friend connections:

Converting Mermaid diagram...

In this graph, every person can reach every other person:

Alice → Bob → Carol
Alice → David → Eve
Carol → Eve (directly)

No matter which two vertices you pick, a path exists. This is the hallmark of a connected graph.

A Disconnected Graph

Now consider a scenario where two groups of people have no connections between them:

Converting Mermaid diagram...

This graph has two connected components:

{Alice, Bob, Carol} — fully connected among themselves
{David, Eve, Frank} — fully connected among themselves

But there's no path from anyone in Component 1 to anyone in Component 2. Alice cannot reach David through any sequence of edges. The graph is disconnected.

Visual Intuition

A quick visual test: if you can draw your graph such that all vertices and edges form one continuous "blob" without lifting your pen, it's likely connected. If you see separate clusters with no bridges, it's disconnected. Of course, algorithms provide the definitive answer.

Connected Components: The Building Blocks

Connected components are the fundamental building blocks that partition a graph into its maximal connected subgraphs. Understanding components is crucial for analyzing graph structure and decomposing problems.

Formal Definition

A connected component of an undirected graph G = (V, E) is a maximal subset S ⊆ V such that:

Every pair of vertices in S is connected by a path (using only vertices in S)
No vertex outside S is connected to any vertex in S

The word maximal is critical—it means we cannot add any more vertices while maintaining connectivity. Each connected component is as large as possible.

Properties of Connected Components

Connected components have several important mathematical properties:

Key Properties of Connected Components

•Partition property: Components form a partition of V—every vertex belongs to exactly one component, and components don't overlap
•Edge containment: Every edge (u, v) belongs to exactly one component (the one containing both u and v)
•Internal connectivity: Within a component, the induced subgraph is connected
•External isolation: No edges exist between different components
•Uniqueness: The partition into connected components is unique for any given graph

Counting Components

The number of connected components is a fundamental graph invariant (a property that doesn't change under graph isomorphism). For a graph G:

If G has 1 component, G is connected
If G has k > 1 components, G is disconnected
If G has |V| components, the graph has no edges (each vertex is isolated)

The Component Graph

We can create a higher-level view by treating each connected component as a single "super-vertex." This component graph (or condensation) shows the macro-structure of a disconnected graph. For undirected graphs, the component graph has no edges (since by definition, components are not connected to each other).

Examples of Component Counts
Graph Type	Vertices	Edges	Components	Notes
Complete graph Kₙ	n	n(n-1)/2	1	Maximally connected
Path graph Pₙ	n	n-1	1	Minimally connected
Cycle graph Cₙ	n	n	1	Minimally 2-connected
Empty graph (no edges)	n	0	n	No connectivity
Forest (k trees)	n	n-k	k	Trees are minimally connected

Algorithms for Finding Connected Components

Determining connectivity and identifying components are fundamental algorithmic tasks. There are two primary approaches: traversal-based (using DFS or BFS) and union-find based. Let's explore both in depth.

Approach 1: Traversal-Based (DFS/BFS)

The simplest and most intuitive method uses graph traversal. The key insight is:

A single DFS or BFS starting from any vertex will visit exactly the vertices in that vertex's connected component.

By repeatedly starting new traversals from unvisited vertices, we can identify all components:

connected_components.py
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
def find_connected_components(graph: dict[int, list[int]]) -> list[list[int]]:
    """
    Find all connected components in an undirected graph.
    
    Args:
        graph: Adjacency list representation where graph[v] = list of neighbors
        
    Returns:
        List of components, where each component is a list of vertices
        
    Time Complexity: O(V + E) - each vertex and edge visited once
    Space Complexity: O(V) - for visited set and recursion stack
    """
    visited = set()
    components = []
    
    def dfs(vertex: int, component: list[int]) -> None:
        """Explore all vertices reachable from 'vertex'."""
        visited.add(vertex)
        component.append(vertex)
        
        for neighbor in graph.get(vertex, []):
            if neighbor not in visited:
                dfs(neighbor, component)
    
    # Iterate through all vertices
    for vertex in graph:
        if vertex not in visited:
            # Found a new component - explore it completely
            current_component = []
            dfs(vertex, current_component)
            components.append(current_component)
    
    return components
 
 
def is_connected(graph: dict[int, list[int]]) -> bool:
    """
    Determine if the graph is connected.
    
    A graph is connected iff it has exactly one connected component.
    """
    if not graph:
        return True  # Empty graph is vacuously connected
    
    components = find_connected_components(graph)
    return len(components) == 1
 
 
# Example usage
graph = {
    0: [1, 2],
    1: [0, 2],
    2: [0, 1],
    3: [4],
    4: [3],
    5: []  # Isolated vertex
}
 
components = find_connected_components(graph)
print(f"Number of components: {len(components)}")  # Output: 3
print(f"Components: {components}")  # Output: [[0, 1, 2], [3, 4], [5]]
print(f"Is connected: {is_connected(graph)}")  # Output: False

Approach 2: Union-Find (Disjoint Set Union)

For dynamic graphs where edges are added over time, Union-Find provides an efficient alternative. It supports:

Union(u, v): Connect two components
Find(u): Determine which component contains u
Connected(u, v): Check if u and v are in the same component

union_find_connectivity.py
Python
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
class UnionFind:
    """
    Union-Find (Disjoint Set Union) for connectivity queries.
    
    Uses path compression and union by rank for near-O(1) operations.
    Specifically, O(α(n)) where α is the inverse Ackermann function.
    """
    
    def __init__(self, n: int):
        """Initialize n separate components (vertices 0 to n-1)."""
        self.parent = list(range(n))  # Each vertex is its own parent
        self.rank = [0] * n           # Rank for union by rank
        self.component_count = n      # Initially n separate components
    
    def find(self, x: int) -> int:
        """
        Find the root (representative) of x's component.
        Uses path compression: makes all nodes point directly to root.
        """
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # Path compression
        return self.parent[x]
    
    def union(self, x: int, y: int) -> bool:
        """
        Merge the components containing x and y.
        
        Returns True if a merge occurred (x and y were in different components).
        Returns False if x and y were already in the same component.
        """
        root_x = self.find(x)
        root_y = self.find(y)
        
        if root_x == root_y:
            return False  # Already in same component
        
        # Union by rank: attach smaller tree under larger tree
        if self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
        elif self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
        else:
            self.parent[root_y] = root_x
            self.rank[root_x] += 1
        
        self.component_count -= 1
        return True
    
    def connected(self, x: int, y: int) -> bool:
        """Check if x and y are in the same component."""
        return self.find(x) == self.find(y)
    
    def get_component_count(self) -> int:
        """Return the current number of connected components."""
        return self.component_count
 
 
# Building the graph incrementally
uf = UnionFind(6)  # Vertices 0-5
 
# Add edges one by one
edges = [(0, 1), (1, 2), (0, 2), (3, 4)]
for u, v in edges:
    uf.union(u, v)
 
print(f"Component count: {uf.get_component_count()}")  # 3 (vertices 5 is isolated)
print(f"0 connected to 2: {uf.connected(0, 2)}")  # True
print(f"0 connected to 3: {uf.connected(0, 3)}")  # False

When to Use Which Algorithm

Use DFS/BFS when: (1) you have a static graph and need to find all components once, (2) you need the actual list of vertices in each component, or (3) you want to process vertices in a specific order. Use Union-Find when: (1) edges are added dynamically, (2) you need fast connectivity queries, or (3) you're building a graph incrementally (like Kruskal's MST algorithm).

Complexity Analysis

Understanding the time and space complexity of connectivity algorithms is essential for choosing the right approach and predicting performance at scale.

DFS/BFS Traversal Approach

DFS/BFS Connectivity Analysis
Metric	Complexity	Explanation
Time Complexity	O(V + E)	Each vertex visited once, each edge examined once
Space Complexity	O(V)	Visited set + recursion stack (DFS) or queue (BFS)
Adjacency Matrix	O(V²)	Must scan all V² entries for neighbors
Single query	O(V + E)	Still need full traversal to confirm reachability

Union-Find Approach

Union-Find has remarkable nearly-constant time operations:

Union-Find Complexity Analysis
Operation	Time Complexity	Notes
find(x)	O(α(n)) ≈ O(1)	α(n) ≤ 4 for all practical n
union(x, y)	O(α(n)) ≈ O(1)	Amortized with path compression
connected(x, y)	O(α(n)) ≈ O(1)	Two find operations
Build from m edges	O(m · α(n))	m union operations
Space	O(n)	Parent and rank arrays

The Inverse Ackermann Function

The inverse Ackermann function α(n) grows so slowly that for all practical purposes (n < 2^65536), α(n) ≤ 4. This makes Union-Find operations effectively constant time. It's one of the most remarkable results in algorithm analysis: a data structure that supports dynamic connectivity in nearly-constant time per operation.

Comparison Summary

Choosing between approaches depends on the use case:

Scenario	Best Approach	Reasoning
Static graph, find all components	DFS/BFS	Single O(V+E) pass is optimal
Static graph, many queries	DFS/BFS + cache	Precompute component IDs
Dynamic graph, edges added	Union-Find	O(α(n)) per edge addition
Must list component members	DFS/BFS	Union-Find only stores roots
Very dense graph	Either	Both handle dense graphs well

Connectivity in Directed Graphs

Connectivity becomes significantly more nuanced in directed graphs. Because edges have direction, reachability is no longer symmetric: reaching v from u doesn't guarantee reaching u from v.

Weak vs. Strong Connectivity

Directed graphs have two types of connectivity:

Weakly Connected: A directed graph is weakly connected if replacing all directed edges with undirected edges results in a connected graph. In other words, ignoring edge directions, every vertex can reach every other.

Strongly Connected: A directed graph is strongly connected if for every pair of vertices u and v:

There exists a directed path from u to v, AND
There exists a directed path from v to u

Strong connectivity is a much stricter requirement. It means we can navigate from anywhere to anywhere following edge directions.

Weakly Connected Example

Consider a directed graph where:

A → B → C

We can't get from C back to A, but ignoring directions, the graph is connected. This is weakly connected but not strongly connected.

Converting Mermaid diagram...

Strongly Connected Example

Now add an edge C → A:

A → B → C → A (cycle)

Now every vertex can reach every other vertex. This is strongly connected.

Converting Mermaid diagram...

Strongly Connected Components (SCCs)

Just as undirected graphs decompose into connected components, directed graphs decompose into Strongly Connected Components (SCCs). An SCC is a maximal set of vertices where every vertex can reach every other vertex.

Key properties of SCCs:

The SCCs partition the vertex set (every vertex is in exactly one SCC)
The condensation graph (treating each SCC as a vertex) is always a DAG
Finding SCCs enables topological decomposition of complex graphs

Algorithms for SCCs:

Kosaraju's Algorithm: Two DFS passes (O(V + E))
Tarjan's Algorithm: Single DFS pass (O(V + E))
Path-based Algorithm: Also single DFS (O(V + E))

These algorithms are covered in depth in the graph algorithms chapter, but the concept is essential to understand here: directed connectivity decomposes into SCCs, and the relationships between SCCs form a DAG.

Direction Matters

A common mistake is to apply undirected connectivity algorithms to directed graphs. This will find weakly connected components, not strongly connected components. Always use direction-aware algorithms (like Kosaraju or Tarjan) for directed graph connectivity analysis.

Real-World Applications of Connectivity

Graph connectivity underlies countless real-world systems. Understanding where and how connectivity analysis applies helps you recognize it in practical problems.

Applications Across Domains

•Social Networks: Find communities within a platform; identify isolated user groups; measure how viral content can spread through the network; detect fake account clusters that aren't connected to legitimate users
•Computer Networks: Determine if all nodes can communicate; identify network partitions after failures; analyze impact of router/switch failures on connectivity; design redundant paths
•Transportation: Check if passengers can travel between any two cities; identify disconnected regions requiring new routes; analyze impact of road closures; optimize bus/train routes to maintain connectivity
•Electrical Grids: Verify all consumers are connected to power sources; identify blackout regions; design redundant power transmission paths; analyze fault tolerance
•Software Dependencies: Find modules that are completely independent; identify unused code components; detect circular dependencies through SCC analysis; plan migration strategies
•Image Processing: Connected component labeling identifies distinct objects in images; used in OCR, medical imaging, and computer vision; region segmentation relies on pixel connectivity

Case Study: Network Resilience Analysis

Consider analyzing the resilience of a computer network. Key questions include:

Current state: Is the network connected? (Single component check)
Critical nodes: Which nodes, if failed, would disconnect the network? (Articulation points)
Critical edges: Which edges, if failed, would disconnect the network? (Bridges)
Redundancy: How many independent paths exist between critical servers? (Edge/vertex connectivity)

These questions progressively build on basic connectivity to form a complete resilience analysis. Connectivity is the foundation upon which more sophisticated network analysis builds.

Interview Pattern

Many interview problems can be reframed as connectivity problems: "Can we reach state B from state A?" becomes "Is there a path in the state-space graph?" Grid traversal problems, word ladders, and puzzle-solving all reduce to graph connectivity. When you see these patterns, reach for DFS/BFS or Union-Find.

Common Patterns and Pitfalls

Working with graph connectivity involves recognizing common patterns and avoiding frequent mistakes. Here are the key insights gained through experience.

Best Practices

•Always validate inputs: Check for empty graphs and isolated vertices
•Handle isolated vertices: They form their own components
•Choose the right algorithm: DFS for static, Union-Find for dynamic
•Watch for directed vs undirected: Don't mix up the algorithms
•Use iterative DFS for large graphs: Avoid stack overflow
•Cache component IDs: If querying connectivity repeatedly

Common Mistakes

•Forgetting isolated vertices: They won't appear in adjacency lists
•Stack overflow on recursive DFS: Convert to iterative for large graphs
•Wrong Union-Find initialization: Must handle 0-indexed vs 1-indexed
•Applying undirected algo to directed graph: Misses directionality
•Not handling self-loops: Can confuse traversal logic
•Modifying graph during traversal: Invalidates visited state

The Isolated Vertex Trap

A particularly common bug involves isolated vertices (vertices with no edges). In adjacency list representation, isolated vertices might not appear as keys if you're only adding vertices when edges are added:

# Bug: isolated vertices missing
graph = {}
for u, v in edges:
    graph.setdefault(u, []).append(v)
    graph.setdefault(v, []).append(u)
# Vertex 5 with no edges is missing from graph!

# Fix: explicitly add all vertices
def build_graph(n: int, edges: list) -> dict:
    graph = {i: [] for i in range(n)}  # All vertices present
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    return graph

Always ensure your graph representation includes isolated vertices when counting components.

Summary: Mastering Graph Connectivity

Graph connectivity is a foundational concept that underlies much of graph theory and its applications. Let's consolidate what we've learned:

Key Takeaways

•A graph is connected if there's a path between every pair of vertices; otherwise, it's disconnected
•Connected components are maximal connected subgraphs that partition the vertex set
•DFS/BFS finds components in O(V + E) time by exploring from each unvisited vertex
•Union-Find supports dynamic connectivity with nearly O(1) operations using path compression and union by rank
•Directed graphs have weak and strong connectivity; SCCs decompose directed graphs into strongly connected pieces
•Real-world applications span social networks, transportation, image processing, and network resilience
•Common pitfalls include forgetting isolated vertices and using undirected algorithms on directed graphs

What's Next:

With connectivity understood, we're ready to explore paths and cycles—the "roads" within a graph and the circular journeys that return to their starting point. Cycles have profound implications for graph algorithms and are essential for understanding phenomena from deadlocks to feedback loops.

Page Complete

You now have a deep understanding of graph connectivity. You can determine if graphs are connected, find all connected components, choose between DFS/BFS and Union-Find based on the problem requirements, and understand the nuances of connectivity in directed graphs. Next, we'll explore paths and cycles.

Data Structures & AlgorithmsGraph Properties

Graph Properties — Connectivity, Cycles, Degree

LevelIntermediate

Duration90 mins

TopicGraph Properties

1 / 4

Connected vs Disconnected Graphs

Why Connectivity Matters

Network reliability: Can a network continue functioning if nodes fail?
Algorithm correctness: Many algorithms assume connected graphs
Problem decomposition: Disconnected graphs can often be solved piece by piece
Real-world modeling: Physical and logical networks must account for connectivity

What You Will Learn

Fundamental Definitions of Connectivity

What is a Path?

A path in a graph G = (V, E) is a sequence of vertices v₀, v₁, v₂, ..., vₖ where:

Each consecutive pair of vertices (vᵢ, vᵢ₊₁) is connected by an edge
No vertex appears more than once in the sequence

The length of a path is the number of edges it traverses (k in the sequence above). A path from vertex u to vertex v establishes that v is reachable from u.

Connected Graphs: The Formal Definition

An undirected graph G = (V, E) is said to be connected if and only if:

For every pair of vertices u, v ∈ V, there exists a path from u to v.

The Single-Vertex Case

Disconnected Graphs

The Connectivity Spectrum

Connectivity isn't just a binary property. Graphs can be:

Connected: All vertices reachable from all others
Disconnected: At least one unreachable pair exists
k-connected: Remains connected after removing any k-1 vertices (we'll touch on this advanced concept later)

For now, we focus on the fundamental binary distinction: connected vs. disconnected.

Connectivity Classification Summary
Property	Connected Graph	Disconnected Graph
Path existence	Path exists between every vertex pair	At least one vertex pair with no path
Edge requirement	At least \|V\| - 1 edges (minimum)	Can have any number of edges
Component count	Exactly 1 connected component	2 or more connected components
Traversal behavior	Single DFS/BFS visits all vertices	Multiple traversals needed
Reachability matrix	All non-diagonal entries are reachable	Some entries unreachable

Visualizing Connectivity

The difference between connected and disconnected graphs becomes immediately apparent when visualized. Let's examine both cases to build intuition.

A Connected Graph

Consider a social network where every person can eventually reach every other person through friend-of-friend connections:

Converting Mermaid diagram...

In this graph, every person can reach every other person:

Alice → Bob → Carol
Alice → David → Eve
Carol → Eve (directly)

No matter which two vertices you pick, a path exists. This is the hallmark of a connected graph.

A Disconnected Graph

Now consider a scenario where two groups of people have no connections between them:

Converting Mermaid diagram...

This graph has two connected components:

{Alice, Bob, Carol} — fully connected among themselves
{David, Eve, Frank} — fully connected among themselves

But there's no path from anyone in Component 1 to anyone in Component 2. Alice cannot reach David through any sequence of edges. The graph is disconnected.

Visual Intuition

Connected Components: The Building Blocks

Formal Definition

A connected component of an undirected graph G = (V, E) is a maximal subset S ⊆ V such that:

Every pair of vertices in S is connected by a path (using only vertices in S)
No vertex outside S is connected to any vertex in S

The word maximal is critical—it means we cannot add any more vertices while maintaining connectivity. Each connected component is as large as possible.

Properties of Connected Components

Connected components have several important mathematical properties:

Key Properties of Connected Components

•Partition property: Components form a partition of V—every vertex belongs to exactly one component, and components don't overlap
•Edge containment: Every edge (u, v) belongs to exactly one component (the one containing both u and v)
•Internal connectivity: Within a component, the induced subgraph is connected
•External isolation: No edges exist between different components
•Uniqueness: The partition into connected components is unique for any given graph

Counting Components

The number of connected components is a fundamental graph invariant (a property that doesn't change under graph isomorphism). For a graph G:

If G has 1 component, G is connected
If G has k > 1 components, G is disconnected
If G has |V| components, the graph has no edges (each vertex is isolated)

The Component Graph

Examples of Component Counts
Graph Type	Vertices	Edges	Components	Notes
Complete graph Kₙ	n	n(n-1)/2	1	Maximally connected
Path graph Pₙ	n	n-1	1	Minimally connected
Cycle graph Cₙ	n	n	1	Minimally 2-connected
Empty graph (no edges)	n	0	n	No connectivity
Forest (k trees)	n	n-k	k	Trees are minimally connected

Algorithms for Finding Connected Components

Approach 1: Traversal-Based (DFS/BFS)

The simplest and most intuitive method uses graph traversal. The key insight is:

A single DFS or BFS starting from any vertex will visit exactly the vertices in that vertex's connected component.

By repeatedly starting new traversals from unvisited vertices, we can identify all components:

connected_components.py
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
def find_connected_components(graph: dict[int, list[int]]) -> list[list[int]]:
    """
    Find all connected components in an undirected graph.
    
    Args:
        graph: Adjacency list representation where graph[v] = list of neighbors
        
    Returns:
        List of components, where each component is a list of vertices
        
    Time Complexity: O(V + E) - each vertex and edge visited once
    Space Complexity: O(V) - for visited set and recursion stack
    """
    visited = set()
    components = []
    
    def dfs(vertex: int, component: list[int]) -> None:
        """Explore all vertices reachable from 'vertex'."""
        visited.add(vertex)
        component.append(vertex)
        
        for neighbor in graph.get(vertex, []):
            if neighbor not in visited:
                dfs(neighbor, component)
    
    # Iterate through all vertices
    for vertex in graph:
        if vertex not in visited:
            # Found a new component - explore it completely
            current_component = []
            dfs(vertex, current_component)
            components.append(current_component)
    
    return components
 
 
def is_connected(graph: dict[int, list[int]]) -> bool:
    """
    Determine if the graph is connected.
    
    A graph is connected iff it has exactly one connected component.
    """
    if not graph:
        return True  # Empty graph is vacuously connected
    
    components = find_connected_components(graph)
    return len(components) == 1
 
 
# Example usage
graph = {
    0: [1, 2],
    1: [0, 2],
    2: [0, 1],
    3: [4],
    4: [3],
    5: []  # Isolated vertex
}
 
components = find_connected_components(graph)
print(f"Number of components: {len(components)}")  # Output: 3
print(f"Components: {components}")  # Output: [[0, 1, 2], [3, 4], [5]]
print(f"Is connected: {is_connected(graph)}")  # Output: False

Approach 2: Union-Find (Disjoint Set Union)

For dynamic graphs where edges are added over time, Union-Find provides an efficient alternative. It supports:

Union(u, v): Connect two components
Find(u): Determine which component contains u
Connected(u, v): Check if u and v are in the same component

union_find_connectivity.py
Python
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
class UnionFind:
    """
    Union-Find (Disjoint Set Union) for connectivity queries.
    
    Uses path compression and union by rank for near-O(1) operations.
    Specifically, O(α(n)) where α is the inverse Ackermann function.
    """
    
    def __init__(self, n: int):
        """Initialize n separate components (vertices 0 to n-1)."""
        self.parent = list(range(n))  # Each vertex is its own parent
        self.rank = [0] * n           # Rank for union by rank
        self.component_count = n      # Initially n separate components
    
    def find(self, x: int) -> int:
        """
        Find the root (representative) of x's component.
        Uses path compression: makes all nodes point directly to root.
        """
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # Path compression
        return self.parent[x]
    
    def union(self, x: int, y: int) -> bool:
        """
        Merge the components containing x and y.
        
        Returns True if a merge occurred (x and y were in different components).
        Returns False if x and y were already in the same component.
        """
        root_x = self.find(x)
        root_y = self.find(y)
        
        if root_x == root_y:
            return False  # Already in same component
        
        # Union by rank: attach smaller tree under larger tree
        if self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
        elif self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
        else:
            self.parent[root_y] = root_x
            self.rank[root_x] += 1
        
        self.component_count -= 1
        return True
    
    def connected(self, x: int, y: int) -> bool:
        """Check if x and y are in the same component."""
        return self.find(x) == self.find(y)
    
    def get_component_count(self) -> int:
        """Return the current number of connected components."""
        return self.component_count
 
 
# Building the graph incrementally
uf = UnionFind(6)  # Vertices 0-5
 
# Add edges one by one
edges = [(0, 1), (1, 2), (0, 2), (3, 4)]
for u, v in edges:
    uf.union(u, v)
 
print(f"Component count: {uf.get_component_count()}")  # 3 (vertices 5 is isolated)
print(f"0 connected to 2: {uf.connected(0, 2)}")  # True
print(f"0 connected to 3: {uf.connected(0, 3)}")  # False

When to Use Which Algorithm

Complexity Analysis

Understanding the time and space complexity of connectivity algorithms is essential for choosing the right approach and predicting performance at scale.

DFS/BFS Traversal Approach

DFS/BFS Connectivity Analysis
Metric	Complexity	Explanation
Time Complexity	O(V + E)	Each vertex visited once, each edge examined once
Space Complexity	O(V)	Visited set + recursion stack (DFS) or queue (BFS)
Adjacency Matrix	O(V²)	Must scan all V² entries for neighbors
Single query	O(V + E)	Still need full traversal to confirm reachability

Union-Find Approach

Union-Find has remarkable nearly-constant time operations:

Union-Find Complexity Analysis
Operation	Time Complexity	Notes
find(x)	O(α(n)) ≈ O(1)	α(n) ≤ 4 for all practical n
union(x, y)	O(α(n)) ≈ O(1)	Amortized with path compression
connected(x, y)	O(α(n)) ≈ O(1)	Two find operations
Build from m edges	O(m · α(n))	m union operations
Space	O(n)	Parent and rank arrays

The Inverse Ackermann Function

Comparison Summary

Choosing between approaches depends on the use case:

Scenario	Best Approach	Reasoning
Static graph, find all components	DFS/BFS	Single O(V+E) pass is optimal
Static graph, many queries	DFS/BFS + cache	Precompute component IDs
Dynamic graph, edges added	Union-Find	O(α(n)) per edge addition
Must list component members	DFS/BFS	Union-Find only stores roots
Very dense graph	Either	Both handle dense graphs well

Connectivity in Directed Graphs

Connectivity becomes significantly more nuanced in directed graphs. Because edges have direction, reachability is no longer symmetric: reaching v from u doesn't guarantee reaching u from v.

Weak vs. Strong Connectivity

Directed graphs have two types of connectivity:

Strongly Connected: A directed graph is strongly connected if for every pair of vertices u and v:

There exists a directed path from u to v, AND
There exists a directed path from v to u

Strong connectivity is a much stricter requirement. It means we can navigate from anywhere to anywhere following edge directions.

Weakly Connected Example

Consider a directed graph where:

A → B → C

We can't get from C back to A, but ignoring directions, the graph is connected. This is weakly connected but not strongly connected.

Converting Mermaid diagram...

Strongly Connected Example

Now add an edge C → A:

A → B → C → A (cycle)

Now every vertex can reach every other vertex. This is strongly connected.

Converting Mermaid diagram...

Strongly Connected Components (SCCs)

Key properties of SCCs:

The SCCs partition the vertex set (every vertex is in exactly one SCC)
The condensation graph (treating each SCC as a vertex) is always a DAG
Finding SCCs enables topological decomposition of complex graphs

Algorithms for SCCs:

Kosaraju's Algorithm: Two DFS passes (O(V + E))
Tarjan's Algorithm: Single DFS pass (O(V + E))
Path-based Algorithm: Also single DFS (O(V + E))

Direction Matters

Real-World Applications of Connectivity

Graph connectivity underlies countless real-world systems. Understanding where and how connectivity analysis applies helps you recognize it in practical problems.

Applications Across Domains

•Social Networks: Find communities within a platform; identify isolated user groups; measure how viral content can spread through the network; detect fake account clusters that aren't connected to legitimate users
•Computer Networks: Determine if all nodes can communicate; identify network partitions after failures; analyze impact of router/switch failures on connectivity; design redundant paths
•Transportation: Check if passengers can travel between any two cities; identify disconnected regions requiring new routes; analyze impact of road closures; optimize bus/train routes to maintain connectivity
•Electrical Grids: Verify all consumers are connected to power sources; identify blackout regions; design redundant power transmission paths; analyze fault tolerance
•Software Dependencies: Find modules that are completely independent; identify unused code components; detect circular dependencies through SCC analysis; plan migration strategies
•Image Processing: Connected component labeling identifies distinct objects in images; used in OCR, medical imaging, and computer vision; region segmentation relies on pixel connectivity

Case Study: Network Resilience Analysis

Consider analyzing the resilience of a computer network. Key questions include:

Current state: Is the network connected? (Single component check)
Critical nodes: Which nodes, if failed, would disconnect the network? (Articulation points)
Critical edges: Which edges, if failed, would disconnect the network? (Bridges)
Redundancy: How many independent paths exist between critical servers? (Edge/vertex connectivity)

These questions progressively build on basic connectivity to form a complete resilience analysis. Connectivity is the foundation upon which more sophisticated network analysis builds.

Interview Pattern

Common Patterns and Pitfalls

Working with graph connectivity involves recognizing common patterns and avoiding frequent mistakes. Here are the key insights gained through experience.

Best Practices

•Always validate inputs: Check for empty graphs and isolated vertices
•Handle isolated vertices: They form their own components
•Choose the right algorithm: DFS for static, Union-Find for dynamic
•Watch for directed vs undirected: Don't mix up the algorithms
•Use iterative DFS for large graphs: Avoid stack overflow
•Cache component IDs: If querying connectivity repeatedly

Common Mistakes

•Forgetting isolated vertices: They won't appear in adjacency lists
•Stack overflow on recursive DFS: Convert to iterative for large graphs
•Wrong Union-Find initialization: Must handle 0-indexed vs 1-indexed
•Applying undirected algo to directed graph: Misses directionality
•Not handling self-loops: Can confuse traversal logic
•Modifying graph during traversal: Invalidates visited state

The Isolated Vertex Trap

# Bug: isolated vertices missing
graph = {}
for u, v in edges:
    graph.setdefault(u, []).append(v)
    graph.setdefault(v, []).append(u)
# Vertex 5 with no edges is missing from graph!

# Fix: explicitly add all vertices
def build_graph(n: int, edges: list) -> dict:
    graph = {i: [] for i in range(n)}  # All vertices present
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    return graph

Always ensure your graph representation includes isolated vertices when counting components.

Summary: Mastering Graph Connectivity

Graph connectivity is a foundational concept that underlies much of graph theory and its applications. Let's consolidate what we've learned:

Key Takeaways

•A graph is connected if there's a path between every pair of vertices; otherwise, it's disconnected
•Connected components are maximal connected subgraphs that partition the vertex set
•DFS/BFS finds components in O(V + E) time by exploring from each unvisited vertex
•Union-Find supports dynamic connectivity with nearly O(1) operations using path compression and union by rank
•Directed graphs have weak and strong connectivity; SCCs decompose directed graphs into strongly connected pieces
•Real-world applications span social networks, transportation, image processing, and network resilience
•Common pitfalls include forgetting isolated vertices and using undirected algorithms on directed graphs

What's Next:

Page Complete