Scribd
Upload
91 views7 pages

Minimum Spanning Tree Explained

The document provides an overview of minimum spanning trees and Prim's algorithm. It defines a minimum spanning tree as a spanning tree that connects all vertices of a graph using the minimum total cost of edges. Prim's algorithm is described as a procedure that grows a minimum spanning tree by iteratively adding the cheapest possible edge that connects an unknown vertex to the tree. An example application of building bridges between islands at minimum cost is given.

Uploaded by

sudhan
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
91 views7 pages

Minimum Spanning Tree Explained

The document provides an overview of minimum spanning trees and Prim's algorithm. It defines a minimum spanning tree as a spanning tree that connects all vertices of a graph using the minimum total cost of edges. Prim's algorithm is described as a procedure that grows a minimum spanning tree by iteratively adding the cheapest possible edge that connects an unknown vertex to the tree. An example application of building bridges between islands at minimum cost is given.

Uploaded by

sudhan
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Graph – Minimum Spanning

Tree

P VASUKI
Definition
• A (free) tree is a connected undirected
graph with no cycles.

• A spanning tree for an undirected graph is


a free tree that contains all of its vertices
– spanning trees exists iff the graph is
connected

• For example, given n islands and a desire


to connect them with bridges, the minimal
set of bridges forms a spanning tree.
• The minimal set of bridges has size n-1
– spanning trees always have n-1 edges

• Minimizing the total cost of constructing the


bridges corresponds to finding a minimum
cost spanning tree.

• Here we begin with a weighted graph where


the cost of the edge {v,w} is the cost of
building the bridge between v and w.
– not the cost of using it
• Prim’s algorithm grows the spanning
tree by adding one edge at a time
• It adds the cheapest possible legal
edge (Similar to Dijkstra)
– that goes to an unknown vertex
• The only change is how d is updated
– d stores the shortest distance to a
known vertex
– when v is added, d(w) becomes
min{d(w), c(v,w)}
Prim’s Algorithm – Example

A
A
6
12

B 5 C 5
B C
8 12

12 D 7 D
3 1
9 F
F
E
E
A
A

5
B 5 C
B C

D
D 1
3
3 F
F
E
E
A
A
6
6

B 8 5 C
B 5 C

D D
1 1
3 3
F F
E E

You might also like