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.
[Note that the particular BFS depends
on the order of vertices in adjacency lists. You should get
the results below, assuming that you used my data, but with
adjacency lists in a different order, we would expect the
results to differ. Of course all the distances will be the
same, but the specific BFS spanning tree and the particular
shortest paths will differ.]
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.
[A shortest path from 10 to 1 is:
10-8-7-3-1. BFS tree is below top.]
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.
[A shortest path from 0 to 9 is:
0-4-7-8-9. BFS tree is below bottom.]
BFS Tree From Node 10 (top) and From Node 0 (bottom)
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). [The requested path
goes from the vertex in the top level at the far left (ND).
One then just follows predessesors back to the lower right
vertex (SC). In terms of vertex numbers from 35, this
path goes 35-36-26-19-20-21-16.]
