DFS: Komponen Terhubung dan Flood Fill
Terapkan DFS untuk menghitung komponen terhubung, selesaikan number-of-islands pada grid 2D, dan implementasikan flood fill untuk pemrosesan citra.
DFS: Komponen Terhubung dan Flood Fill adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 3 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Definisi Komponen Terhubung
Sebuah komponen terhubung dalam graf tak berarah adalah himpunan maksimal simpul yang memiliki jalur antara setiap pasangan simpul dalam himpunan tersebut. Satu graf dapat memiliki beberapa komponen yang tidak saling terhubung. Menemukan komponen terhubung merupakan dasar bagi banyak soal graf: pengelompokan, penggabungan, penghitungan pulau, dan konsolidasi akun semuanya dapat direduksi menjadi operasi dasar ini.
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}')Menghitung Komponen Terhubung dengan DFS
Telusuri semua simpul. Untuk setiap simpul yang belum dikunjungi, mulai DFS untuk menandai semua simpul yang dapat dicapainya sebagai telah dikunjungi. Setiap kali DFS dimulai, berarti ditemukan satu komponen baru. Hitung jumlah dimulainya DFS untuk memperoleh jumlah komponen. Algoritma O(V + E) ini bekerja dengan benar baik pada graf yang terhubung maupun yang tidak.
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)])) # 2Jumlah Pulau
Jumlah Pulau (LeetCode #200) adalah soal komponen terhubung kanonis pada kisi 2D. Setiap sel '1' termasuk dalam sebuah pulau; sel '1' yang bersebelahan (atas/bawah/kiri/kanan) membentuk pulau yang sama. Hitung jumlah pulau yang berbeda menggunakan DFS: telusuri semua sel, dan ketika menemukan '1' yang belum dikunjungi, mulai DFS yang menandai semua sel '1' yang terhubung (pengisian area), lalu tambah penghitungnya.
def num_islands(grid):
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
count = 0
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols:
return
if grid[r][c] != '1':
return
grid[r][c] = '#' # mark visited in-place
dfs(r+1,c); dfs(r-1,c)
dfs(r,c+1); dfs(r,c-1)
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
dfs(r, c)
count += 1
return count
grid = [['1','1','0','0','0'],
['1','1','0','0','0'],
['0','0','1','0','0'],
['0','0','0','1','1']]
print(num_islands(grid)) # 3Algoritma Pengisian Area
Pengisian Area (LeetCode #733) mengganti semua sel terhubung yang memiliki warna awal tertentu dengan warna baru—persis seperti alat ember cat pada penyunting gambar. Gunakan DFS: mulai dari piksel sumber, lalu secara rekursif warnai ulang semua tetangga yang memiliki warna awal yang sama. Kasus khusus yang penting: jika warna sel awal sudah sama dengan warna baru, segera berhenti untuk mencegah rekursi tak terbatas.
def flood_fill(image, sr, sc, new_color):
original = image[sr][sc]
if original == new_color:
return image # edge case: same color, nothing to do
rows, cols = len(image), len(image[0])
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols:
return
if image[r][c] != original:
return
image[r][c] = new_color
dfs(r+1,c); dfs(r-1,c)
dfs(r,c+1); dfs(r,c-1)
dfs(sr, sc)
return image
image = [[1,1,1],[1,1,0],[1,0,1]]
result = flood_fill(image, 1, 1, 2)
for row in result: print(row)
# [[2,2,2],[2,2,0],[2,0,1]]Luas Maksimum Pulau
Luas Maksimum Pulau (LeetCode #695) memperluas penghitungan pulau: untuk setiap pulau, kembalikan ukuran pulau yang terbesar. Selama pengisian area dengan DFS, hitung sel yang Anda tandai. DFS mengembalikan ukuran pulau saat ini, dan Anda melacak nilai maksimum di antara semua pulau. Ini adalah perluasan sederhana dari pola komponen terhubung.
def max_area_of_island(grid):
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
max_area = 0
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols:
return 0
if grid[r][c] != 1:
return 0
grid[r][c] = 0 # mark visited
return (1 + dfs(r+1,c) + dfs(r-1,c) +
dfs(r,c+1) + dfs(r,c-1))
for r in range(rows):
for c in range(cols):
if grid[r][c] == 1:
max_area = max(max_area, dfs(r, c))
return max_area
grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,1,1,0,1,0,0,0,0,0,0,0,0],
[0,1,0,0,1,1,0,0,1,0,1,0,0]]
print(max_area_of_island(grid)) # 6Aliran Air Pasifik-Atlantik
Aliran Air Pasifik-Atlantik (LeetCode #417) menanyakan sel mana yang airnya dapat mengalir ke kedua samudra, yaitu Pasifik (tepi atas/kiri) dan Atlantik (tepi bawah/kanan). Alih-alih menyimulasikan air yang mengalir turun, gunakan DFS terbalik: air mengalir naik dari samudra. Lakukan dua penelusuran DFS — satu dari perbatasan Pasifik dan satu dari perbatasan Atlantik — sambil mengumpulkan sel yang dapat dijangkau. Irisannya adalah jawabannya.
def pacific_atlantic(heights):
rows, cols = len(heights), len(heights[0])
pac = set(); atl = set()
def dfs(r, c, visited, prev_h):
if (r,c) in visited or r < 0 or r >= rows or c < 0 or c >= cols:
return
if heights[r][c] < prev_h:
return # water can't flow uphill in reverse
visited.add((r,c))
for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
dfs(r+dr, c+dc, visited, heights[r][c])
for r in range(rows):
dfs(r, 0, pac, heights[r][0]) # Pacific left
dfs(r, cols-1, atl, heights[r][cols-1]) # Atlantic right
for c in range(cols):
dfs(0, c, pac, heights[0][c]) # Pacific top
dfs(rows-1, c, atl, heights[rows-1][c]) # Atlantic bottom
return sorted(pac & atl) # intersection
print(pacific_atlantic([[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]))DFS Iteratif untuk Komponen Terhubung
Gunakan DFS iteratif (dengan tumpukan eksplisit) untuk menghindari batas rekursi Python pada kisi berukuran besar. Versi iteratif setara dengan DFS rekursif, tetapi menggunakan tumpukan alih-alih tumpukan pemanggilan. Masukkan simpul awal, lalu pop, tandai sebagai telah dikunjungi, dan masukkan tetangga yang belum dikunjungi. Cara ini menangani kisi hingga jutaan sel dengan aman, sedangkan DFS rekursif dapat menyebabkan luapan tumpukan.
def count_components_iterative(n, edges):
from collections import defaultdict
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
visited = set()
count = 0
for start in range(n):
if start in visited:
continue
# Iterative DFS
stack = [start]
while stack:
node = stack.pop()
if node in visited:
continue
visited.add(node)
for nb in graph[node]:
if nb not in visited:
stack.append(nb)
count += 1
return count
print(count_components_iterative(6, [(0,1),(0,2),(1,2),(3,4)])) # 3Wilayah yang Dikelilingi
Wilayah yang Dikelilingi (LeetCode #130) menangkap semua wilayah 'O' yang sepenuhnya dikelilingi oleh batas 'X'. Suatu wilayah TIDAK ditangkap jika salah satu sel 'O'-nya menyentuh tepi papan. Triknya: alih-alih mencari wilayah yang dikelilingi secara langsung, lakukan DFS dari semua sel 'O' di perbatasan dan tandai semua yang dapat dijangkau sebagai aman. Kemudian balikkan: semua sel 'O' yang tersisa dikelilingi dan menjadi 'X', sedangkan sel yang aman dikembalikan menjadi 'O'.
def solve(board):
if not board:
return
rows, cols = len(board), len(board[0])
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols:
return
if board[r][c] != 'O':
return
board[r][c] = 'S' # safe: connected to border
dfs(r+1,c); dfs(r-1,c)
dfs(r,c+1); dfs(r,c-1)
# Mark border-connected O's as safe
for r in range(rows):
dfs(r, 0); dfs(r, cols-1)
for c in range(cols):
dfs(0, c); dfs(rows-1, c)
# Flip: surrounded O -> X, safe S -> O
for r in range(rows):
for c in range(cols):
if board[r][c] == 'O': board[r][c] = 'X'
elif board[r][c] == 'S': board[r][c] = 'O'
board = [['X','X','X','X'],['X','O','O','X'],
['X','X','O','X'],['X','O','X','X']]
solve(board)
print([board[1][1], board[3][1]]) # X, OHitung Sub-Pulau
Hitung Sub-Pulau (LeetCode #1905) mencari pulau di grid2 yang seluruhnya berada di dalam sebuah pulau di grid1. Lakukan DFS dari setiap sel '1' di grid2: sebuah pulau merupakan sub-pulau jika setiap sel yang dikunjunginya juga bernilai '1' di grid1. Triknya: kunjungi ALL sel di pulau tersebut (untuk menandainya sebagai telah ditelusuri), tetapi lacak apakah ALL sel itu juga bernilai '1' di grid1. Jangan berhenti lebih awal saat menemukan '0' pertama di grid1 — Anda akan melewatkan penandaan sel lain dari pulau yang sama.
def count_sub_islands(grid1, grid2):
rows, cols = len(grid2), len(grid2[0])
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols:
return True
if grid2[r][c] != 1:
return True
grid2[r][c] = 0 # mark visited
is_sub = grid1[r][c] == 1 # this cell must be in grid1
is_sub = dfs(r+1,c) and is_sub # note: AND not short-circuit OR
is_sub = dfs(r-1,c) and is_sub
is_sub = dfs(r,c+1) and is_sub
is_sub = dfs(r,c-1) and is_sub
return is_sub
count = 0
for r in range(rows):
for c in range(cols):
if grid2[r][c] == 1 and dfs(r, c):
count += 1
return count
print(count_sub_islands([[1,1,1],[1,0,1],[1,1,1]],
[[1,1,1],[1,0,1],[1,1,1]])) # 1DFS dibandingkan dengan BFS untuk Komponen Terhubung
DFS dan BFS sama-sama menemukan semua komponen terhubung dengan kompleksitas waktu O(V + E) dan ruang O(V) yang sama. DFS lebih sederhana untuk diterapkan secara rekursif pada masalah komponen terhubung, sedangkan BFS lebih disukai jika Anda juga memerlukan informasi jalur terpendek. Dalam masalah kisi, DFS lebih ramah terhadap tembolok karena menjelajah jauh ke satu arah sebelum mundur, sehingga mengakses lokasi memori yang berdekatan secara berurutan.
# DFS advantages for connected components:
# - Simpler recursive implementation
# - Lower constant factor for small graphs
# - Can restore grid state during backtracking (if needed)
# BFS advantages:
# - Finds shortest path while traversing
# - Better for wide, shallow graphs (avoids deep recursion)
# - Multi-source initialisation is natural
# Same asymptotic complexity: O(V + E) time, O(V) space
# Grid (m rows, n cols): O(mn) time and space
print('DFS and BFS: same O(V+E) complexity for component counting')Pulau dengan Batasan: Bentuk dan Keliling
Keliling Pulau (LeetCode #463) menghitung total keliling satu-satunya pulau dalam sebuah kisi. Untuk setiap sel daratan ('1'), lakukan add 4 pada keliling, lalu kurangi 2 untuk setiap sel daratan yang bersebelahan (sisi yang digunakan bersama). Pendekatan berbasis rumus O(mn) ini tidak memerlukan DFS — tetapi memahami bahwa pendekatan ini setara dengan DFS yang menghitung sisi batas memperkuat hubungan antara masalah kisi dan penalaran graf.
def island_perimeter(grid):
rows, cols = len(grid), len(grid[0])
perimeter = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == 1:
perimeter += 4 # start with 4 sides
# Subtract shared edges with adjacent land cells
if r > 0 and grid[r-1][c] == 1:
perimeter -= 2 # shared top edge
if c > 0 and grid[r][c-1] == 1:
perimeter -= 2 # shared left edge
return perimeter
grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
print(island_perimeter(grid)) # 16Uji Cepat
Uji pemahaman Anda tentang konsep Struktur Data & Algoritma — Persiapan Wawancara Pemrograman dari pelajaran ini.
Ringkasan Pelajaran
Dalam pelajaran ini Anda mempelajari: komponen terhubung melalui DFS dengan pelacakan kunjungan, jumlah pulau dan pengisian area sebagai penerapan klasik pada kisi 2D, serta pola lanjutan seperti DFS terbalik dari perbatasan (wilayah yang dikelilingi) dan DFS ganda dengan pelacakan batasan (sub-pulau). Berikutnya kita akan membahas deteksi siklus dalam graf berarah dan tak berarah.
Pertanyaan yang Sering Diajukan
Apakah pelajaran “DFS: Komponen Terhubung dan Flood Fill” gratis?
Ya — teks lengkap “DFS: Komponen Terhubung dan Flood Fill” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Coding Interview Prep, upgrade ke CoddyKit PRO. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “DFS: Komponen Terhubung dan Flood Fill”?
Terapkan DFS untuk menghitung komponen terhubung, selesaikan number-of-islands pada grid 2D, dan implementasikan flood fill untuk pemrosesan citra. Kamu berlatih Coding Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai Coding Interview Prep?
Tidak diperlukan pengalaman sebelumnya. Coding Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 3 dari 4.
Berapa lama pelajaran “DFS: Komponen Terhubung dan Flood Fill” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran Coding Interview Prep ini?
Ya. Setiap pelajaran Coding Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- Representasi Graf dan Persiapan Traversal
- BFS: Jalur Terpendek dan Traversal Level
- DFS: Komponen Terhubung dan Flood Fill
- Deteksi Siklus pada Graf Berarah dan Tak Berarah