Tracing Graph Searches

Manually tracing graph searches is an essential skill in understanding and debugging graph searches. Tracing requires some understanding of the representation of a graph on the computer, though this need not be detailed.

A graph search requires two data structures:

The basic ideas of a graph search trace will be illustrated by a breadth-first search, which uses an ordinary first-in-first-out queue as a dispenser.

Representations of the Graph

For many graph searches you need two basic capabilities:

For tracing, you can get by with a minimal representation as long as the above information can be deduced. The visual representation shown below is sufficient. The computer representation is just a suggestion of the actual computer representation.

Visual representation
A Graph
Computer representation
vertexneighbors
ab c d
ba e
ca e f
da f g
eb c h
fc d h
gd h
he f g

A Breadth-First Search of the Graph

Edges are visited in first-in-first-out order. An ordinary first-in-first-out queue serves as the dispenser. The edges leaving a vertex are added to the queue in alphabetic order. This just for definiteness. A search can add the edges in any order.

search processing
edgevertexadd edges
---visit aab ac ad
visit abvisit bba be
visit acvisit cca ce cf
visit ad visit d da df dg
skip ba
visit be visit e eb ec eh
skip ca
skip ce
visit cf visit f fc fd fh
skip da
skip df
visit dg visit g gd gh
skip eb
skip ec
visit eh visit h he hf hg
skip remaining edges
solution table
vertexvia
a ---
b ab
c ac
d ad
e be
f cf
g dg
h eh

SECTION_HEADER

Section overview text.