DFS: Connected Components and Flood Fill
Apply DFS to count connected components, solve number-of-islands on a 2D grid, and implement flood fill for image processing.
Connected Components Defined
A connected component in an undirected graph is a maximal set of vertices such that there is a path between every pair of vertices in the set. A single graph can have multiple disconnected components. Finding connected components is the foundation of many graph problems: grouping, merging, island counting, and account consolidation all reduce to this primitive.
from collections import defaultdict
# Graph with 3 components: {0,1,2}, {3,4}, {5}
graph = defaultdict(list)
for u, v in [(0,1),(0,2),(1,2),(3,4)]:
graph[u].append(v)
graph[v].append(u)
# Node 5 is isolated (no edges)
for node in [0,1,2,3,4,5]:
if node not in graph:
graph[node] = []
# We need DFS or BFS from each unvisited node
# to discover all components
print('Graph has nodes 0-5 with components: {0,1,2}, {3,4}, {5}')Counting Connected Components with DFS
Iterate over all nodes. For each unvisited node, launch a DFS to mark all reachable nodes as visited. Each DFS launch corresponds to discovering one new component. Count the number of DFS launches to get the number of components. This O(V + E) algorithm works correctly whether the graph is connected or not.
from collections import defaultdict
def count_components(n, edges):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
visited = set()
count = 0
def dfs(node):
visited.add(node)
for nb in graph[node]:
if nb not in visited:
dfs(nb)
for node in range(n):
if node not in visited:
dfs(node)
count += 1
return count
print(count_components(6, [(0,1),(0,2),(1,2),(3,4)])) # 3
print(count_components(5, [(0,1),(1,2),(3,4)])) # 2All lessons in this course
- Graph Representations and Traversal Setup
- BFS: Shortest Path and Level Traversal
- DFS: Connected Components and Flood Fill
- Cycle Detection in Directed and Undirected Graphs