Minimum Spanning Tree problem (not in book): Consider the following undirected weighted graph. 1 a. List...

Transcribed Image Text:

Minimum Spanning Tree problem (not in book): Consider the following undirected weighted graph. 1 a. List the edges that are in the minimum spanning tree that Kruskal's algorithm would find in the order that Kruskal's algorithm would add them to the MST. In listing an edge, just list it as an ordered pair. E.g., an edge between x and y would be (x, y). b. List the edges that are in the minimum spanning tree that Prim's algorithm would find if it used vertex A as the root in the order that Prim's algorithm would add them to the MST. c. List the edges that are in the minimum spanning tree that Prim's algorithm would find if it used vertex G as the root in the order that Prim's algorithm would add them to the MST. A 4 B 3 5 15 E 12 D 18 8 14 7 G F 10 Minimum Spanning Tree problem (not in book): Consider the following undirected weighted graph. 1 a. List the edges that are in the minimum spanning tree that Kruskal's algorithm would find in the order that Kruskal's algorithm would add them to the MST. In listing an edge, just list it as an ordered pair. E.g., an edge between x and y would be (x, y). b. List the edges that are in the minimum spanning tree that Prim's algorithm would find if it used vertex A as the root in the order that Prim's algorithm would add them to the MST. c. List the edges that are in the minimum spanning tree that Prim's algorithm would find if it used vertex G as the root in the order that Prim's algorithm would add them to the MST. A 4 B 3 5 15 E 12 D 18 8 14 7 G F 10

Answer rating: 100% (QA)

To solve this problem we can use Kruskals algorithm to find the minimum spanning tree MST of the giv... View the full answer