Part of course:

Prim's algorithm for Minimum Spanning Tree

- Video with step-by-step example
- Algorithm steps
- Pseudo-code
- Run-time analysis
- Correctness of Prim's algorithm
- The cut property
- Correctness of Prim's algorithm

NaN.

Part of course: Learn Algorithms and Data Structures

Prim's algorithm for Minimum Spanning Tree[ Edit ]

Given an *undirected weighted graph*, a minimum spanning tree (MST) is a subset of the edges of the graph which *form a tree* and have the *minimum total edge weight*. For a MST to exist, the graph must be *connected *(that is, every pair of nodes must be reachable from each other)*.*

Prim's algorithm build's the minimum spanning tree **one vertex at a time**. To see what that means, watch the following video.

- Start at an arbitrary node. Mark the node
*visited*. Mark all other nodes*unvisited*. - While there is an unvisited node
- Consider all edges which connect a
*visited*node to an*unvisited*node. Out of these edges, pick the one with the minimum weight. - Mark the
*unvisited*node corresponding to the edge*visited*. Add edge to minimum spanning tree. - Done!

define prims_algorithm(graph):# initializationunvisited = set(all nodes in graph)heap = empty heapMST = empty set# start at an arbitrary nodesource = choose node at randomunvisited.remove(source) # mark visitedfor neighbor of source:# add edge to heap with priority=edge weightheap.insert_with_priority(edge_weight(source, neighbor), (source, neighbor))# while there is an unvisited nodewhile not unvisited.empty():# if heap is empty, graph is disconnectedif heap.empty(): return INFINITY# get minimum-weight edge to an unvisited node from heap# (note: all edges in heap have at-least one end = visited node)edge_weight, (previous, node) = heap.pop()if node not in unvisited: continue # already visited# found new reachable node. mark visited and update MSTunvisited.remove(node)MST.add((previous, node))# add all edges from this node to the heapfor neighbor of node:# add edge to heap with priority=edge weightheap.insert_with_priority(edge_weight(node, neighbor), (node, neighbor))return MST

Given a graph with n nodes and m edges, Prim's algorithm has a run-time of O(m \log m). Since m \leq n^2, this is also O(m \log n). The most expensive operation is heap inserts and heap pops, and we do each operation m times (once per edge).

The main idea behind both Prim's algorithm and Kruskal's algorithm is the cut property.

Consider any subset S of all vertices V of the graph. Consider all edges going from a vertex in S to a vertex outside S. The cut property states that, if e is the edge with minimum weight among all these edges, then e must be part of the minimum spanning tree.

**Proof of cut property**: The proof is quite simple. Assume the contrary, that is, the MST of the graph does not include e. Since the minimum spanning tree spans all vertices, it has at-least one edge e' going from S to outside S. If this edge is replaced by e, we get a spanning tree with lesser weight. This is a contradiction, since the original tree was a *minimum* spanning tree.

In Prim's algorithm, in each step, we consider a cut and choose the minimum weight edge crossing the cut. Each of these edges must be part of the MST, as proved above.

Read more…(406 words)

Mark as completed

Previous

Hands-on: Implementing Dijkstra's algorithm

Next

Kruskal's algorithm for Minimum Spanning Tree

Part of courses:

About the contributor:

Keshav DhandhaniaFormer TopCoder India #1. DM me for 1-on-1 mentorship (paid)

100%

Loading…

Have a question? Ask here…

Post

Part of course:

Prim's algorithm for Minimum Spanning Tree

- Video with step-by-step example
- Algorithm steps
- Pseudo-code
- Run-time analysis
- Correctness of Prim's algorithm
- The cut property
- Correctness of Prim's algorithm

Ready to join our community?

Sign up below to automatically get notified of new courses, get **reminders** to finish ones you subscribe to, and **bookmark** lessons to read later.

Continue with Facebook

— OR —

Your Full Name

Email address

I have an account. Log in instead

By signing up, you agree to our Terms and our Privacy Policy.

Popular Courses

New Courses

About Us

Get in touch

Copyright 2016-18, Compose Labs Inc. All rights reserved.