Minimum Spanning Tree (MST).
The application scenario and premise of minimum spanning tree algorithm
- Connected graph: in the case of fully connected, there is a minimum spanning tree;
- Undirected graph: Minimum spanning tree algorithm is to solve such a kind of problem, from any vertex can reach other vertices of the graph, and cost the least, so one-way graph is not suitable for this scene;
- Weighted graph: If you have no right, you can consider the weight is 111, and the weighted case is more widely applied.
In the case of unconnected, each maximally connected subgraph has a minimum spanning tree, and a minimum spanning forest is formed. To simplify the problem, we will only talk about the minimum spanning tree in the fully connected case.
application
Wiring design: an edge can connect all vertices with minimal cost.
The theoretical basis of two algorithms: the segmentation theorem
What is syncopation
The nodes in the graph are divided into two parts, called a Cut. If two endpoints of an Edge are on different sides of the Cut, the Edge is called a Crossing Edge.
The cutting theorem tells us that for any cutting, the shortest crosscutting edge must belong to the minimum spanning tree
Segmentation theorem: In a weighted graph, given any segmentation, the edge with the least weight among all crosscutting edges must belong to the minimum spanning tree of the graph.
The key word of the segmentation theorem is “arbitrary”.
Description:
- It’s important that this is true for any given slice;
- With the cutting theorem, you can start with one vertex and spread out bit by bit until you find all the vertices, and the minimum spanning tree is found.
Understand the segmentation theorem
The key to understanding the segmentation theorem is two properties of trees:
- Property 1: a tree connects two vertices arbitrarily, forming a ring;
- Property 2: A tree will split into two trees if any edge is deleted.
Supplementary notes:
- A tree is a connected graph, from which one vertex can reach any vertex in the graph.
- Connecting any two vertices of different trees forms a larger tree.
Prove the segmentation theorem
The proof of the segmentation theorem can be proved by “proof by contradiction”, which seems to say nothing at all.
Proof:
- If we choose the crosscut edge (E1) that is not the shortest, we get the minimum spanning tree.
- Since there is the shortest crosscutting edge (E2), add the shortest crosscutting edge to form a ring;
- At this point, we remove the edge (E1) initially selected, and the ring becomes a tree. Since E2 < E1, we find a spanning tree with smaller sum of weights, which is in contradiction with the minimality of the initial “minimum spanning tree”. Therefore, for any segmentation, the shortest edge in the crosscut must belong to the “minimum spanning tree”.
Let’s start with The Kruskal algorithm, because its description is very simple, and the implementation of the Kruskal algorithm needs to use and look up the set. Then introduce Prim algorithm, Prim algorithm implementation needs to use priority queue.
Kruskal algorithm
Based on the segmentation theorem, the edges are arranged in order of weight from small to large, and taken out one by one. If a ring is formed, the current edge is discarded until the edge with “vertices -1” is found, and the minimum spanning tree is found.
Let’s start with the picture below.
Edge “2-6” is the shortest edge at this time. After we pick this edge, we mark the two vertices of this edge in red, and a segmentation occurs.
We then select the shortest edge “2-3” among the black edges and mark vertex 3 in red, at which point another shard occurs.
We then select the shortest edge “3-4” among the black edges and label vertex 4 in red, at which point another shard occurs.
Then we select the shortest edge “0-1” among the black edges, and label the two vertices of this edge in red, at which point another sharding occurs.
Now the shortest edge is edge “4-6” and since vertex 4 and vertex 6 are both in the red camp, it’s not a crosscutting edge, so get rid of it and pick the shortest edge “5-6” out of the rest of the black edges.
Now, even though all the vertices are red, they’re currently separated, so the whole thing looks like a shard. Pick the shortest side, there are two shortest sides, just pick one of them.
The minimum spanning tree is shown as follows:
Here is the code implementation, in order to highlight the idea of the algorithm, we simplify the coding, save a lot of judgment.
Reference Code 1:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
public class Kruskal {
/** * The sum of weights of the minimum spanning tree */
private int mstCost;
public int getMstCost(a) {
return mstCost;
}
/** * Minimum spanning tree edge list */
private List<int[]> mst;
public List<int[]> getMst() {
return mst;
}
/ * * *@param V
* @paramDefinition of each edge of edges: [starting point, end point, weight] */
public Kruskal(int V, int[][] edges) {
int E = edges.length;
if (E < V - 1) {
throw new IllegalArgumentException("Parameter error");
}
mst = new ArrayList<>(E - 1);
// Start with the edge with the least weight
Arrays.sort(edges, Comparator.comparingInt(o -> o[2]));
UnionFind unionFind = new UnionFind(V);
// How many edges are currently found
int count = 0;
for (int[] edge : edges) {
// If a ring is formed, proceed to the next edge
if (unionFind.isConnected(edge[0], edge[1]) {continue;
}
unionFind.union(edge[0], edge[1]);
this.mstCost += edge[2];
mst.add(new int[]{edge[0], edge[1], edge[2]});
count++;
if (count == V - 1) {
break; }}}private class UnionFind {
private int[] parent;
private int count;
private int N;
public UnionFind(int N) {
this.N = N;
this.count = N;
this.parent = new int[N];
for (int i = 0; i < N; i++) { parent[i] = i; }}public int find(int x) {
while(x ! = parent[x]) { x = parent[x]; }return x;
}
public void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) {
return;
}
parent[rootX] = rootY;
count--;
}
public int getCount(a) {
return count;
}
public boolean isConnected(int x, int y) {
returnfind(x) == find(y); }}public static void main(String[] args) {
int N = 7;
int[][] edges = {{0.1.4},
{0.5.8},
{1.2.8},
{1.5.11},
{2.3.3},
{2.6.2},
{3.4.3},
{4.5.8},
{4.6.6},
{5.6.7}}; Kruskal kruskal =new Kruskal(N, edges);
int mstCost = kruskal.getMstCost();
System.out.println("Sum of weights of minimum spanning tree:" + mstCost);
List<int[]> mst = kruskal.getMst();
System.out.println("List of minimum spanning tree edges:");
for (int[] edge : mst) {
System.out.println("[" + edge[0] + "-" + edge[1] + "]" + ", weight:" + edge[2]); }}}Copy the codeComplexity analysis:
- Time complexity: O(ElogE)O(E \log E)O(ElogE), where EEE is the number of edges of the graph;
- Space complexity: O(V)O(V)O(V), where VVV is the number of vertices in the graph, and the search set requires a vvV-length array space.
Prim algorithm
Based on the segmentation theorem, we can start from any vertex and spread out bit by bit, forming different slices in the process of diffusion. We can choose the shortest edge of crosscut from different slices until all vertices are found (or until the edge of “vertices -1” is found), and the minimum spanning tree is found.
Let’s look at a specific example:
The original diagram looks like this.
So let’s start at any vertex, let’s pick vertex zero here. The following sharding is formed, with edge “0-1” and edge “0-5” as the crosscutting edges of the current sharding.
Select the shortest crosscut edge “0-1” (length 444), join the set S, and then put 1 into the red camp to form a new shards. So let’s take all of the adjacent edges to vertex one, which are crosscutting edges, and add them to S.
Pick the shortest crosscut edge, there are two crosscuts of equal length, just pick any one of them, here we pick the edge “1-2”. So let’s take all the adjacent edges of vertex two, which are crosscutting edges, and add them to S.
Select the shortest crosscutting edge “2-6” and add all adjacent edges of vertex 2 to S, they are crosscutting edges.
Select the shortest crosscutting edge “2-3” and add all adjacent edges of vertex 3 to S, they are crosscutting edges.
Select the shortest crosscutting edge “3-4” and add all adjacent edges of worry vertex 4 to S. Please note: at this point, the edge “4-6” that was previously crosscutting edge is no longer crosscutting edge. Although we found this, the program cannot see it at this time.
Then the shortest edge “4-6” in set S is selected, and the program checks to see if “4-6” is a crosscutting edge. So the program always checks to see if an edge is crosscut when it’s pulled out, and if it’s not, it drops it.
Next, from the shortest edge “5-6” in set S, we find 6 edges. “7 vertices and 6 edges” form the minimum spanning tree.
Prim algorithm looks for the “minimum spanning tree” like this: it starts with no shards, gradually forms shards, and finally returns to no shards.
Reference Code 2:
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Set;
public class Prim {
private int mstCost;
public int getMstCost(a) {
return mstCost;
}
private List<int[]> mst;
public List<int[]> getMst() {
return mst;
}
public Prim(int V, int[][] edges) {
int len = edges.length;
if (len < V - 1) {
throw new IllegalArgumentException("Parameter error");
}
mst = new ArrayList<>(len - 1);
Set<int[]>[] adj = new HashSet[V];
for (int i = 0; i < V; i++) {
adj[i] = new HashSet<>();
}
for (int[] edge : edges) {
// [from, to, weight]
adj[edge[0]].add(new int[]{edge[0], edge[1], edge[2]});
adj[edge[1]].add(new int[]{edge[1], edge[0], edge[2]});
}
boolean[] visited = new boolean[V];
visited[0] = true;
// PriorityQueue<int[]> minHeap = new PriorityQueue<>(len, (o1, o2) -> o1[2] - o2[2]);
PriorityQueue<int[]> minHeap = new PriorityQueue<>(len, Comparator.comparingInt(o -> o[2]));
minHeap.addAll(adj[1]);
int count = 0;
while(! minHeap.isEmpty()) {int[] edge = minHeap.poll();
if (visited[edge[0]] && visited[edge[1]]) {
continue;
}
this.mstCost += edge[2];
mst.add(new int[]{edge[0], edge[1], edge[2]});
count++;
if (count == (V - 1)) {
break;
}
int newV;
if (visited[edge[0]]) {
newV = edge[1];
} else {
newV = edge[0];
}
visited[newV] = true;
for (int[] successor : adj[newV]) {
if(! visited[successor[1]]) { minHeap.add(successor); }}}}public static void main(String[] args) {
int V = 7;
int[][] edges = {{0.1.4},
{0.5.8},
{1.2.8},
{1.5.11},
{2.3.3},
{2.6.2},
{3.4.3},
{4.5.8},
{4.6.6},
{5.6.7}}; Prim prim =new Prim(V, edges);
int mstCost = prim.getMstCost();
System.out.println("Sum of weights of minimum spanning tree:" + mstCost);
List<int[]> mst = prim.getMst();
System.out.println("List of minimum spanning tree edges:");
for (int[] edge : mst) {
System.out.println("[" + edge[0] + "-" + edge[1] + "]" + ", weight:" + edge[2]); }}}Copy the codeComplexity analysis:
- Time complexity: O(ElogE)O(E \log E)O(ElogE), where EEE is the number of edges of the graph;
- Space complexity: O(E)O(E)O(E), worst case, all edges should be in the priority queue.
The Prim algorithm we introduce here is also called lazy Prim. In fact, the time complexity of the search set can also be optimized to ElogVE \log VElogV (generally, V
The index heap is actually a heap (priority queue). This data structure does not operate on data directly, but on indexes of data, which can achieve additional benefits:
- It is convenient to locate the weight of the edge where the vertex is;
- Changes can be made and the index heap automatically adjusts its structure.
The index heap can be found in the book algorithms (4th edition), which we will not cover here.
conclusion
Both Kruskal algorithm and Prim algorithm of minimum spanning tree are based on the “cutting theorem”. Let’s review again: “The shortest edge of any crosscutting edge must be a minimum spanning tree of data”.
- The Kruskal algorithm starts with the shortest edge, one by one, and if the newly considered edge forms a ring with the one already considered, it is discarded and the next edge is considered.
- Prim algorithm can start from any vertex to form segmentation, consider the shortest crosscutting edge, and then consider the edges that have not been taken into account. Finally, when the segmentation disappears, the minimum spanning tree can be found.
An exercise in minimum spanning trees on “Force link”.
- “Force buckle” 1135: the lowest cost unicom all cities;
- 1168: Optimization of water resources allocation;
- Problem 1489: Find critical and pseudo-critical edges in the minimum spanning tree