Marking visited

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.

Exercise 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)).

Show example 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))

Test yourself

Marking visited: match the terms

visited

Prevents repeats
set

Fast lookup
graph

Neighbors
queue

Order
What is the role of the visited set?
- Speed up
- Prevent repeats
- Store weight
- Keep order
Show answer

Prevent repeats — Prevent repeats.

Visited add

if node not in visited:
    visited.____(node)

Show answer

if node not in visited:
    visited.add(node)

Next lesson: Summary - BFS

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies