CS61B Guide
  • This site is now deprecated
  • Object Oriented Programming
    • Inheritance
    • Access Control
    • Dynamic Method Selection
    • Java Objects
    • Generic Types
  • Asymptotics
    • Asymptotic Analysis Basics
    • Amortization
    • Asymptotics Practice
  • Abstract Data Types
    • Collections
      • Arrays
      • Linked Lists
      • Sets
      • Stacks and Queues
    • Binary Trees
      • Heaps
      • Balanced BSTs
      • Tries
    • Graphs
    • Hashing and Hash Tables
    • Union Find (Disjoint Sets)
    • Comparables and Comparators
  • Sorting
    • Sorting
  • Algorithms
    • Minimax Algorithm
    • Searching
      • Binary Search
      • Depth First Search (DFS)
      • Breadth First Search (BFS)
    • Shortest Paths
      • Dijkstra's Algorithm
      • A* Search
    • Minimum Spanning Trees
      • Prim's Algorithm
      • Kruskal's Algorithm
  • Misc Topics
    • Modular Arithmetic and Bit Manipulation
    • Exceptions
    • More Resources
Powered by GitBook
On this page
  • Conceptual Overview
  • Detailed Breakdown
  • Useful Properties/Invariants
  • Pseudocode
  • Runtime Analysis
  • Demo

Was this helpful?

  1. Algorithms
  2. Minimum Spanning Trees

Prim's Algorithm

Special thanks to Arin for writing this page!

PreviousMinimum Spanning TreesNextKruskal's Algorithm

Last updated 5 years ago

Was this helpful?

Before reading, review , as that is the foundation of Prim's algorithm!

Conceptual Overview

Prim's algorithm is an optimal way to construct a minimum spanning tree. It basically starts from an arbitrary vertex, then considers all its immediate neighbors and picks the edge with smallest weight to be part of the MST. Note: this creates a cut in the graph, where the two nodes in the MST being constructed are in one set, and every other vertex of the graph is in another set.

Now, the edges taken into consideration include all immediate neighbors of every node in the MST. Add the edge that has the smallest weight to the MST. Repeat until every vertex has been visited. The result is an MST for the graph.

Detailed Breakdown

The way Prim's algorithm is usually implemented is via , edgeTo array, and distTo array. You will soon see its similarities to .

First, insert all vertices into the PriorityQueue, storing vertices in order of distance from MST. Then, remove vertex with highest priority in the PriorityQueue and relax its edges. In each of these iterations, the distTo and edgeTo arrays will be updated for each vertex v if the weight of the edge is smaller than the current value in distTo[v]. In other words, only update if the distance from the MST to the vertex is the best seen so far. This is a very important point, and is one of the subtleties that makes Prim's algorithm fundamentally different from Dijkstra's.

Useful Properties/Invariants

The MST under construction is always connected.

Pseudocode

public class Prims() {

    public Prims() {
        PQ = new PriorityQueue<>();
        edgeTo = new Edge[numVertices];
        distTo = new Dist[numVertices];
        marked = new boolean[numVertices];
    }

    public void doPrims() {
        PQ.add(sourceVertex, 0);
        for(v : allOtherVertices) {
            PQ.add(v, INFINITY);
        }
        while (!PQ.isEmpty()) {
            Vertex p = PQ.removeSmallest();
            marked[p] = true;
            relax(p);
        }
    }

    public void relax(Vertex p) {
        for (q : p.neighbors()) {
            if (marked[q]) { continue; }
            if (q.edgeWeight < distTo[q]) {
                distTo[q] = q.edgeWeigth;
                edgeTo[q] = p;
                PQ.changePriority(q, distTo[q]);
            }
        }
    }
}

Looking at this pseudocode, the resemblance to Dijkstra's makes them seem nearly identical. But hopefully you've read the conceptual overviews first, and you understand the remarkable subtlety that leads to two very fundamentally different algorithms.

Runtime Analysis

This is the same as for Dijkstra's Algorithm.

Unsimplified:

θ(V∗log(V)+V∗log(V)+E∗log(V))\theta(V * log(V) + V * log(V) + E * log(V))θ(V∗log(V)+V∗log(V)+E∗log(V))

Simplified:

θ(E∗log(V))\theta(E * log(V))θ(E∗log(V))

Explanation:

  • each add operation to PQ takes log(V), and perform this V times

  • each removeFirst operation to PQ takes log(V) and perform this V times

  • each change priority operation to PQ takes log(V), perform this at most as many times as there are edges

  • everything else = O(1)

  • usually, there are more or equal edges compared to the number of vertices.

Demo

Minimum Spanning Trees
PriorityQueue
Dijkstra's
https://docs.google.com/presentation/d/1GPizbySYMsUhnXSXKvbqV4UhPCvrt750MiqPPgU-eCY/edit#slide=id.g9a60b2f52_0_0