Part I:

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.

a. Depth-first traversal starting at vertex A.

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 E 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 graph. For the same edge length, you could order the edges using the alphabet order. (For example, for length 2, the order is AB, AE, CD, CE)

a. Construct the minimal spanning tree using Kruskal's Algorithm

b. Construct the minimal spanning tree using Prim's Algorithm, using A as the root.

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

Part II: programming exercise

Modify the bfs.java program (Listing A) to find the minimum spanning tree using a breadth-first search, rather than the depth-first search shown in mst.java (Listing B). In main(), create a graph with 9 vertices and 12 edges, and find its minimum spanning tree.

Attachment:- java program.txt