[Graph Algo Series 4] Minimum Spanning Tree (MST, Undirected Graph) — Prim, Kruskal

Note that it’s recommended to finish reading Graph Algo Series 1 (Basic concepts), 2 (Frequently used techniques) and 3 (Digraph algorithms) first before diving deep into this article :)

MST Definition: a spanning tree of a graph is a connected subgraph with no cycles and includes all vertices. A minimum spanning tree of an edge-weighted graph is a spanning tree whose weight is the smallest among all other spanning trees.

Underlying principles:

• Cut: partition of a graph vertices into two nonempty disjoint sets.
• Crossing edge: an edge that connectsa vertex in one set with a vertex in the other.
• The crossing edge of minimum weight is in the MST of the graph.

Use Greedy Algorithm to find the cut one by one and eventually get to the MST.

Prim’s Algorithm

Start with any vertex, and add V — 1 edges to it, always taking the next minimum weight edge that connects a vertex on the tree to a vertex not yet on the tree. Use a PriorityQueue<Edge> structure to contain the crossing edges. The PriorityQueue should contain all edges from that vertex to any non-tree vertex.

1. Lazy: Defer the removal to later (i.e. when they emerge at the top of the PQ and we are considering to add them to the tree).

Space O(E), time O(ElogE).

  public LazyPrimMST(EdgeWeightedGraph G) {
      mst = new Queue<Edge>();
      pq = new MinPQ<Edge>();
      marked = new boolean[G.V()];
      for (int v = 0; v < G.V(); v++)     // run Prim from all vertices to
          if (!marked[v]) prim(G, v);     // get a minimum spanning forest
  }

  // run Prim's algorithm
  private void prim(EdgeWeightedGraph G, int s) {
      scan(G, s);
      while (!pq.isEmpty()) {                        // better to stop when mst has V-1 edges
          Edge e = pq.delMin();                      // smallest edge on pq
          int v = e.either(), w = e.other(v);        // two endpoints
          if (marked[v] && marked[w]) continue;      // lazy, both v and w already scanned
          mst.enqueue(e);                            // add e to MST
          weight += e.weight();
          if (!marked[v]) visit(G, v);               // v becomes part of tree
          if (!marked[w]) visit(G, w);               // w becomes part of tree
      }
  }

  // add all edges e incident to v onto pq if the other endpoint has not yet been scanned
  private void visit(EdgeWeightedGraph G, int v) {
      assert !marked[v];
      marked[v] = true;
      for (Edge e : G.adj(v))
          if (!marked[e.other(v)]) pq.insert(e);
  }

2. Eager: Remove edges that connecting the newly-added-to-tree vertex and a vertex that is already on the tree proactively from the PQ. Maintain on the PQ just the shortest edge that connects it to the tree for each non-tree vertex. Keep track of the minimum-weight edge and check whether the addition of v to the tree necessitates that we update that minimum.

Space O(V), time O(ElogV).

public PrimMST(EdgeWeightedGraph G) {
    edgeTo = new Edge[G.V()];
    distTo = new double[G.V()];
    marked = new boolean[G.V()];
    pq = new IndexMinPQ<Double>(G.V());
    for (int v = 0; v < G.V(); v++)
        distTo[v] = Double.POSITIVE_INFINITY;

    for (int v = 0; v < G.V(); v++)      // run from each vertex to find
        if (!marked[v]) prim(G, v);      // minimum spanning forest
}

// run Prim's algorithm in graph G, starting from vertex s
private void prim(EdgeWeightedGraph G, int s) {
    distTo[s] = 0.0;
    pq.insert(s, distTo[s]);
    while (!pq.isEmpty()) {
        int v = pq.delMin();
        visit(G, v);
    }
}

// scan vertex v
private void visit(EdgeWeightedGraph G, int v) {
    marked[v] = true;
    for (Edge e : G.adj(v)) {
        int w = e.other(v);
        if (marked[w]) continue;         // v-w is obsolete edge
        if (e.weight() < distTo[w]) {
            distTo[w] = e.weight();
            edgeTo[w] = e;
            if (pq.contains(w)) pq.decreaseKey(w, distTo[w]);
            else                pq.insert(w, distTo[w]);
        }
    }
}

Kruskal’s Algorithm

Process the edges in order of their weighted values, and add to the result tree the edge that doesn’t form a cycle. Stop after adding V — 1 edges have been taken. We use an array (or PQ if it dynamically changes) to order edges by weight, and union-find to identify cycles.

The difference with Prim is that Prim grows a single tree, while Kruskal finds an edge that connects to trees in a forest of growing trees.

Space O(E), time O(ElogE).

 public KruskalMST(EdgeWeightedGraph G) {
    double weight;                        // weight of MST
    Queue<Edge> mst = new Queue<Edge>();  // edges in MST

    // create array of edges, sorted by weight
    Edge[] edges = new Edge[G.E()];
    int t = 0;
    for (Edge e: G.edges()) {
        edges[t++] = e;
    }
    Arrays.sort(edges);

    // run greedy algorithm
    UF uf = new UF(G.V());
    for (int i = 0; i < G.E() && mst.size() < G.V() - 1; i++) {
        Edge e = edges[i];
        int v = e.either();
        int w = e.other(v);

        // v-w does not create a cycle
        if (uf.find(v) != uf.find(w)) {
            uf.union(v, w);     // merge v and w components
            mst.enqueue(e);     // add edge e to mst
            weight += e.weight();
        }
    }
}

Notes:

1. The above algorithms only apply for undirected graph. For directed graph, the problem type is named ‘minimum cost arborescence’.
2. When you are working on related algorithm problems, do take care of assumptions such as: edge weights may be zero or negative, graph is connected or not, edge weights are unique…

Reference: The textbook Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne