#### 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:

• A dispenser - this determines the order in which edges and vertices are visited.
• A structure for recording results. This structure is often a table (Java java.util.Map).

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:

• Given a vertex, find the edges that leave the vertex.
• Given an edge, find the vertex that it comes from and find the vertex that it goes to.

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
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