This algorithm was first propsed by Jarnik, but typically attributed to Prim. It starts from an arbitrary vertex (root) and at each stage, add a new branch (edge) to the tree already constructed, much like a mould. The algorithm halts when all the vertices in the graph have been reached.

To understand the problem statement refer

This is similar to djikstra's algorithm where we were clear where to begin with as we were given the source vertex, but here we have to choose arbitrarily.

This strategy is greedy in the sense that at each step the partial spanning tree is augmented with an edge that is the smallest among all possible adjacent edges.

Example

Lets start with following graph:

Lets start with edge 1 to begin with, covering 2 nodes.

We can now select the edge with min weight between 3 edges - 2,3,4. Lets select 2 as it is min.

Now we have 3 edges - 3 ,4 and 5, from the nodes that we have visited, so lets take 3 as it is minimum, but it doesn't add any new node, so we just discard it. (Marker in the below diagram means that we are just covering it)

Now we have 2 options of edges - 4 or 5, and as 4 is minimum we select it, it adds the last nodes also to the visited nodes, and hence prim's algo is complete.

So edges 1,2 and 4 make MST.

Analysis

The algorithm spends most of its time in finding the smallest edge. So, time of the algorithm basically depends on how do we search this edge.

Just find the smallest edge by searching the adjacency list of the vertices in V. In this case, each iteration costs O(m) time, yielding a total running time of O(mn) OR O(|E|.|V|).

We will focus on adjacency lists only. Can we do better? Answer is yes. As we saw in the main WHILE loop, we are getting the minimum of the edge lengths crossing the frontier, and getMin() of heap will be very useful, which will speed up repeated getMin() elements on the edges.

This is similar to djikstra''s algo where we stored edges, but here we have to vertices.

By using binary heaps, the algorithm runs in O(m log n).

Check - Can initialize heap with O (m+log n) = O(m log n) preprocessing.

Now we have to make sure that above 2 variants hold when we execute WHILE loop.

So, first variant will hold as we have initialized the heap with vertices only.

Making the 2nd variant

eg.

This ensures that 2nd variant holds. Deleting the vertex at some position is little tricky, so we have to do some book keeping to keep the index of the vertex as well.

By using Fibonacci heaps, the algorithm runs in O(m + n log n) = O (m log n)

Correctness of Prim's algorithm

Part 1 - Prim's algorithm atleast computes a spanning tree T*

Part 2 - T* is an MST

To be done later.

To understand the problem statement refer

**here**.This is similar to djikstra's algorithm where we were clear where to begin with as we were given the source vertex, but here we have to choose arbitrarily.

This strategy is greedy in the sense that at each step the partial spanning tree is augmented with an edge that is the smallest among all possible adjacent edges.

Example

Lets start with following graph:

Lets start with edge 1 to begin with, covering 2 nodes.

We can now select the edge with min weight between 3 edges - 2,3,4. Lets select 2 as it is min.

Now we have 3 edges - 3 ,4 and 5, from the nodes that we have visited, so lets take 3 as it is minimum, but it doesn't add any new node, so we just discard it. (Marker in the below diagram means that we are just covering it)

Now we have 2 options of edges - 4 or 5, and as 4 is minimum we select it, it adds the last nodes also to the visited nodes, and hence prim's algo is complete.

So edges 1,2 and 4 make MST.

**MST-PRIM****Input:**A weighted, undirected graph G=(V, E, w)**Output:**A minimum spanning tree T.T={} Let r be an arbitrarily chosen vertex from V. X = {r} WHILE | U| < n DO Find u in X and v in V-X such that the edge (u, v) is a smallest edge between X-V. T = T U{(u, v)} //add u,v to T X= X U {v} //add v to vertices covered set U

Analysis

The algorithm spends most of its time in finding the smallest edge. So, time of the algorithm basically depends on how do we search this edge.

**Adjacency list analysis**Just find the smallest edge by searching the adjacency list of the vertices in V. In this case, each iteration costs O(m) time, yielding a total running time of O(mn) OR O(|E|.|V|).

**Adjacency matrix analysis****Can we do better?**We will focus on adjacency lists only. Can we do better? Answer is yes. As we saw in the main WHILE loop, we are getting the minimum of the edge lengths crossing the frontier, and getMin() of heap will be very useful, which will speed up repeated getMin() elements on the edges.

__Heap operation costs__- Insert element ----- O(log n)
- Get Min element ----O(log n)

**here**.This is similar to djikstra''s algo where we stored edges, but here we have to vertices.

**Prim's Algorithm with Binary heap**By using binary heaps, the algorithm runs in O(m log n).

*Invariant 1*: elements in the heap will be vertices i.e. vertices of V-X*Invariant 2*: for v ∈ V-X, key[v] = cheapest edge (u,v) with u ∈ X. If this edge don't exists, put infinity.Check - Can initialize heap with O (m+log n) = O(m log n) preprocessing.

Now we have to make sure that above 2 variants hold when we execute WHILE loop.

So, first variant will hold as we have initialized the heap with vertices only.

Making the 2nd variant

eg.

when v added to X{ foreach edge (v,w) in E { if(w belongs to V-X){ Delete w from heap Recompute key[w] = min ([key[1], (v-w)) re-insert into heap } }

This ensures that 2nd variant holds. Deleting the vertex at some position is little tricky, so we have to do some book keeping to keep the index of the vertex as well.

__Analysis:__- n-1 Inserts during pre-processing
- n-1 extract min (one per iteration while loop)
- each edge (v,w) triggers one delete/insert combo, implies O(m) time.

**Fibonacci heap**By using Fibonacci heaps, the algorithm runs in O(m + n log n) = O (m log n)

Correctness of Prim's algorithm

__- Prim's algorithm always computes an MST.__*Theorem*Part 1 - Prim's algorithm atleast computes a spanning tree T*

Part 2 - T* is an MST

To be done later.

## 0 comments:

## Post a Comment