Analytics Vidhya
Published in

Analytics Vidhya

BFS, DFS and Union Find

I am going to show the connections between BFS(Breadth First Search), DFS(Depth First Search) and Union Find by one example.

The example is one question from leetcode.

The problem is 1263. Minimum Moves to Move a Box to Their Target Location

https://leetcode.com/problems/minimum-moves-to-move-a-box-to-their-target-location/

It is a hard problem. The reason that it is hard is it contains two BFSs.

The solution to this problem can be: BFS + BFS or BFS + DFS or BFS + Union Find

Solution 1(BFS + BFS, runtime 160ms)

Solution 1 improved BFS + BFS by using deque (116 ms)

Solution 2(BFS + DFS runtime 632 ms)

class Solution:
def minPushBox(self, grid: List[List[str]]) -> int:
R, C = len(grid), len(grid[0])
for i in range(R):
for j in range(C):
if grid[i][j] == 'S':
pi, pj = i, j
elif grid[i][j] == 'B':
bi, bj = i, j

def dfs_person(i, j, ti, tj, bi, bj):
seen = set()
if ti>=R or tj>=C or grid[ti][tj]=='#':return False
open_list = [(i,j)]
while open_list:
i,j = open_list.pop()
if (i,j)==(ti,tj):return True
seen.add((i, j))
for di, dj in [(1, 0),(-1, 0), (0, 1), (0, -1)]:
r, c = i+di, j+dj
if 0<=r<R and 0<=c<C and (r,c)!=(bi,bj) and (r,c) not in seen and grid[r][c]!='#':
open_list.append((r,c))
return False


def bfs(i, j, pi, pj):
b_seen = set()
cur_level = {(i,j, pi, pj, 0)}
while cur_level:
nxt_level = set()
for i, j, pi, pj, d in cur_level:
b_seen.add((i,j, pi, pj))
if grid[i][j] == 'T':return d
for di, dj in [(1, 0),(-1, 0), (0, 1), (0, -1)]:
r, c = i+di, j+dj
if 0<=r<R and 0<=c<C and grid[r][c]!='#' and (r,c, i, j) not in b_seen:
ti, tj = i-di, j-dj
if dfs_person(pi, pj, ti, tj, i, j):
nxt_level.add((r,c,i, j, d+1))
cur_level = nxt_level
return -1
return bfs(bi, bj, pi, pj)

Solution 3(BFS + Union Find runtime1608 ms)

class Solution:
def minPushBox(self, grid: List[List[str]]) -> int:
R, C = len(grid), len(grid[0])
self.uf = {}
for i in range(R):
for j in range(C):
if grid[i][j] == 'S':
pi, pj = i, j
elif grid[i][j] == 'B':
bi, bj = i, j
def find(x):
self.uf.setdefault(x, x)
if self.uf[x] != x:
self.uf[x] = find(self.uf[x])
return self.uf[x]

def union(x, y):
self.uf[find(y)] = find(x)

def union_find(i, j, bi, bj):
open_list = [(i,j)]
seen = set()
while open_list:
i,j = open_list.pop()
seen.add((i, j))
for di, dj in [(1, 0),(-1, 0), (0, 1), (0, -1)]:
r, c = i+di, j+dj
if 0<=r<R and 0<=c<C and (r,c)!=(bi,bj) and (r,c) not in seen and grid[r][c]!='#':
union((i, j), (r, c))
open_list.append((r, c))

def bfs(i, j, pi, pj):
b_seen = set()
cur_level = {(i,j, pi, pj, 0)}
while cur_level:
nxt_level = set()
for i, j, pi, pj, d in cur_level:
b_seen.add((i,j, pi, pj))
if grid[i][j] == 'T':return d
children = [(i+di, j+dj, i-di, j-dj)
for di, dj in [(1, 0),(-1, 0), (0, 1), (0, -1)]
if 0<=i+di<R and 0<=j+dj<C and grid[i+di][j+dj]!='#' and (i+di, j+dj, i, j) not in b_seen]
if children:
self.uf = {}
union_find(pi, pj , i, j)
for r, c, ti, tj in children:
if find((ti, tj)) == find((pi, pj)):
nxt_level.add((r,c,i, j, d+1))
cur_level = nxt_level
return -1
return bfs(bi, bj, pi, pj)

Solution 4(BFS + DFS TLE) The reason that this solution is TLE might be the open_list size is too large if we keep all levels elements in the whole list. Solution 2 compares with this solution, only the open_list part is changed to only maintain the current level and next level. The speed of solution 2 is much faster and can get accepted.

class Solution:
def minPushBox(self, grid: List[List[str]]) -> int:
R, C = len(grid), len(grid[0])
for i in range(R):
for j in range(C):
if grid[i][j] == 'S':
pi, pj = i, j
elif grid[i][j] == 'B':
bi, bj = i, j

def dfs_person(i, j, ti, tj, bi, bj):
seen = set()
if ti>=R or tj>=C or grid[ti][tj]=='#':return False
open_list = [(i,j)]
while open_list:
i,j = open_list.pop()
if (i,j)==(ti,tj):return True
seen.add((i, j))
for di, dj in [(1, 0),(-1, 0), (0, 1), (0, -1)]:
r, c = i+di, j+dj
if 0<=r<R and 0<=c<C and (r,c)!=(bi,bj) and (r,c) not in seen and grid[r][c]!='#':
open_list.append((r,c))
return False

def bfs(i, j, pi, pj):
b_seen = set()
open_list = [(i,j, pi, pj, 0)]
for i, j, pi, pj, d in open_list:
b_seen.add((i,j, pi, pj))
if grid[i][j] == 'T':return d
for di, dj in [(1, 0),(-1, 0), (0, 1), (0, -1)]:
r, c = i+di, j+dj
if 0<=r<R and 0<=c<C and grid[r][c]!='#' and (r,c, i, j) not in b_seen:
ti, tj = i-di, j-dj
if dfs_person(pi, pj, ti, tj, i, j):
open_list.append((r,c,i, j, d+1))
return -1
return bfs(bi, bj, pi, pj)

Actually solution 4 get TLE is not because of the large open_list size. The reason is too many duplicated value is put into the open list. When changing the code to the following one, it works and runtime is 348 ms.

Solution 5 (BFS + DFS return a seen set 788 ms) It seems in this case union find is slower than DFS.

class Solution:
def minPushBox(self, grid: List[List[str]]) -> int:
R, C = len(grid), len(grid[0])
for i in range(R):
for j in range(C):
if grid[i][j] == 'S':
pi, pj = i, j
elif grid[i][j] == 'B':
bi, bj = i, j

def dfs_person(i, j, bi, bj):
seen = set()
open_list = [(i,j)]
while open_list:
i,j = open_list.pop()
seen.add((i, j))
for di, dj in [(1, 0),(-1, 0), (0, 1), (0, -1)]:
r, c = i+di, j+dj
if 0<=r<R and 0<=c<C and (r,c)!=(bi,bj) and (r,c) not in seen and grid[r][c]!='#':
open_list.append((r,c))
return seen

def bfs(i, j, pi, pj):
b_seen = set()
cur_level = {(i,j, pi, pj, 0)}
while cur_level:
nxt_level = set()
for i, j, pi, pj, d in cur_level:
b_seen.add((i,j, pi, pj))
if grid[i][j] == 'T':return d
children = [(i+di, j+dj, i-di, j-dj)
for di, dj in [(1, 0),(-1, 0), (0, 1), (0, -1)]
if 0<=i+di<R and 0<=j+dj<C and grid[i+di][j+dj]!='#' and (i+di, j+dj, i, j) not in b_seen]
if children:
seen = dfs_person(pi, pj , i, j)
for r, c, ti, tj in children:
if (pi, pj) in seen and (ti, tj ) in seen:
nxt_level.add((r,c,i, j, d+1))
cur_level = nxt_level
return -1
return bfs(bi, bj, pi, pj)

Solution 6 (BFS + DFS change data type of open_list for DFS from list to set runtime 192 ms) No idea why it can have such a significant speedup. The appending, traversing and pop speed between list and set should not be that much. Still unclear about this part.

class Solution:
def minPushBox(self, grid: List[List[str]]) -> int:
R, C = len(grid), len(grid[0])
for i in range(R):
for j in range(C):
if grid[i][j] == 'S':
pi, pj = i, j
elif grid[i][j] == 'B':
bi, bj = i, j

def dfs_person(i, j, ti, tj, bi, bj):
seen = set()
if ti>=R or tj>=C or grid[ti][tj]=='#':return False
open_list = {(i,j)}
while open_list:
i,j = open_list.pop()
if (i,j)==(ti,tj):return True
seen.add((i, j))
for di, dj in [(1, 0),(-1, 0), (0, 1), (0, -1)]:
r, c = i+di, j+dj
if 0<=r<R and 0<=c<C and (r,c)!=(bi,bj) and (r,c) not in seen and grid[r][c]!='#':
open_list.add((r,c))
return False


def bfs(i, j, pi, pj):
b_seen = set()
cur_level = {(i,j, pi, pj, 0)}
while cur_level:
nxt_level = set()
for i, j, pi, pj, d in cur_level:
b_seen.add((i,j, pi, pj))
if grid[i][j] == 'T':return d
for di, dj in [(1, 0),(-1, 0), (0, 1), (0, -1)]:
r, c = i+di, j+dj
if 0<=r<R and 0<=c<C and grid[r][c]!='#' and (r,c, i, j) not in b_seen:
ti, tj = i-di, j-dj
if dfs_person(pi, pj, ti, tj, i, j):
nxt_level.add((r,c,i, j, d+1))
cur_level = nxt_level
return -1
return bfs(bi, bj, pi, pj)

From this post, hope the reader can have a better understanding of the difference and connections between BFS, DFS, and union-find.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Jimmy Shen

Jimmy Shen

Data Scientist/MLE/SWE @takemobi