Two examples of DFS/BFS graph traversal
The two LeetCode problems that we are going to discuss are similar because they both can be solved by DFS or BFS algorithms, but different because the input matrices are a connectivity matrix vs. an island matrix.
Example 1:
Each cell in the matrix represents an edge. Given the condition, then x n matrix isConnected where isConnected[i][j] = 1 if the ith city and the jth city are directly connected, and isConnected[i][j] = 0 otherwise. It is obvious that the diagonal cells of the square matrix are all with value 1 and the matrix is a symmetric matrix that is equal to its transpose.
The provinces (vertices) can be indexed as [0, …, n-1]. As there could be an edge between any pair of the vertices, we’ll have to loop through vertex i and vertex j to access all edges provided in the input matrix.
In this circumstance, we start from the vertex 0 and check the connectivity of this vertex with all vertices, including itself for simplicity, each time we come across a 1 in the matrix that we haven’t met before, we write the other vertex of the edge as seen and do the same to this other vertex till we can find no extra edge that is connected. Then we count 1 province for this problem. This process is usually referred to as a function of Explore in many textbooks. After we reach the end cell of the matrix, we finish our counting of provinces.
Example 2:
Each cell in the matrix represents a vertex. The purpose of this problem is to identify all connecting adjacent 1s horizontally or vertically, assuming all four edges of the grid are all surrounded by water.
In this setting, each time we access a 1 in the matrix that we haven’t met before, we will look around its 4 directions for adjacent 1s and repeat the step until we can not find any more adjacent 1s. This is a typical DFS recursive method. After we reach the end of the matrix, we finish counting islands.
Let’s look at the code for DFS recursive method.
#547. Number of Provincesclass Solution:
def dfs_findCircleNum(self, isConnected: List[List[int]]) -> int:
n=len(isConnected) #number of vertex
cnt=0
seen=set()
def explore(i):
for j in range(0,n):
if isConnected[i][j]==1 and j not in seen:
seen.add(j)
explore(j)
for i in range(n):
if i not in seen:
explore(i)
cnt+=1
return cnt
#200. Number of Islandsclass Solution:
def numIslands(self, grid: List[List[str]]) -> int: n=len(grid)
m=len(grid[0])
drt=[(0,1),(1,0),(-1,0),(0,-1)] def dfs(i,j):
if 0>i or i>=n or 0>j or j>=m or grid[i][j]=="0" or (i,j) in visited:
return
visited.add((i,j))
for a,b in drt:
dfs(i+a,j+b)
visited=set()
c=0
for i in range(n):
for j in range(m):
if (i,j) not in visited and grid[i][j]=='1':
c+=1
dfs(i,j)
return c
It is easy to write the code of BFS iterative method once we figured out the DFS method, with a queue to substitue the stack used in DFS method.
#547. Number of Provincesclass Solution:
def bfs_findCircleNum(self, isConnected: List[List[int]]) -> int:
n=len(isConnected) #number of vertex
cnt=0
dq=deque()
seen=set()
for i in range(0,n):
if i not in seen:
dq.append(i)
cnt+=1
while dq:
node=dq.popleft()
for j in range(0,n):
if isConnected[node][j]==1 and j not in seen:
seen.add(j)
dq.append(j)
return cnt#200. Number of Islandsclass Solution:
def numIslands(self, grid: List[List[str]]) -> int:
n=len(grid)
m=len(grid[0])
drt=[(0,1),(1,0),(-1,0),(0,-1)]
c=0
dq=deque()
for i in range(n):
for j in range(m):
if grid[i][j]=='1':
c+=1
dq.append((i,j))
grid[i][j]="0"
while dq:
idx=dq.popleft()
ip=idx[0]
jp=idx[1]
for a,b in drt:
if 0<=ip+a<n and 0<=jp+b<m and grid[ip+a][jp+b]=="1":
dq.append((ip+a,jp+b))
grid[ip+a][jp+b]="0"
return c
The time complexity for both examples is dominated by the size of the matrix and the space complexity is subject to the number of vertices.
Another textbook method to solve these problems is the Union Find algorithm, which we will illustrate in another post.
