DFS: yhtenäiset komponentit ja flood fill
Soveltakaa DFS:ää yhtenäisten komponenttien laskemiseen, ratkaiskaa number-of-islands kaksiulotteisessa ruudukossa ja toteuttakaa flood fill kuvankäsittelyä varten.
DFS: yhtenäiset komponentit ja flood fill on ilmainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti CoddyKitissä. Tämä on oppitunti 3/4. Voit lukea koko oppitunnin alta ilmaiseksi ja harjoitella sen jälkeen käytännössä selaimessa sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla. Oppitunti kuuluu Valmistautuminen ohjelmointihaastatteluihin-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.
Yhtenäiset komponentit
Yhtenäinen komponentti suuntaamattomassa graafissa on maksimaalinen solmujen joukko, jossa jokaisen joukkoon kuuluvan solmuparin välillä on polku. Yhdessä graafissa voi olla useita toisistaan irrallisia komponentteja. Yhtenäisten komponenttien löytäminen on monien graafitehtävien perusta: ryhmittely, yhdistäminen, saarten laskeminen ja tilien yhdistäminen voidaan kaikki pelkistää tähän perusmenetelmään.
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}')Yhtenäisten komponenttien laskeminen DFS:llä
Käykää kaikki solmut läpi. Käynnistäkää jokaisesta käymättömästä solmusta DFS, joka merkitsee kaikki saavutettavat solmut käydyiksi. Jokainen DFS:n käynnistys vastaa yhden uuden komponentin löytämistä. Komponenttien määrä saadaan laskemalla DFS:n käynnistysten lukumäärä. Tämä O(V + E) -algoritmi toimii oikein riippumatta siitä, onko graafi yhtenäinen.
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)])) # 2Number of Islands
Number of Islands (LeetCode #200) on kanoninen yhtenäisten komponenttien tehtävä kaksiulotteisessa ruudukossa. Jokainen ’1’-solu kuuluu saareen, ja vierekkäiset ’1’-solut (ylös/alas/vasemmalle/oikealle) muodostavat saman saaren. Laskekaa erillisten saarten määrä DFS:n avulla: käykää kaikki solut läpi ja käynnistäkää käymättömästä ’1’-solusta löytyessä DFS, joka merkitsee kaikki siihen yhdistyneet ’1’-solut käydyiksi (tulvatäyttö), ja kasvattakaa sitten laskuria.
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)) # 3Flood Fill -algoritmi
Flood Fill (LeetCode #733) korvaa kaikki tietystä aloitusväristä koostuvat toisiinsa yhdistyneet solut uudella värillä – aivan kuten kuvankäsittelyohjelmien maalisäiliötyökalu. Käyttäkää DFS:ää: aloittakaa lähdepikselistä ja värittäkää rekursiivisesti uudelleen kaikki naapurit, joiden väri vastaa alkuperäistä väriä. Keskeinen erikoistapaus: jos aloitussolun väri on jo sama kuin uusi väri, palatkaa heti, jotta rekursio ei jatku ikuisesti.
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]]Saaren suurin pinta-ala
Saaren suurin pinta-ala (LeetCode #695) laajentaa saarten laskentaa: tavoitteena on palauttaa suurimman saaren koko. DFS-tulvatäytön aikana lasketaan merkityt solut. DFS palauttaa nykyisen saaren koon, ja suurinta arvoa seurataan kaikkien saarten joukosta. Tämä on yhteyskomponenttikaavan yksinkertainen laajennus.
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)) # 6Veden virtaus Tyynellemerelle ja Atlantille
Veden virtaus Tyynellemerelle ja Atlantille (LeetCode #417) kysyy, mitkä solut voivat virrata sekä Tyynellemerelle (ylä- ja vasemmat reunat) että Atlantille (ala- ja oikeat reunat). Sen sijaan että simuloitaisiin veden virtaamista alaspäin, käyttäkää käänteistä DFS:ää: vesi virtaa valtameristä ylöspäin. Tehkää kaksi DFS-kierrosta — yksi Tyynenmeren reunoilta ja toinen Atlantin reunoilta — ja kerätkää saavutettavat solut. Näiden joukkojen leikkaus on vastaus.
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]]))Iteratiivinen DFS yhteyskomponenteille
Käyttäkää iteratiivista DFS:ää (jossa on eksplisiittinen pino), jotta Pythonin rekursioraja ei tule vastaan suurilla ruudukoilla. Iteratiivinen versio vastaa rekursiivista DFS:ää, mutta käyttää kutsupinon sijaan omaa pinoa. Asettakaa aloitussolmu pinoon, poistakaa solmu pinosta, merkitkää se vierailluksi ja lisätkää vierailemattomat naapurit pinoon. Näin käsittelette turvallisesti jopa miljoonien solujen ruudukoita, joissa rekursiivinen DFS aiheuttaisi pinon ylivuodon.
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)])) # 3Ympäröidyt alueet
Ympäröidyt alueet (LeetCode #130) käsittelee kaikki 'O'-alueet, jotka ovat kokonaan 'X'-reunojen ympäröimiä. Aluetta EI käsitellä, jos jokin sen 'O'-soluista koskettaa ruudukon reunaa. Ratkaisu on seuraava: sen sijaan että etsisitte ympäröityjä alueita suoraan, tehkää DFS kaikista reunan 'O'-soluista ja merkitkää kaikki saavutettavat solut turvatuiksi. Kääntäkää tämän jälkeen arvot: kaikki jäljelle jäävät 'O'-solut ovat ympäröityjä ja muutetaan 'X'-soluiksi, kun taas turvatut solut palautetaan 'O'-soluiksi.
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, OAli-saarten laskeminen
Ali-saarten laskeminen (LeetCode #1905) etsii grid2:n saaret, jotka ovat kokonaan grid1:n saaren sisällä. Aloittakaa DFS jokaisesta grid2:n '1'-solusta: saari on alisaari, jos jokainen sen käsittelemä solu on myös grid1:ssä '1'. Ratkaisu on seuraava: käsitelkää saaren kaikki solut, jotta ne merkitään tutkituiksi, mutta seuratkaa samalla, ovatko ne kaikki myös grid1:ssä '1'. Älkää lopettako käsittelyä ensimmäiseen grid1:n '0':aan — muuten saman saaren muiden solujen merkitseminen jäisi tekemättä.
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 ja BFS yhteyskomponenteille
Sekä DFS että BFS löytävät kaikki yhteyskomponentit oikein, ja niiden aikavaativuus on O(V + E) ja tilavaativuus O(V). DFS on helpompi toteuttaa rekursiivisesti yhteyskomponenttiongelmissa, kun taas BFS:ää suositaan, kun tarvitaan myös lyhimmän polun tietoja. Ruudukko-ongelmissa DFS hyödyntää välimuistia paremmin, koska se etenee syvälle yhteen suuntaan ennen paluuta ja käsittelee peräkkäisiä muistipaikkoja.
# 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')Rajoitteiden alaiset saaret: muodot ja piirit
Saaren piiri (LeetCode #463) laskee ruudukon ainoan saaren koko piirin. Jokaisesta maasolusta ('1') lisätään piiriin 4, minkä jälkeen vähennetään 2 jokaisesta viereisestä maasolusta (jaetut reunat). Tämä O(mn)-aikainen kaavapohjainen menetelmä ei tarvitse DFS:ää — mutta sen ymmärtäminen, että menetelmä vastaa DFS:ää, joka laskee rajareunat, vahvistaa ruudukko-ongelmien ja graafiajattelun välistä yhteyttä.
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)) # 16Pikatarkistus
Testatkaa, miten hyvin hallitsette tämän oppitunnin Data Structures & Algorithms — Coding Interview Prep -aiheen käsitteet.
Oppitunnin yhteenveto
Tässä oppitunnissa opitte: yhteyskomponentit DFS:n ja vierailujen seurannan avulla, saarten laskemisen ja tulvatäytön kaksiulotteisten ruudukoiden perussovelluksina sekä edistyneitä malleja, kuten käänteinen DFS reunoilta (ympäröidyt alueet) ja usean DFS:n käyttö rajoitteiden seurannassa (alisaaret). Seuraavaksi käsittelemme syklien tunnistamista suunnatuissa ja suuntaamattomissa graafeissa.
Opi Valmistautuminen ohjelmointihaastatteluihin tekoälytuutorin avulla — ilmaiseksi
Kirjoita ja suorita oikeaa koodia selaimessa, saa välitöntä apua tekoälytuutorilta ympäri vuorokauden ja jatka siitä, mihin jäit, verkossa tai sovelluksessa.
- Kurssit
- 90
- Oppitunnit
- 360
Usein kysytyt kysymykset
Onko oppitunti ”DFS: yhtenäiset komponentit ja flood fill” ilmainen?
Kyllä – oppitunnin ”DFS: yhtenäiset komponentit ja flood fill” koko tekstin voi lukea täällä verkossa ilmaiseksi. Jos haluat harjoitella interaktiivisesti sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla sekä avata koko Valmistautuminen ohjelmointihaastatteluihin-kurssin, päivitä CoddyKit PROhon. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.
Mitä opin oppitunnilla ”DFS: yhtenäiset komponentit ja flood fill”?
Soveltakaa DFS:ää yhtenäisten komponenttien laskemiseen, ratkaiskaa number-of-islands kaksiulotteisessa ruudukossa ja toteuttakaa flood fill kuvankäsittelyä varten. Harjoittelet Valmistautuminen ohjelmointihaastatteluihin-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.
Tarvitsenko kokemusta aloittaakseni Valmistautuminen ohjelmointihaastatteluihin-opiskelun?
Aiempi kokemus ei ole tarpeen. CoddyKitin Valmistautuminen ohjelmointihaastatteluihin-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 3/4.
Kuinka kauan ”DFS: yhtenäiset komponentit ja flood fill”-oppitunnin suorittaminen kestää?
Useimmat CoddyKitin oppitunnit kestävät noin 5–10 minuuttia. Jokainen oppitunti on lyhyt ja interaktiivinen, joten edistyt tasaisesti ja voit jatkaa siitä, mihin jäit – sekä verkossa että sovelluksessa.
Voinko kirjoittaa ja suorittaa koodia tällä Valmistautuminen ohjelmointihaastatteluihin-oppitunnilla?
Kyllä. Jokainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti sisältää sisäänrakennetun koodieditorin, joten voit kirjoittaa ja suorittaa oikeaa koodia suoraan selaimessa ja saada välitöntä palautetta tekoälyltä – paikallista asennusta ei tarvita.
Kaikki tämän kurssin oppitunnit
- Graafien esitystavat ja läpikäyntien valmistelu
- BFS: lyhin polku ja tasoläpikäynti
- DFS: yhtenäiset komponentit ja flood fill
- Syklien tunnistaminen suunnatuissa ja suuntaamattomissa graafeissa