Builds on Level-Order BFS, which you haven’t finished yet.
BFS on a Graph (Mark on Push)
seen set marks a node when it is added to queue, so a node with two parents is expanded once and a cycle ends.A graph has n nodes, numbered from 0 to n - 1. The list edges describes its connections. Each pair [u, v] is one edge, and it joins node u and node v in both directions, so you can walk it either way.
You start at node source. Return true if you can walk along edges to node destination, and false if you cannot.
Graph BFS
graph with cycles ➔ mark `seen` when pushed ➔ each node queued once| 1 | from collections import defaultdict, deque |
| 2 | from typing import Dict, List |
| 3 | |
| 4 | def validPath(n: int, edges: List[List[int]], source: int, destination: int) -> bool: |
| 5 | """Find if Path Exists in Graph (LC 1971): BFS from source that marks a node in seen when it is added to queue. |
| 6 | V = n nodes. E = len(edges). The graph is undirected and can have cycles. |
| 7 | Time: O(V + E) | Space: O(V + E) for the adjacency lists, seen and queue |
| 8 | """ |
| 9 | if source == destination: |
| 10 | return True |
| 11 | |
| 12 | graph: Dict[int, List[int]] = defaultdict(list) # node -> its neighbours, built from the edge list |
| 13 | for u, v in edges: |
| 14 | graph[u].append(v) |
| 15 | graph[v].append(u) |
| 16 | |
| 17 | seen = {source} # every node that is in queue or has already left it |
| 18 | queue = deque([source]) # nodes found but not yet expanded, in the order they were found |
| 19 | |
| 20 | while queue: |
| 21 | # 1. Expand the Oldest Found Node: |
| 22 | # Every neighbour of node is looked at once, when node leaves queue. |
| 23 | node = queue.popleft() |
| 24 | for neighbour in graph[node]: |
| 25 | if neighbour == destination: |
| 26 | return True |
| 27 | |
| 28 | # 2. Mark on Push: |
| 29 | # A neighbour joins seen at the moment it joins queue, not when it leaves. |
| 30 | # A node that waits in queue is then already marked, so a second parent |
| 31 | # cannot add it again, and a cycle cannot refill the queue. |
| 32 | if neighbour not in seen: |
| 33 | seen.add(neighbour) |
| 34 | queue.append(neighbour) |
| 35 | |
| 36 | return False |
seen is in queue or has already left it, so each node is added to queue exactly once.A graph can reach one node from two parents, so mark a node in seen at the moment you add it to queue, not when you take it out. Each node then enters queue once, so a cycle cannot refill the queue and the loop ends. The trap is skipping the seen check: on a cycle, the loop never ends when destination cannot be reached.
See it run
Mark on push, step by step
seen [0]destination 6
Each circle is a node. The first row under the graph is queue: the left box leaves first. The second row is seen.
nodethe node just taken out of queuequeuedwaiting in queue, already in seenexpandedall its neighbours were looked atneighbourthe neighbour being looked at now
Put the source 0 in queue and in seen. The destination is 6.
Gotcha 1 of 4
- The trap
Gotcha 1: Adding a neighbour without checking
seenMistakequeue.append(neighbour)Fixif neighbour not in seen: seen.add(neighbour) queue.append(neighbour)What happens: A graph can have a cycle. Without the
seencheck, every neighbour goes intoqueueagain and again. On a cycle the nodes keep refillingqueue, so the loop never ends when the destination cannot be reached.Example: n = 4, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 3Mistake: the loop never endsFix: returns False
- The input is a tree, as in Binary Tree Level Order Traversal (LC 102): no node has two parents, so no
seenset is needed. See Level-Order BFS - You need the fewest moves, as in Shortest Path in Binary Matrix (LC 1091), not only whether a node can be reached: each node also stores
dist. See Shortest-Path BFS
Deep Dive
Why a graph needs seen and a tree does not
In a tree, every node has one parent. The walk reaches each node by exactly one path, so no node is added to queue twice.
In a graph, a node can have two parents or sit on a cycle. In the board, node 3 is a neighbour of both 1 and 2. The walk reaches it from node 1 first. When it later looks at node 3 from node 2, node 3 is already in seen, so it is not added again.
The board uses source = 0 and destination = 6. Node 6 is in a separate group of nodes, so queue empties and the answer is False. seen ends as [0, 1, 2, 3, 4], and each of those nodes was added to queue once.
Mark on push: why the mark goes before queue.append
seen.add(neighbour) runs in the same step as queue.append(neighbour). The invariant is: every node in queue, and every node that has already left queue, is in seen.
If the mark waits until the node leaves queue, a node that is still waiting is not marked. A second parent then adds it again. The answer stays correct, but the same node is expanded many times.
On a complete graph with 10 nodes, marking on push puts 9 nodes into queue. Marking on pop means the code adds a node to seen only when it takes the node out of queue, skips a node that is already in seen, and adds a neighbour to queue unless the neighbour is already in seen. Then queue gets 45 entries, one for each pair of nodes.
What happens with no seen at all
Take the three links [0, 1], [1, 2] and [2, 0], with source = 0 and destination = 3. The three nodes form a cycle. Node 3 has no link.
Without seen, node 0 adds 1 and 2. Node 1 adds 0 and 2. Node 2 adds 1 and 0. Each of them adds the others again, so queue never empties. The loop never ends.
With seen, the three nodes are added once each, queue empties after three nodes, and the answer is False.
The cost, and what the card does not add
The code builds the adjacency lists in O(V + E) time. Each node enters queue once and leaves it once. Each link is looked at twice, once from each end. So the search takes O(V + E) time, and graph, seen and queue take O(V + E) space.
This card answers the question: can the destination be reached? It does not store how far each node is. The card Shortest-Path BFS adds a dist value to each node for that.
For a start with many sources, or a graph that is a grid, the same seen rule holds. Only the way the neighbours are listed changes.
60-Second Pitch
"The graph is undirected and can have cycles, so I build adjacency lists and run BFS from the source. I keep a seen set and add a node to seen at the same moment I add it to queue. A node that is waiting in queue is then already marked, so a second parent cannot add it again, and a cycle cannot refill the queue. If a neighbour is the destination, I return True. If queue empties first, I return False. Each node enters queue once and each link is looked at twice, so the time is O(V + E) and the space is O(V + E)."
Common Questions
- Why do you mark a node when you add it to
queueand not when you take it out? A node that is waiting in
queueis not yet marked if you mark on pop. A second parent then adds it again. The answer stays correct, but a node can be expanded once for each link that points to it. On a complete graph with 10 nodes that is 45 queue entries instead of 9.- Can you use depth-first search instead? What changes?
Yes, for this question. Replace
queue.popleft()withstack.pop(), or use recursion. Theseenrule is the same. The answer to "is there a path" does not depend on the order. BFS is needed when the number of moves matters.- What are the time and space complexity?
O(V + E)time andO(V + E)space. Building the adjacency lists costsO(V + E). Each node entersqueueonce. Each link is looked at twice, once from each end.- What if the input is an adjacency matrix and not a list of edges?
Then finding the neighbours of a node costs a scan of one row, which is O(V). The search takes O(V^2) time. The
seenrule does not change.- How would you also count the nodes that can be reached?
Return
len(seen)whenqueueis empty.seenholds exactly the nodes that were added toqueue, which are the nodes reachable from the source.
SWE Reasoning
Spot it
- The input is a graph: a list of edges, an adjacency list or an adjacency matrix. It can have cycles.
- The question is about reaching: is there a path, how many nodes are reachable, visit every node once, copy the graph.
- No weights and no order of visiting is required, so a plain queue is enough.
- A node can be reached from two different parents. This is the signal that a
seenset is needed.
The invariant, step by step
seenstarts as{source}andqueuestarts as[source]. Both hold the source, so the invariant holds.- Each round takes the oldest node out of
queueand looks at its neighbours. - A neighbour that is the destination ends the search with
True. - A neighbour that is not in
seenis added toseenand toqueuein the same step. The invariant still holds. - A neighbour already in
seenis left alone. It is inqueueor already expanded. - When
queueis empty, every node reachable from the source was expanded, so the answer isFalse.
Traps
- No
seencheck. On a cycle,queuenever empties when the destination cannot be reached. - Only one direction of each edge. The graph is undirected, so both
graph[u]andgraph[v]need the link. - No check for
source == destination. The walk compares only neighbours, so a path of length 0 is missed. - Marking when the node leaves
queue. A waiting node is not marked, so it is added again and expanded many times.
Practice
Builds on Level-Order BFS, which you haven’t finished yet.
BFS on a Graph (Mark on Push)
seen set marks a node when it is added to queue, so a node with two parents is expanded once and a cycle ends.A graph has n nodes, numbered from 0 to n - 1. The list edges describes its connections. Each pair [u, v] is one edge, and it joins node u and node v in both directions, so you can walk it either way.
You start at node source. Return true if you can walk along edges to node destination, and false if you cannot.
Graph BFS
graph with cycles ➔ mark `seen` when pushed ➔ each node queued once| 1 | from collections import defaultdict, deque |
| 2 | from typing import Dict, List |
| 3 | |
| 4 | def validPath(n: int, edges: List[List[int]], source: int, destination: int) -> bool: |
| 5 | """Find if Path Exists in Graph (LC 1971): BFS from source that marks a node in seen when it is added to queue. |
| 6 | V = n nodes. E = len(edges). The graph is undirected and can have cycles. |
| 7 | Time: O(V + E) | Space: O(V + E) for the adjacency lists, seen and queue |
| 8 | """ |
| 9 | if source == destination: |
| 10 | return True |
| 11 | |
| 12 | graph: Dict[int, List[int]] = defaultdict(list) # node -> its neighbours, built from the edge list |
| 13 | for u, v in edges: |
| 14 | graph[u].append(v) |
| 15 | graph[v].append(u) |
| 16 | |
| 17 | seen = {source} # every node that is in queue or has already left it |
| 18 | queue = deque([source]) # nodes found but not yet expanded, in the order they were found |
| 19 | |
| 20 | while queue: |
| 21 | # 1. Expand the Oldest Found Node: |
| 22 | # Every neighbour of node is looked at once, when node leaves queue. |
| 23 | node = queue.popleft() |
| 24 | for neighbour in graph[node]: |
| 25 | if neighbour == destination: |
| 26 | return True |
| 27 | |
| 28 | # 2. Mark on Push: |
| 29 | # A neighbour joins seen at the moment it joins queue, not when it leaves. |
| 30 | # A node that waits in queue is then already marked, so a second parent |
| 31 | # cannot add it again, and a cycle cannot refill the queue. |
| 32 | if neighbour not in seen: |
| 33 | seen.add(neighbour) |
| 34 | queue.append(neighbour) |
| 35 | |
| 36 | return False |
seen is in queue or has already left it, so each node is added to queue exactly once.A graph can reach one node from two parents, so mark a node in seen at the moment you add it to queue, not when you take it out. Each node then enters queue once, so a cycle cannot refill the queue and the loop ends. The trap is skipping the seen check: on a cycle, the loop never ends when destination cannot be reached.
See it run
Mark on push, step by step
seen [0]destination 6
Each circle is a node. The first row under the graph is queue: the left box leaves first. The second row is seen.
nodethe node just taken out of queuequeuedwaiting in queue, already in seenexpandedall its neighbours were looked atneighbourthe neighbour being looked at now
Put the source 0 in queue and in seen. The destination is 6.
Gotcha 1 of 4
- The trap
Gotcha 1: Adding a neighbour without checking
seenMistakequeue.append(neighbour)Fixif neighbour not in seen: seen.add(neighbour) queue.append(neighbour)What happens: A graph can have a cycle. Without the
seencheck, every neighbour goes intoqueueagain and again. On a cycle the nodes keep refillingqueue, so the loop never ends when the destination cannot be reached.Example: n = 4, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 3Mistake: the loop never endsFix: returns False
- The input is a tree, as in Binary Tree Level Order Traversal (LC 102): no node has two parents, so no
seenset is needed. See Level-Order BFS - You need the fewest moves, as in Shortest Path in Binary Matrix (LC 1091), not only whether a node can be reached: each node also stores
dist. See Shortest-Path BFS
Deep Dive
Why a graph needs seen and a tree does not
In a tree, every node has one parent. The walk reaches each node by exactly one path, so no node is added to queue twice.
In a graph, a node can have two parents or sit on a cycle. In the board, node 3 is a neighbour of both 1 and 2. The walk reaches it from node 1 first. When it later looks at node 3 from node 2, node 3 is already in seen, so it is not added again.
The board uses source = 0 and destination = 6. Node 6 is in a separate group of nodes, so queue empties and the answer is False. seen ends as [0, 1, 2, 3, 4], and each of those nodes was added to queue once.
Mark on push: why the mark goes before queue.append
seen.add(neighbour) runs in the same step as queue.append(neighbour). The invariant is: every node in queue, and every node that has already left queue, is in seen.
If the mark waits until the node leaves queue, a node that is still waiting is not marked. A second parent then adds it again. The answer stays correct, but the same node is expanded many times.
On a complete graph with 10 nodes, marking on push puts 9 nodes into queue. Marking on pop means the code adds a node to seen only when it takes the node out of queue, skips a node that is already in seen, and adds a neighbour to queue unless the neighbour is already in seen. Then queue gets 45 entries, one for each pair of nodes.
What happens with no seen at all
Take the three links [0, 1], [1, 2] and [2, 0], with source = 0 and destination = 3. The three nodes form a cycle. Node 3 has no link.
Without seen, node 0 adds 1 and 2. Node 1 adds 0 and 2. Node 2 adds 1 and 0. Each of them adds the others again, so queue never empties. The loop never ends.
With seen, the three nodes are added once each, queue empties after three nodes, and the answer is False.
The cost, and what the card does not add
The code builds the adjacency lists in O(V + E) time. Each node enters queue once and leaves it once. Each link is looked at twice, once from each end. So the search takes O(V + E) time, and graph, seen and queue take O(V + E) space.
This card answers the question: can the destination be reached? It does not store how far each node is. The card Shortest-Path BFS adds a dist value to each node for that.
For a start with many sources, or a graph that is a grid, the same seen rule holds. Only the way the neighbours are listed changes.
60-Second Pitch
"The graph is undirected and can have cycles, so I build adjacency lists and run BFS from the source. I keep a seen set and add a node to seen at the same moment I add it to queue. A node that is waiting in queue is then already marked, so a second parent cannot add it again, and a cycle cannot refill the queue. If a neighbour is the destination, I return True. If queue empties first, I return False. Each node enters queue once and each link is looked at twice, so the time is O(V + E) and the space is O(V + E)."
Common Questions
- Why do you mark a node when you add it to
queueand not when you take it out? A node that is waiting in
queueis not yet marked if you mark on pop. A second parent then adds it again. The answer stays correct, but a node can be expanded once for each link that points to it. On a complete graph with 10 nodes that is 45 queue entries instead of 9.- Can you use depth-first search instead? What changes?
Yes, for this question. Replace
queue.popleft()withstack.pop(), or use recursion. Theseenrule is the same. The answer to "is there a path" does not depend on the order. BFS is needed when the number of moves matters.- What are the time and space complexity?
O(V + E)time andO(V + E)space. Building the adjacency lists costsO(V + E). Each node entersqueueonce. Each link is looked at twice, once from each end.- What if the input is an adjacency matrix and not a list of edges?
Then finding the neighbours of a node costs a scan of one row, which is O(V). The search takes O(V^2) time. The
seenrule does not change.- How would you also count the nodes that can be reached?
Return
len(seen)whenqueueis empty.seenholds exactly the nodes that were added toqueue, which are the nodes reachable from the source.
SWE Reasoning
Spot it
- The input is a graph: a list of edges, an adjacency list or an adjacency matrix. It can have cycles.
- The question is about reaching: is there a path, how many nodes are reachable, visit every node once, copy the graph.
- No weights and no order of visiting is required, so a plain queue is enough.
- A node can be reached from two different parents. This is the signal that a
seenset is needed.
The invariant, step by step
seenstarts as{source}andqueuestarts as[source]. Both hold the source, so the invariant holds.- Each round takes the oldest node out of
queueand looks at its neighbours. - A neighbour that is the destination ends the search with
True. - A neighbour that is not in
seenis added toseenand toqueuein the same step. The invariant still holds. - A neighbour already in
seenis left alone. It is inqueueor already expanded. - When
queueis empty, every node reachable from the source was expanded, so the answer isFalse.
Traps
- No
seencheck. On a cycle,queuenever empties when the destination cannot be reached. - Only one direction of each edge. The graph is undirected, so both
graph[u]andgraph[v]need the link. - No check for
source == destination. The walk compares only neighbours, so a path of length 0 is missed. - Marking when the node leaves
queue. A waiting node is not marked, so it is added again and expanded many times.