通过这个问题把BFS、DFS、并查集的一些思路和程序主体模板进行一下总结。
其中BFS和DFS属于最基本最容易直接观察的，并查集属于最容易理解的。本题来自LeetCode200.岛屿数量；思路搬运自题解区第二条“liweiwei1419”大神，代码部分参考自题解区第三条“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
原题解作者引出了一个非常形象的解释，就是洪水，或者感染，我们对整片区域进行遍历，如果找到了一块陆地，先计数加1，代表我们已经发现了一块新大陆，然后我们找到与这块大陆相连的区域，并将之前发现的大陆给淹没，然后再对新发现的大陆进行相同的操作直至没有新大陆被发现了，代表我们已经处理完一整块海岛了，最后的计数就是题中所要求的的海岛数目，而我们所说的这个“洪水”或者“感染”就是一个DFS深度遍历的过程。
按照上面的思路，我们先把感染的函数，也就是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)
然后再对整片区域进行遍历即可，因为我们检查到一个“1”之后会把与它同为海岛的所有区域全部置“0”，所以我们每发现一次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
广度遍历就是需要借助一个队列来完成相关功能，用一个集合来存储所有被遍历过的点，那么当我们发现一个点为“1”且不在集合中，我们就可以启动广度遍历，具体来说就是检查这个点四周的所有点，如果与它相连接的点未被遍历，则加入到队列中待遍历，且加入集合seen中被标记为已遍历状态。
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.并查集
并查集的思路我之前的一篇文章里面已经写了，主要有两个操作，一个是寻找最原始的祖先结点，一个是连接结点的操作，只有两个节点的原始祖先结点不相同时才连接，否则的话它们本身就已经属于同一个圈子里面了。
寻找祖先结点函数
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)
#对于无向图，把谁当做谁的父节点都无所谓
if node1 != node2:
parent[node1] = node2
用并查集做处理的话，就只需要检查每个点的右边和下面然后决定是否连接即可。
记住要把延伸出来的“1”结点挂在原结点上,这样比较好理解
例如（i,j）有一个结点（i，j+1）
我们应该让（i,j+1）的父节点等于（i,j）
parent[i*col+j+1] = i*col+j
然后还应注意把所有的水域都连接到一个虚拟的节点上，即让水域的父节点等于-2。
最后统计parent数组中-1的个数即可
这一块我也是按照自己习惯的方式写了下，速度比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
网友评论