4.3 Minimum Spanning Tree 笔记+理解

• Given a connected undirected graph, a spinning tree is a connected, acyclic subgraph that contains all the vertices;
• and a MST is a spinning tree that has the min. weights.

Cut:

• A cut partitions the vertices into two nonempty sets;
• A crossing edge connects the two sets partitioned by the cut;

Cut property:

The crossing edge that has the min. weight of a cut is in the MST.
Pf: Given a cut, assume the min. crossing edge is not in the MST.

• Adding to the MST will form a cycle, and in that cycle, there must be a crossing edge of that cut.
• Replace with will still form a spanning tree, but now the newly formed spanning tree has less weight than the original MST.

• So contradiction.

  
  
  image

Greedy Algorithm for MST

• start with all edges uncolored
• choose a cut that has no colored crossing edge, color the min. weight edge
• until there are colored edges

Pf [correctness]:

• edges colored are in the MST (cut property)
• if there're less than edges, then there must be cuts that have uncolored crossing edges (the graph is connected)

Implementations:

Prim's Algorithm:

• Start from any of the vertices,
• greedily growing the tree so that the next edge added would be the min. weight edge that connects the existing MST to the unvisited vertices color the min. crossing edge in a cut that partitions the MST and the unvisited vertices.
• until there're edges
  Pf [correctness]:
  It's just a special case for the greedy algorithm for the MST!!

Lazy Prim's Implementation

Edge.java

Edge API

EdgeWeightedGraph.java

EdgeWeightedGraph API

Public void LazyPrimMST(EdgeWeightedGraph G) {
    boolean[] marked = new boolean[G.V()];
    MinPQ<Edge> pq = new MinPQ<>();
    Queue<Edge> mst = new Queue<>();
    visit(G, 0);
    while (!pq.isEmpty()) {
        Edge e = pq.delMin();
        int v = e.either(); int w = e.other(v);
        if (marked[v] && marked[w]) { continue; }
        if (!marked[v]) { visit(G, v); }
        if (!marked[w]) { visit(G, w); }
    }
}

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

Running time:

• At most edges in the priority queue takes ~ to insert(), ~ to delMin()
• At most edges to insert and delete, so ~

Eager Prim's Implementation:

Every time the tree grows (adding to the MST), update the min. weight edges between the no-tree vertices adj. to and the tree.

When we add a vertex v to the tree, the only possible change with respect to each non- tree vertex w is that adding v brings w closer than before to the tree. In short, we do not need to keep on the priority queue all of the edges from w to tree vertices—we just need to keep track w of the minimum-weight edge and check whether the addition of v to the tree necessitates that we update that minimum (be- cause of an edge v-w that has lower weight), which we can do as we process each edge in v’s adjacency list.

public void EagerPrimMST(EdgeWeightedGraph G) {
    marked = new boolean[G.V()];
    // min. distance from a non-tree vertex v to the MST
    distTo = new double[G.V()]; 
    for (int v = 0; v < G.V(); v++) {
        distTo[v] = INFINITY;
    }
    // min. weight edge from a non-tree vertex v to the MST
    edgeTo = new Edge[G.V()];

    // key is vertex
    // priority is the min. distance to the tree
    pq = new IndexMinPQ<Double>(G.V());

    pq.insert(0, 0.0); // start from vertex 0
    distTo[0] = 0.0;
    while (!pq.isEmpty()) {
        // Add closest vertex to tree.
        visit(G, pq.delMin());
    }
}

private void visit(... G, int v) {
    marked[v] = true;
    for (Edge e : G.adj(v)) {
        int w = e.other(v)
        if (marked[e.other(v)]) { continue; }
        if (e.weight() < distTo[w]) {
            // update if there's closer path from w to the tree
            edgeTo[w] = e;
            distTo[w] = e.weight();
            // update the index pq
            if (pq.contains(w)) { pq.change(w, e.weight()); } // at most E times
            else { pq.insert(w, e.weight()); } // at most V times
        }
    }
}

Running time:

• pq contains at most , so pq operation ~
• inserts, deletes, and changes
• total ~

Kruskal's Algorithm:

• sort the edges by weights in ascending order
• add the edges to the tree in the order as long as the edge to be added wouldn't form a cycle
• until edges are added

how to check cycle?
use Union Find ~ lg V

• if vertex v and w are already connected, then adding the edge v-w will form a cycle
• if not, v-w will union the two sets

public void KruskalMST(... G) {
    MinPQ<Edge> pq = new MinPQ<>();
    UF uf = new UF(G.V())
    for (Edge e : G.E()) { // ~ElogE
        pq.insert(e);
    }
    while (!pq.isEmpy()) { // E times
        Edge e = pq.delMin(); // ~ log E
        int v = e.either(); int w = e.other(v);
        if (!uf.connected(v, w)) { // ~ lg V
            mst.enqueue(e);
            uf.connect(v, w);  // ~ lg V
        }
    }
}

Running time: ~