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.

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 |

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.