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

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

Section overview text.