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

Introduction

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

Def. A spanning tree of is a subgraph 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.

Greedy MST algorithm:

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

Edge-weighted graph API

Weighted edge

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

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

Kruskal’s algorithm

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

• Add next edge to tree 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 to tree 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 .
• If and are in same set, then adding would create a cycle.
• To add to , merge sets containing and .

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 (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 and greedily grow tree .
• Add to the min weight edge with exactly one endpoint in .
• Repeat until 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 . 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 .

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

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 and extra space proportional to (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 , where priority of vertex weight of shortest edge connecting to .

• Delete min vertex and add its associated edge to .
• Update PQ by considering all edges incident to
  • ignore if is already in
  • add to PQ if not already on it
  • decrease priority of if becomes shortest edge connecting to

Indexed priority queue

Associate an index between and with each key in a priority queue.

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

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 算法

实现步骤：

• 选定一个起始顶点（比如 ）
• 从起始顶点开始，贪心地扩展生成树。具体方法是：找到与已经生成的树相连的权重最小的边，并把它加入到生成树中
• 重复该过程直到生成树的边数达到

Lazy 实现使用优先队列存储至少一个端点在生成树中的边，通过删除最小值操作来选择要加入生成树的边。如果边的两个端点都已标记，则忽略该边；否则，将未标记的顶点加入到生成树中并将与之相连的边添加到优先队列中。

Eager 实现使用优先队列存储与生成树相连的顶点，每个顶点的优先级表示连接该顶点与生成树的最短边的权重。通过删除最小顶点并更新优先队列来选择要加入生成树的边。