Explore BrainMass

Minimal Spanning Tree for a connected weighted graph

Find a minimal spanning tree for the connected weighted graph, following Prim's algorithm. Please see attached 4.doc for the details on graph and Prim's algorithm for finding a minimal spanning tree.


Solution Preview

Since nothing is mentioned about the start vertex in the question, let us assume it as vertex 1 i.e. s=1 in step 3 of algorithm.

To start with, start vertex (1) will already be in mst, i.e. v(1) = 1.
Loop in step 5 will ...

Solution Summary

Apart from showing stepwise addition of vertices and edges to a MST for the graph, solution also explains the Prim's algorithm briefly.