graphs - dfs and bfs Flashcards
You are given an m x n grid where each cell can have one of three values:
0 representing an empty cell,
1 representing a fresh orange, or
2 representing a rotten orange.
Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.
Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.
from collections import deque
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
queue = deque()
# Step 1). build the initial set of rotten oranges
fresh_oranges = 0
ROWS, COLS = len(grid), len(grid[0])
for r in range(ROWS):
for c in range(COLS):
if grid[r][c] == 2:
queue.append((r, c))
elif grid[r][c] == 1:
fresh_oranges += 1
# Mark the round / level, _i.e_ the ticker of timestamp
queue.append((-1, -1))
# Step 2). start the rotting process via BFS
minutes_elapsed = -1
directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
while queue:
row, col = queue.popleft()
if row == -1:
# We finish one round of processing
minutes_elapsed += 1
if queue: # to avoid the endless loop
queue.append((-1, -1))
else:
# this is a rotten orange
# then it would contaminate its neighbors
for d in directions:
neighbor_row, neighbor_col = row + d[0], col + d[1]
if ROWS > neighbor_row >= 0 and COLS > neighbor_col >= 0:
if grid[neighbor_row][neighbor_col] == 1:
# this orange would be contaminated
grid[neighbor_row][neighbor_col] = 2
fresh_oranges -= 1
# this orange would then contaminate other oranges
queue.append((neighbor_row, neighbor_col))
# return elapsed minutes if no fresh orange left
return minutes_elapsed if fresh_oranges == 0 else -1nearest exit from maze
Input: maze = [["+","+",".","+"],[".",".",".","+"],["+","+","+","."]], entrance = [1,2] Output: 1 Explanation: There are 3 exits in this maze at [1,0], [0,2], and [2,3]. Initially, you are at the entrance cell [1,2]. - You can reach [1,0] by moving 2 steps left. - You can reach [0,2] by moving 1 step up. It is impossible to reach [2,3] from the entrance. Thus, the nearest exit is [0,2], which is 1 step away.
def nearestExit(maze: List[List[str]], entrance: List[int]) -> int:
rows, cols = len(maze), len(maze[0])
dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
# Mark the entrance as visited since its not a exit.
start_row, start_col = entrance
maze[start_row][start_col] = "+"
# Start BFS from the entrance, and use a queue `queue` to store all
# the cells to be visited.
queue = collections.deque()
queue.append([start_row, start_col, 0])
while queue:
curr_row, curr_col, curr_distance = queue.popleft()
# For the current cell, check its four neighbor cells.
for d in dirs:
next_row = curr_row + d[0]
next_col = curr_col + d[1]
# If there exists an unvisited empty neighbor:
if 0 <= next_row < rows and 0 <= next_col < cols \
and maze[next_row][next_col] == ".":
# If this empty cell is an exit, return distance + 1.
if 0 == next_row or next_row == rows - 1 or 0 == next_col or next_col == cols - 1:
return curr_distance + 1
# Otherwise, add this cell to 'queue' and mark it as visited.
maze[next_row][next_col] = "+"
queue.append([next_row, next_col, curr_distance + 1])
# If we finish iterating without finding an exit, return -1.
return -1There are n rooms labeled from 0 to n - 1 and all the rooms are locked except for room 0. Your goal is to visit all the rooms. However, you cannot enter a locked room without having its key.
When you visit a room, you may find a set of distinct keys in it. Each key has a number on it, denoting which room it unlocks, and you can take all of them with you to unlock the other rooms.
Given an array rooms where rooms[i] is the set of keys that you can obtain if you visited room i, return true if you can visit all the rooms, or false otherwise.
class Solution:
def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
visited = set()
stack = collections.deque()
stack.append((0, rooms[0]))
while stack:
current, keys = stack.popleft()
visited.add(current)
for key in keys:
if key not in visited:
stack.append((key, rooms[key]))
number of provinces
There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c.
A province is a group of directly or indirectly connected cities and no other cities outside of the group.
You are given an n 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.
Return the total number of provinces.
class Solution:
def findCircleNum(self, isConnected: List[List[int]]) -> int:
def dfs(i):
visited[i] = True
for j in range(len(isConnected)):
if isConnected[i][j] == 1 and not visited[j]:
dfs(j)
provinces = 0
visited = [False] * len(isConnected)
for i in range(len(isConnected)):
if not visited[i]:
provinces += 1
dfs(i)
return provincesnumber of provinces
intuition
Initialization: We start by initializing a visited array to keep track of which cities have been visited during our traversals.
Traversal: For each city, if it has not been visited, we perform a DFS (or BFS) starting from that city to visit all cities that are part of the same province. During this traversal, we mark all connected cities as visited.
Counting Provinces: Each time a DFS/BFS is initiated from an unvisited city, it signifies the discovery of a new province, so we increment our province count.
Return Result: Finally, the total number of provinces (connected components) is returned as the result.
Reorder Routes to Make All Paths Lead to the City Zero
There are n cities numbered from 0 to n - 1 and n - 1 roads such that there is only one way to travel between two different cities (this network form a tree). Last year, The ministry of transport decided to orient the roads in one direction because they are too narrow.
Roads are represented by connections where connections[i] = [ai, bi] represents a road from city ai to city bi.
This year, there will be a big event in the capital (city 0), and many people want to travel to this city.
Your task consists of reorienting some roads such that each city can visit the city 0. Return the minimum number of edges changed.
It’s guaranteed that each city can reach city 0 after reorder.
class Solution:
def minReorder(self, n, connections):
grid = [[] for _ in range(n)]
vis = [False] * n
for src, dest in connections:
grid[src].append(-dest)
grid[dest].append(src)
return self.solve(grid, 0, vis)
def solve(self, grid, val, vis):
if vis[val]:
return 0
ans = 0
vis[val] = True
for ele in grid[val]:
if vis[abs(ele)]:
continue
if ele < 0:
ans += 1
ans += self.solve(grid, abs(ele), vis)
return ans
Example usage:
sol = Solution()
n = 6
connections = [[0, 1], [1, 3], [2, 3], [4, 0], [4, 5]]
print(sol.minReorder(n, connections))Reorder Routes to Make All Paths Lead to the City Zero
intuition
Graph Representation: First, we represent the graph using an adjacency list, where each node points to its connected nodes. We use a positive value for edges that are already correctly oriented and a negative value for edges that might need to be reversed.
Depth-First Search (DFS): Starting from node 0, we traverse the graph using DFS. During the traversal, we keep track of visited nodes to avoid cycles and unnecessary computations.
Edge Evaluation: For each edge, if the edge is negatively valued (indicating a possible reversal), we increment our reversal count. If the edge is positively valued, we continue the DFS traversal without incrementing the count.
Return the Result: The final count after the DFS traversal will give us the minimum number of edges that need to be reversed.
Evaluate Division
You are given an array of variable pairs equations and an array of real numbers values, where equations[i] = [Ai, Bi] and values[i] represent the equation Ai / Bi = values[i]. Each Ai or Bi is a string that represents a single variable.
You are also given some queries, where queries[j] = [Cj, Dj] represents the jth query where you must find the answer for Cj / Dj = ?.
Return the answers to all queries. If a single answer cannot be determined, return -1.0.
class Solution:
def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
graph={}
for eq,value in zip(equations,values):
if eq[0] not in graph: graph[eq[0]]={}
if eq[1] not in graph: graph[eq[1]]={}
graph[eq[0]][eq[1]]=value
graph[eq[1]][eq[0]]=1/value
def dfs(src,dst,visited):
if src not in graph or dst not in graph: return -1
if src==dst: return 1
visited.add(src)
for neighbour,value in graph[src].items():
if neighbour not in visited:
result=dfs(neighbour,dst,visited)
if result!=-1: return result*value
return -1
results=[]
for query in queries: results.append(dfs(query[0],query[1],set()))
return resultsEvaluate Division
intuition
This algorithm solves a problem of evaluating division expressions, represented by equations, and returning the results of specific queries. Here’s the intuition behind the solution:
Graph Construction: The algorithm builds a graph where each variable is a node, and each equation represents an edge with a weight. For example, if “a / b = 2”, the edge from “a” to “b” is labeled 2, and from “b” to “a” is 1/2 (reciprocal).
Depth-First Search (DFS): To solve each query, it performs a DFS to find a path from the source variable to the target. If a path exists, the algorithm multiplies the edge weights along the path to compute the result.
Handling Queries: For each query, the DFS searches the graph and either returns the result of the division or -1 if no path (or equation relationship) exists between the variables.
In summary, this is a graph traversal algorithm where the nodes are variables, edges are equations, and DFS is used to find and compute the value for each query.
