Explore BrainMass
Share

Prim algorithm

This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

Please see the attached file.

For the graph in 16.28(a), replicate the trace of Prim's algorithm to create a minimum spanning tree. For each step, create the list of minInfo elements in the priority queue and indicate which vertices and edges are in the current spanning tree, along with the accumulated total weight.

Figure 16-28(a)

© BrainMass Inc. brainmass.com March 21, 2019, 6:54 pm ad1c9bdddf
https://brainmass.com/computer-science/trees/prim-algorithm-272209

Attachments

Solution Preview

We start from the vertex A and proceed with the Prim's algorithm.
At the beginning, the priority queue is minInfo = [A], totalWeight = 0.
Step 1: Choose the edge (A, B) because it has the minimum length with minInfo. Then minInfo = [A, B] and totalWeight = 1
Step 2: Choose the edge (B, C) because it has the minimum length with minInfo. Then ...

Solution Summary

Prim algorithms are examined. A list of minInfo elements in the priority queue and indicates which verticies and edges are in the current spanning tree.

$2.19