1. Answer questions for the following graph, if a new vertex is visited and there is more than one possibility to select, following the alphabet order. see image.
a. Depth-first traversal starting at vertex B.
b. Depth-first traversal starting at vertex F.
c. Breadth-first traversal starting at vertex A.
d. Breadth-first traversal starting at vertex F.
e. Shortest path from vertex A to vertex H using breadth-first search.
f. Shortest path from vertex G to vertex C using breadth-first search.
g. Shortest path from vertex F to vertex A using breadth-first search.
2. Answer questions for the following matrix. For the same edge length, you could order the edges using the alphabet order. (For example, for length 3, the order is AB,BC)
0 3 8 11 9 inf
3 0 3 9 5 7
8 3 0 inf 10 2
11 9 inf 0 7 1
9 5 10 7 0 inf
Inf 7 2 1 inf 0
a. Construct the minimal spanning tree using Kruskal's Algorithm, showing the edges selecting order.
b. Construct the minimal spanning tree using Prim's Algorithm, using A as the root and showing the edges selecting order.
c. Construct the shortest path using Dijkstra's Algorithm, using A as the source node. Using a table to describe the status of each step (example shown in handouts)
Text programming project 13.4 on page 668. Hint, the Warshall algorithm is on page 93 on chapter 13, you could directly implement based on the algorithm without using the code from Programming Project 13.3. In your application program, please use the below graph to test your code.
0 1 1 inf inf 1 inf
inf 0 inf inf 1 1 inf
inf inf 0 inf inf inf inf
inf inf 1 0 inf inf 1
inf inf inf inf 0 1 inf
1 inf inf inf inf 0 1
Inf inf inf 1 1 inf 0