Visited state

What is a graph?

A graph is a collection of vertices and edges. A vertex, also called a node, represents an item. An edge represents a connection between two items. Edges can have a direction or a weight. Graph traversal visits connected vertices while remembering which have already been visited.

Example: Let A, B, and C be vertices, with edges A–B and B–C. A can reach C through B. A directed edge A → B permits movement from A to B but does not automatically permit movement back.

Helpful before this chapter

If these ideas are new, begin with:

Hash maps and sets Queues and deques Recursion

Understand the idea

Visited state prevents repeated expansion. Mark BFS nodes on enqueue; DFS can mark on discovery. State may need more than a boolean when distinguishing active recursion from completed nodes.

Work through an example

B and C both reach D. Marking D when first enqueued prevents duplicate queue entries and preserves its first shortest distance.

Time and space complexity

O(V) visited storage; combined adjacency-list traversal O(V+E).

Why it works

Each discovered vertex is scheduled at most once for a plain traversal.

Common mistakes

Marking only after dequeue can schedule duplicates.
One global visited set is unsuitable for all path-enumeration problems.

Chapter lab · Python implementation

A graph models entities and connections; edges can be directed or undirected, weighted or unweighted. Our lab uses adjacency lists and marks BFS vertices when enqueuing. The diagram has a cycle A-B-D-C-A, so visited state is essential. Distances count edges because every edge has equal cost.

This shared lab connects the chapter's topics. Follow the current lesson's worked example first, then trace the complete implementation. Additional algorithms described in topic exercises are variations you can implement independently.

from collections import deque

def bfs(graph,start):
    distances={start:0}
    parent={start:None}
    queue=deque([start])
    while queue:
        node=queue.popleft()
        for neighbor in graph.get(node,[]):
            if neighbor not in distances:
                distances[neighbor]=distances[node]+1
                parent[neighbor]=node
                queue.append(neighbor)
    return distances,parent

def components(graph):
    seen=set(); count=0
    for start in graph:
        if start in seen: continue
        count+=1; seen.add(start); stack=[start]
        while stack:
            node=stack.pop()
            for neighbor in graph[node]:
                if neighbor not in seen:
                    seen.add(neighbor); stack.append(neighbor)
    return count

Run and test the lab

Copy the implementation and these assertions into a Python 3 file and run it. An assertion failure means the actual result differs from the expectation. Add the current topic's exercise and boundary tests to deepen your understanding.

g={'A':['B','C'],'B':['A','D'],'C':['A','D'],'D':['B','C'],'E':[]}
d,p=bfs(g,'A'); assert d=={'A':0,'B':1,'C':1,'D':2}
assert p['D'] in ['B','C']
assert components(g)==2
assert bfs({'X':[]},'X')[0]=={'X':0}

CHECK YOUR UNDERSTANDING