Explore BrainMass
Share

Explore BrainMass

    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 April 1, 2020, 4:57 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