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·
3 Approachesclick to switch
FIG. FIND IF PATH EXISTS IN GRAPH● INTERACTIVE
visualization loads as you reach it
Time
O(V + E)
  • Building graph scans all E edges once. helper then visits each of the V nodes at most once (guarded by visited), following each of the E edges at most twice (once per direction) - V + E.
Space
O(V + E)
  • graph's adjacency lists store both directions of every edge, O(E), plus visited holds up to V nodes and the recursion stack can hold up to V frames on a path graph - V + E.
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 Approachesclick to switch
Explanation

hashmap maps every original node to its clone, built lazily the first time each node is seen - either as the recursion root or as someone's neighbor. visited tracks which nodes have already had their neighbor list wired up, so a node reachable through a cycle is never re-expanded. rec(node) creates the clone (if missing), and - only the first time this node is visited - recurses into each neighbor before appending that neighbor's clone to hashmap[node].neighbors.

Analysis
Time
O(V + E)
  • Every node is expanded once (guarded by visited) and every edge is crossed once.
Space
O(V)
  • hashmap and visited hold up to V entries; the recursion stack goes as deep as the graph.
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 Approachesclick to switch
Explanation

Each bomb i can trigger bomb j when j sits within bomb i's blast radius - math.dist(a, b) <= bombs[i][2]. That's directed and not necessarily symmetric (i reaching j doesn't mean j reaches i), so build a directed adjacency list adj_list by testing every ordered pair (i, j).

The answer is "starting from the single best bomb, how many bombs eventually detonate" - a reachable-set size, and reachable-set-from-a-node is exactly what DFS computes. Run one DFS per candidate start, using a fresh visited set each time, and keep the largest.

Analysis
Time
O(n^3)
  • Building adj_list checks every ordered pair, O(n^2).
  • Running a full DFS from each of the n bombs is O(n * (n + E)), and E is itself O(n^2) in the worst case (every bomb in range of every other).
Space
O(n^2)
  • adj_list holds up to O(n^2) directed edges in the worst case; visited and the recursion stack are O(n).
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