Lecture_24_Network models : Minimal Spanning Tree problem

24 .1 Minimal Spanning Tree Prob lem
A tree is defined to be an undirected, acyclic and connected graph. A spanning tree is a subgraph
of G (undirected, connected graph), is a tree and contains all the vertices of G. A minimum
spanning tree is a spanning tree but has weights or lengths associated with edges and the total
weight is at the minimum.
Prim’s Algorithm
? It starts at any vertex (say A) in a graph and finds the least cost vertex (say B) connected
to the start vertex.
? Now either from A or B, it will find the next least costly vertex connection, without
creating cycle (say C)
? Now either from A, B or C find the next least costly vertex connection, without creating a
cycle and so on.
? Eventually all the vertices will be connected without any cycles and a minimum spanning
tree will be the result.
Example 1
Suppose it is desired to establish a cable communication network that links major cities, which is
shown in the figure. Determine how the cities are connected such that the total cable mileage is
minimized.