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.
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 |
---|
![]() |
Computer representation | |
---|---|
vertex | neighbors |
a | b c d |
b | a e |
c | a e f |
d | a f g |
e | b c h |
f | c d h |
g | d h |
h | e f g |
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 | ||
---|---|---|
edge | vertex | add edges |
--- | visit a | ab ac ad |
visit ab | visit b | ba be |
visit ac | visit c | ca 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 | |
---|---|
vertex | via |
a | --- |
b | ab |
c | ac |
d | ad |
e | be |
f | cf |
g | dg |
h | eh |
Section overview text.