Campus pathfinder
Finding and drawing routes across a campus map.
Choosing a route
Click a location to set the start, then move the pointer over another vertex to choose a destination. The program redraws the route on top of the campus map. The map is a graph: locations are vertices and the connections between them are edges.
Breadth-first search
A queue holds the frontier of the search. As vertices are discovered, a backpointer records where each came from. Once the search has reached the goal, following those pointers reconstructs a path from the destination to the start. Because the graph is unweighted, this finds a route with the fewest edges; it does not minimize walking distance.
Drawing and data
The graph loader creates vertex objects from a text file, and the graphics loop draws the vertices and their adjacency lists. Mouse handling, graph search, and drawing are separate parts of the program. The supplied cs1lib library handles the graphics window.