Skip to main content

Traversal

Visiting every vertex reachable from a start, systematically. BFS walks outward in rings using a queue; DFS commits to one branch and plunges using a stack (explicit, or the call stack via recursion). Both are the same loop with two knobs - the neighbour function, and how you track visited.

The mechanics, the correctness argument for why BFS's first arrival is always shortest, and the traps that come from marking visited at the wrong moment all live on the learn page: Traversal. The problems below are that engine with one knob turned.

1971. Find if Path Exists in Graph​

Easy·
4 Approaches · 2 patterns
FIG. FIND IF PATH EXISTS IN GRAPH● INTERACTIVE
visualization loads as you reach it
class Solution:
def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
graph = defaultdict(list)
 
for src, dst in edges:
graph[src].append(dst)
graph[dst].append(src)
 
return self.helper(graph, source, destination, set())
 
def helper(self, graph, node, target, visited):
 
if node == target:
return True
 
if node in visited:
return False
 
visited.add(node)
 
for neighbor in graph[node]:
if self.helper(graph, neighbor, target, visited):
return True
 
return False

133. Clone Graph​

Medium·
4 Approaches
FIG. 133 CLONE GRAPH RECURSIVE● INTERACTIVE
visualization loads as you reach it
class Solution:
def cloneGraph(self, root: Optional["Node"]) -> Optional["Node"]:
def rec(node):
if node not in hashmap:
hashmap[node] = Node(node.val)
if node not in visited:
visited.add(node)
for neighbor in node.neighbors:
rec(neighbor)
hashmap[node].neighbors.append(hashmap[neighbor])
return hashmap[node]
 
if not root:
return
hashmap = {root: Node(root.val)}
visited = set()
return rec(root)

2101. Detonate the Maximum Bombs​

Medium·
3 Approaches
FIG. 2101 DETONATE THE MAXIMUM BOMBS● INTERACTIVE
visualization loads as you reach it
class Solution:
def maximumDetonation(self, bombs: List[List[int]]) -> int:
def dfs(node):
if node in visited:
return
visited.add(node)
for neighbor in adj_list[node]:
dfs(neighbor)
 
n = len(bombs)
adj_list = collections.defaultdict(list)
for i in range(n):
for j in range(n):
if i != j:
a = (bombs[i][0], bombs[i][1])
b = (bombs[j][0], bombs[j][1])
if math.dist(a, b) <= bombs[i][2]:
adj_list[i].append(j)
 
maxi = 0
for node in range(n):
visited = set()
dfs(node)
maxi = max(maxi, len(visited))
return maxi