Marking visited
- Algorithms course
- Intermediate
- Lesson 55/80
- 4 min
Mark visited vertices to avoid repeats.
Marking visited
To avoid reprocessing a vertex, a visited set is kept. A vertex is added the first time it is seen.
This lets BFS finish in O(V + E) time; each vertex and edge is processed once.
Without a visited set the same vertex may enter the queue repeatedly; this leads to infinite loops.
When to mark
Marking when adding to the queue prevents the same vertex from entering twice; this is more efficient.
Marking at processing time also works but uses more space; it is a tradeoff.
Early marking reduces memory use and is the preferred approach in practice.
Practice Visited count
Write bfs_count(graph, start). Return how many vertices BFS visits. Print 4 with print(bfs_count({0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2]}, 0)).
Starter code
def bfs_count(graph, start):
# Count visited verticesSample solution
def bfs_count(graph, start):
# Count visited vertices
visited = set()
queue = [start]
while queue:
node = queue.pop(0)
if node not in visited:
visited.add(node)
for nb in graph[node]:
if nb not in visited:
queue.append(nb)
return len(visited)
print(bfs_count({0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2]}, 0))Expected output
4
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Marking visited: match the terms
| Term | Meaning |
|---|---|
visited |
Prevents repeats |
set |
Fast lookup |
graph |
Neighbors |
queue |
Order |
2 What is the role of the visited set?
- Speed up
- Prevent repeats Correct answer
- Store weight
- Keep order
Explanation: Prevent repeats.
3 Visited add
if node not in visited:
visited.____(node)if node not in visited:
visited.add(node)Explanation: add is right.