__Prim’s Algorithm__

__Prim’s Algorithm__

__-to find minimum spanning tree__

__-to find minimum spanning tree__

**Some useful definitions:**

• **F****r****inge edge: **An edge which has one vertex is in partially constructed tree Ti and the other is not.

• **U****n****seen edge: **An edge with both vertices not in Ti

### Algorithm:

#### ALGORITHM Prim (G)

//Prim’s algorithm for constructing a MST

//Input: A weighted connected graph G = { V, E }

//Output: ET the set of edges composing a MST of G

// the set of tree vertices can be initialized with any vertex

Find a minimum-weight edge e* = (v*, u*) among all the edges (v, u) such that v is in VT and u is in V – VT

**The method:**

**STE****P 1**: Start with a tree, T0, consisting of one vertex

**STE****P 2**: “Grow” tree one vertex/edge at a time

• Construct a series of expanding sub-trees T1, T2, … Tn-1.

• At each stage construct Ti + 1 from Ti by adding the minimum weight edge connecting a vertex in tree (Ti) to one vertex not yet in tree

, choose from“fringe” edges (this is the “greedy” step!)

Algorithm stops when all vertices are included

**Example:**

Apply Prim’s algorithm for the following graph to find MST.

**Efficiency:**

Efficiency of Prim’s algorithm is based on data structure used to store priority queue.

• Unordered array:

Efficiency:Θ(n2)• Binary heap:

Efficiency:Θ(m log n)• Min-heap: For graph with n nodes and m edges:

Efficiency: (n + m) log n

### Conclusion:

• Prim’s algorithm is a “vertex based algorithm”

• Prim’s algorithm “Needs priority queue for locating the nearest vertex.” The choice of priority queue matters in Prim implementation.

o Array - optimal for dense graphs

o Binary heap - better for sparse graphs

o Fibonacci heap - best in theory, but not in practice