通過這個問題把BFS、DFS、并查集的一些思路和程序主體模板進行一下總結。
其中BFS和DFS屬于最基本最容易直接觀察的，并查集屬于最容易理解的。本題來自LeetCode200.島嶼數(shù)量；思路搬運自題解區(qū)第二條“l(fā)iweiwei1419”大神，代碼部分參考自題解區(qū)第三條“powcai”大神。
作者：liweiwei1419
鏈接：https://leetcode-cn.com/problems/number-of-islands/solution/dfs-bfs-bing-cha-ji-python-dai-ma-java-dai-ma-by-l/
作者：powcai
鏈接：https://leetcode-cn.com/problems/number-of-islands/solution/dfs-bfs-bing-cha-ji-chao-ji-qing-xi-by-powcai/
1.DFS
原題解作者引出了一個非常形象的解釋，就是洪水，或者感染，我們對整片區(qū)域進行遍歷，如果找到了一塊陸地，先計數(shù)加1，代表我們已經(jīng)發(fā)現(xiàn)了一塊新大陸，然后我們找到與這塊大陸相連的區(qū)域，并將之前發(fā)現(xiàn)的大陸給淹沒，然后再對新發(fā)現(xiàn)的大陸進行相同的操作直至沒有新大陸被發(fā)現(xiàn)了，代表我們已經(jīng)處理完一整塊海島了，最后的計數(shù)就是題中所要求的的海島數(shù)目，而我們所說的這個“洪水”或者“感染”就是一個DFS深度遍歷的過程。
按照上面的思路，我們先把感染的函數(shù)，也就是DFS的模板給寫出來。
def dfs(i, j):
grid[i][j] = "0" #先將當前大陸淹沒
for x, y in [[-1, 0], [1, 0], [0, -1], [0, 1]]: #然后檢查它的四周
tmp_i = i + x
tmp_j = j + y
if 0 <= tmp_i < row and 0 <= tmp_j < col and grid[tmp_i][tmp_j] == "1":
#如果它的四周也有大陸，則對它的四周進行相同操作
dfs(tmp_i, tmp_j)
然后再對整片區(qū)域進行遍歷即可，因為我們檢查到一個“1”之后會把與它同為海島的所有區(qū)域全部置“0”，所以我們每發(fā)現(xiàn)一次1都屬于獨立的新大陸。
整段代碼如下：
def numIslands(self, grid: List[List[str]]) -> int:
if not grid:
return 0
row = len(grid)
col = len(grid[0])
def dfs(i,j):
grid[i][j] = '0'
for r,c in[(i-1,j),(i,j+1),(i+1,j),(i,j-1)]:
if 0<=r<row and 0<=c<col and grid[r][c] == '1':
dfs(r,c)
res = 0
for i in range(row):
for j in range(col):
if grid[i][j] == '1':
dfs(i,j)
res += 1
return res
2.BFS
廣度遍歷就是需要借助一個隊列來完成相關功能，用一個集合來存儲所有被遍歷過的點，那么當我們發(fā)現(xiàn)一個點為“1”且不在集合中，我們就可以啟動廣度遍歷，具體來說就是檢查這個點四周的所有點，如果與它相連接的點未被遍歷，則加入到隊列中待遍歷，且加入集合seen中被標記為已遍歷狀態(tài)。
BFS代碼如下
def bfs(i,j):
seen.add((i,j))
queue.append([i,j])
while queue:
node = queue.pop(0)
nr,nc = node[0],node[1]
for r,c in [(nr-1,nc),(nr,nc+1),(nr+1,nc),(nr,nc-1)]:
if 0<=r<row and 0<=c<col and grid[r][c] == '1' and (r,c) not in seen:
seen.add((r,c))
queue.append([r,c])
整體代碼如下,BFS是我自己寫的，又臭又長QAQ......
def numIslands(self, grid: List[List[str]]) -> int:
if not grid:
return 0
row = len(grid)
col = len(grid[0])
seen = set()
queue = []
def bfs(i,j):
seen.add((i,j))
queue.append([i,j])
while queue:
node = queue.pop(0)
nr,nc = node[0],node[1]
for r,c in [(nr-1,nc),(nr,nc+1),(nr+1,nc),(nr,nc-1)]:
if 0<=r<row and 0<=c<col and grid[r][c] == '1' and (r,c) not in seen:
seen.add((r,c))
queue.append([r,c])
res = 0
for i in range(row):
for j in range(col):
if grid[i][j] == '1' and (i,j) not in seen:
bfs(i,j)
res += 1
return res
3.并查集
并查集的思路我之前的一篇文章里面已經(jīng)寫了，主要有兩個操作，一個是尋找最原始的祖先結點，一個是連接結點的操作，只有兩個節(jié)點的原始祖先結點不相同時才連接，否則的話它們本身就已經(jīng)屬于同一個圈子里面了。
尋找祖先結點函數(shù)
def find_fa(node):
temp = node
#只要這個結點不是原始結點就一直往上搜尋
while parent[temp] != -1:
temp = parent[temp]
return temp
連接操作
def connect(node1,node2):
node1 = find_pa(node1)
node2 = find_pa(node2)
#對于無向圖，把誰當做誰的父節(jié)點都無所謂
if node1 != node2:
parent[node1] = node2
用并查集做處理的話，就只需要檢查每個點的右邊和下面然后決定是否連接即可。
記住要把延伸出來的“1”結點掛在原結點上,這樣比較好理解
例如（i,j）有一個結點（i，j+1）
我們應該讓（i,j+1）的父節(jié)點等于（i,j）
parent[i*col+j+1] = i*col+j
然后還應注意把所有的水域都連接到一個虛擬的節(jié)點上，即讓水域的父節(jié)點等于-2。
最后統(tǒng)計parent數(shù)組中-1的個數(shù)即可
這一塊我也是按照自己習慣的方式寫了下，速度比DFS和BFS都稍微快一點。
def numIslands(self, grid: List[List[str]]) -> int:
if not grid:
return 0
row = len(grid)
col = len(grid[0])
parent = [-1]*row*col
def find_fa(i,j):
node = i*col + j
while parent[node] != -1:
node = parent[node]
return node
def connect(i1,j1,i2,j2):
node1 = find_fa(i1,j1)
node2 = find_fa(i2,j2)
if node1 != node2:
parent[node2] = node1
for i in range(row):
for j in range(col):
if grid[i][j] == '1':
for r,c in [(i,j+1),(i+1,j)]:
if 0<=r<row and 0<=c<col and grid[r][c] == '1':
connect(i,j,r,c)
elif grid[i][j] == '0':
parent[i*col+j] = -2
res = 0
for item in parent:
if item == -1:
res += 1
return res
