BlockLune's Blog | A blog about development and life, powered by Astro.

This is a note for 4.3 Minimum Spanning Trees, Algorithms, Part II.

Introduction

Given. Undirected graph $G$ with positive edge weights (connected).

Def. A spanning tree of $G$ is a subgraph $T$ that is both a tree (connected and acyclic) and spanning (includes all of the vertices).

Goal. Find a min weight spanning tree.

Greedy algorithm

Def. A cut in a graph is a partition of its vertices into two (nonempty) sets.

Def. A crossing edge connects a vertex in one set with a vertex in the other.

Cut property. Given any cut, the crossing edge of min weight is in the MST.

Cut property

Greedy MST algorithm:

Start with all edges colored gray.
Find cut with no black crossing edges; color its min-weight edge black.
Repeat until $V-1$ edges are colored black.

Edge-weighted graph API

Weighted edge

$$ \begin{aligned} \text{public class } &\text{Edge implements Comparable<Edge>}\\ &\text{Edge(int v, int w, double weight)} &\text{create a weighted edge v-w} \\ \text{int }&\text{either()} &\text{either endpoint} \\ \text{int }&\text{other(int v)} &\text{the endpoint that’s not v} \\ \text{int }&\text{compareTo(Edge that)} &\text{compare this edge to that edge} \\ \text{double }&\text{weight()} &\text{the weight} \\ \text{String }&\text{toString()} &\text{string representation} \\ \end{aligned} $$

public class Edge implements Comparable<Edge> {
    private final int v, w;
    private final double weight;

    public Edge(int v, int w, double weight) {
        this.v = v;
        this.w = w;
        this.weight = weight;
    }

    public int either() {
        return v;
    }

    public int other(int vertex) {
        if (vertex == v) {
            return w;
        } else {
            return v;
        }
    }

    public int compareTo(Edge that) {
        if (this.weight < that.weight) return -1;
        else if (this.weight > that.weight) return +1;
        else return 0;
    }
}

Edge-weighted graph

$$ \begin{aligned} \text{public class } &\text{EdgeWeightedGraph}\\ &\text{EdgeWeightedGraph(int V)} &\text{create an empty graph with V vertices} \\ &\text{EdgeWeightedGraph(In in)} &\text{create a graph from input stream} \\ \text{void }&\text{addEdge(Edge e)} &\text{add weighted edge e to this graph} \\ \text{Iterable<Edge> }&\text{adj(int v)} &\text{edges incident to v} \\ \text{Iterable<Edge> }&\text{edges()} &\text{all edges in this graph} \\ \text{int }&\text{V()} &\text{number of vertices} \\ \text{int }&\text{E()} &\text{number of edges} \\ \text{String }&\text{toString()} &\text{string representation} \\ \end{aligned} $$

public class EdgeWeightedGraph {
    private final int V;
    private final Bag<Edge>[] adj; // same as Graph, but adjacency lists of Edges instead of integers

    public EdgeWeightedGraph(int V) {
        this.V = V;
        adj = (Bag<Edge>[]) new Bag[V];
        for (int v = 0; v < V; v++) {
            adj[v] = new Bag<Edge>();
        }
    }

    public void addEdge(Edge e) {
        int v = e.either();
        int w = e.other(v);
        adj[v].add(e);
        adj[w].add(e);
    }

    public Iterable<Edge> adj(int v) {
        return adj[v];
    }
}

Minimum spanning tree API

$$ \begin{aligned} \text{public class } &\text{MST}\\ &\text{MST(EdgeWeightedGraph G)} &\text{constructor} \\ \text{Iterable<Edge> }&\text{edges()} &\text{edges in MST} \\ \text{double }&\text{weight()} &\text{weight of MST} \\ \end{aligned} $$

Kruskal’s algorithm

Consider edges in ascending order (升序) of weight.

Add next edge to tree $T$ unless doing so would create a cycle.

(Kruskal’s algorithm is a special case of the greedy MST algorithm.)

Kruskal’s algorithm: implementation challenge

Challenge. Would adding edge $v-w$ to tree $T$ create a cycle? If not, add it.

Difficulty. Union-find (log* V), DFS (V)

Efficient solution. Use the union-find data structure.

Maintain a set for each connected component in $T$.
If $v$ and $w$ are in same set, then adding $v-w$ would create a cycle.
To add $v-w$ to $T$, merge sets containing $v$ and $w$.

Kruskal’s algorithm: Java implementation

public class KruskalMST {
    private Queue<Edge> mst = new Queue<Edge>();

    public KruskalMST(EdgeWeightedGraph G) {
        MinPQ<Edge> pq = new MinPQ<Edge>();
        for (Edge e : G.edges()) {
            pq.insert(e);
        }

        UF uf = new UF(G.V());
        while (!pq.isEmpty() && mst.size() < G.V() - 1) {
            Edge e = pq.delMin();
            int v = e.either();
            int w = e.other(v);
            if (!uf.connected(v, w)) {
                uf.union(v, w);
                mst.enqueue(e);
            }
        }
    }

    public Iterable<Edge> edges() {
        return mst;
    }
}

Kruskal’s algorithm: running time

Kruskal’s algorithm computes MST in time proportional to $E \log E$ (in the worst case).

operation	frequency	time per op
build pq	1	E log E
delete-min	E	log E
union	V	log* V (*)
connected	E	log* V (*)

* amortized (摊销的) bound using weighted quick union with path compression

Prim’s algorithm

Start with vertex $0$ and greedily grow tree $T$.
Add to $T$ the min weight edge with exactly one endpoint in $T$.
Repeat until $V-1$ edges.

(Prim’s algorithm is a special case of the greedy MST algorithm.)

Prim’s algorithm: implementation challenge

Challenge. Find the min weight edge with exactly one endpoint in $T$. Difficulty. try all edges (E), priority queue (log E)

Prim’s algorithm: lazy implementation

Lazy solution. Maintain a PQ of edges with (at least) one endpoint in $T$.

Key = edge; priority = weight of edge.
Delete-min to determine next edge $e=v-w$ to add to $T$.
Disregard (忽略) if both endpoints $v$ and $w$ are marked (both in $T$).
Otherwise, let $w$ be the unmarked vertex (not in $T$):
- add to PQ any edge incident to $w$ (assuming other endpoint not in $T$)
- add $e$ to $T$ and mark $w$

public class LazyPrimMST {
    private boolean[] marked;  // MST vertices
    private Queue<Edge> mst;   // MST edges
    private MinPQ<Edge> pq;    // PQ of edges

    public LazyPrimMST(WeightedGraph G) {
        pq = new MinPQ<Edge>();
        mst = new Queue<Edge>();
        marked = new boolean[G.V()];
        visit(G, 0);

        while (!pq.isEmpty() && mst.size() < G.V() - 1) {
            Edge e = pq.delMin();
            int v = e.either(), w = e.other(v);
            if (marked[v] && marked[w]) continue;
            mst.enqueue(e);
            if (!marked[v]) visit(G, v);
            if (!marked[w]) visit(G, w);
        }
    }

    private void visit(WeightedGraph G, int v) {
        marked[v] = true;
        for (Edge e : G.adj(v)) {
            if (!marked[e.other(v)]) {
                pq.insert(e);
            }
        }
    }

    public Iterable<Edge> mst() {
        return mst;
    }
}

Lazy Prim’s algorithm: running time

Lazy Prim’s algorithm computes the MST in time proportional to $E\log E$ and extra space proportional to $E$ (in the worst case).

operation	frequency	binary heap
delete min	E	log E
insert	E	log E

Prim’s algorithm: eager implementation

Eager solution. Maintain a PQ of vertices (pq has at most one entry per vertex) connected by an edge to $T$, where priority of vertex $v=$ weight of shortest edge connecting $v$ to $T$.

Delete min vertex $v$ and add its associated edge $e=v-w$ to $T$.
Update PQ by considering all edges $e=v-w$ incident to $v$
- ignore if $x$ is already in $T$
- add $x$ to PQ if not already on it
- decrease priority of $x$ if $v-w$ becomes shortest edge connecting $x$ to $T$

Indexed priority queue

Associate an index between $0$ and $N-1$ with each key in a priority queue.

Client can insert and delete-the-minimum.
Client can change the key by specifying the index.

$$ \begin{aligned} \text{public class } &\text{IndexMinPQ<Key extends Comparable<Key>>}\\ &\text{IndexMinPQ(int N)} &\text{create indexed priority queue with indices 0, 1, …, N-1} \\ \text{void }&\text{insert(int i, Key key)} &\text{associate key with index i} \\ \text{void }&\text{decreaseKey(int i, Key key)} &\text{decrease the key associated with index i} \\ \text{boolean }&\text{contains(int i)} &\text{is i an index on the priority queue} \\ \text{int }&\text{delMin()} &\text{remove a minimal key and return its associated index} \\ \text{boolean }&\text{isEmpty()} &\text{is the priority queue empty?} \\ \text{int }&\text{size()} &\text{number of entries in the priority queue} \\ \end{aligned} $$

Implementation.

Start with same code as MinPQ.
Maintain parallel arrays keys[], pq[], and qp[] so that:
- keys[i] is the priority of i
- pq[i] is the index of the key in heap position i
- qp[i] is the heap position of the key with index i
Use swim(qp[i]) implement decreaseKey(i, key).

Personal Summery

Kruskal 算法

实现步骤：

按照边的权重升序排序
在确保不会产生环的情况下，逐个将边加入到生成树中

前置算法 / 数据结构：

优先队列
- C++ std::priority_queue - cppreference
- Java java.util.PriorityQueue - 菜鸟教程
- Python queue.PriorityQueue
并查集

Prim 算法