Breadth-first Searches and PrintPaths.
(See BFS.)
You are to write functions BFS and PrintPath,
as described in the above link. Of course you must include
the code for these functions in your submissions.
First test these functions with the graph
small.txt that was used in:
Recitation
11 (in-class). This file has a weight on the edges, but that
is ignored by the BFS, but instead a weight of 1 is assumed
for each edge. Your run should:
print the result of BFS from vertex 10,
printing the list of vertices with the vertex data (values of the
d and pi fields for each vertex), showing the course
of the search and defining the breadth-first spanning tree,
and in the same run printing a shortest path from 10 to 1.
print the result of BFS from vertex 0,
giving the previous data.
and in the same run printing a shortest path from 0 to 9.
Second, test these functions with the 48-capitals graph,
printing results of BFS from vertex 35 (which is SC).
Also print the shortest path from 35 to 16
(which is ND).
Revision date:2012-11-11.
(Please use ISO
8601, the International Standard.)
