什么是最小生成树?
一个有 n 个结点的连通图的生成树是原图的极小连通子图,且包含原图中的所有 n 个结点,并且有保持图连通的最少的边。最小生成树可以用kruskal(克鲁斯卡尔)算法或prim(普里姆)算法求出。
概述
在一给定的无向图G = (V, E) 中,(u, v) 代表连接顶点 u 与顶点 v 的边(即),而 w(u, v) 代表此边的权重,若存在 T 为 E 的子集且为无循环图,使得的 w(T) 最小,则此 T 为 G 的最小生成树。
最小生成树其实是最小权重生成树的简称
应用
例如:要在n个城市之间铺设光缆,主要目标是要使这 n 个城市的任意两个之间都可以通信,但铺设光缆的费用很高,且各个城市之间铺设光缆的费用不同,因此另一个目标是要使铺设光缆的总费用最低。这就需要找到带权的最小生成树。
关于图的几个概念定义:
- 连通图:在无向图中,若任意两个顶点vivi与vjvj都有路径相通,则称该无向图为连通图。
- 强连通图:在有向图中,若任意两个顶点vivi与vjvj都有路径相通,则称该有向图为强连通图。
- 连通网:在连通图中,若图的边具有一定的意义,每一条边都对应着一个数,称为权;权代表着连接连个顶点的代价,称这种连通图叫做连通网。
- 生成树:一个连通图的生成树是指一个连通子图,它含有图中全部n个顶点,但只有足以构成一棵树的n-1条边。一颗有n个顶点的生成树有且仅有n-1条边,如果生成树中再添加一条边,则必定成环。
以下代码会用到的数据类型:
/*
* 图中的边
*/
public class Edge implements Comparable<Edge> {
private final int v;
private final int w;
private int weight;
public Edge(int v, int w, int 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 getWeight() {
return weight;
}
@Override
public int compareTo(Edge o) {
if (this.weight > o.weight) {
return 1;
} else if (this.weight < o.weight) {
return -1;
} else {
return 1;
}
}
@Override
public String toString() {
return "Edge{" + "v=" + v + ", w=" + w + ", weight=" + weight + '}';
}
}
/*
* 无向连通图的数据类型
*/
public class EdgeWeightedGraph {
private final int V;
private int E;
private LinkedList<Edge>[] adj;
public EdgeWeightedGraph(int V) {
this.V = V;
this.E = 0;
this.adj = (LinkedList<Edge>[]) new LinkedList[V];
for (int v = 0; v < V; v++) {
adj[v] = new LinkedList<Edge>();
}
}
public int V() {
return V;
}
public int E() {
return E;
}
public void addEdge(Edge e) {
int v = e.either();
int w = e.other(v);
adj[v].add(e);
adj[w].add(e);
E++;
}
public LinkedList<Edge> edges() {
LinkedList<Edge> b = new LinkedList<>();
for (int v = 0; v < V; v++) {
for (Edge e : adj[v]) {
if (e.other(v) > v) {
b.add(e);
}
}
}
return b;
}
public Iterable<Edge> adj(int v) {
return adj[v];
}
}
下面介绍两种求最小生成树算法
1.Kruskal算法
此算法可以称为加边法,初始最小生成树边数为0,每迭代一次就选择一条满足条件的最小代价边,加入到最小生成树的边集合里。
- 把图中的所有边按代价从小到大排序;
- 把图中的n个顶点看成独立的n棵树组成的森林;
- 按权值从小到大选择边,所选的边连接的两个顶点 ui , vi。ui , vi,应属于两颗不同的树,则成为最小生成树的一条边,并将这两颗树合并作为一颗树。
- 重复(3),直到所有顶点都在一颗树内或者有n-1条边为止。
此算法需要用到 并查集(Union-Find) 的知识,不懂得同学请先点击这里Union-Find查看有关知识。
代码如下:
并查集:
public class UF {
private int[] id;
private int count;
public UF(int N) {
count = N;
id = new int[N];
for (int i = 0; i < N; i++) {
id[i] = i;
}
}
public int count() {
return count;
}
public boolean connected(int p, int q) {
return find(p) == find(q);
}
public int find(int p) {
while (p != id[p]) {
p = id[p];
}
return p;
}
public void union(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot) {
return;
}
id[pRoot] = qRoot;
count--;
}
}
public class KruskalMST {
private Queue<Edge> mst; // 存储最小生成树的每条边
private Queue<Edge> pq; // 优先队列,获取权重最小的边
private int weight; // 权重和
public KruskalMST() {
}
public void kruskalMST(EdgeWeightedGraph G) {
mst = new LinkedList<Edge>();
pq = new PriorityQueue<Edge>();
for (Edge e : G.edges()) {
pq.offer(e);
}
UF uf = new UF(G.V());
while (!pq.isEmpty() && mst.size() < G.V() - 1) {
Edge e = pq.poll(); // 从pq中获得权重最小的边和它的顶点
int v = e.either();
int w = e.other(v);
if (!uf.connected(v, w)) { // 如果v和w不构成环
uf.union(v, w); // 合并分量
mst.offer(e); // 将边添加到最小生成树中
}
}
printKruskalMST();
}
private void printKruskalMST() {
while (!mst.isEmpty()) {
Edge e = mst.poll();
weight += e.getWeight();
System.out.println(e);
}
System.out.println("总权重为:"+weight);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
int V = sc.nextInt();
int E = sc.nextInt();
EdgeWeightedGraph edgeWeightedGraph = new EdgeWeightedGraph(V);
for (int i = 0; i < E; i++) {
Edge e = new Edge(sc.nextInt() - 1, sc.nextInt() - 1, sc.nextInt());
edgeWeightedGraph.addEdge(e);
}
KruskalMST kruskal = new KruskalMST();
kruskal.kruskalMST(edgeWeightedGraph);
}
}
}
测试如下:
L:\jdk-11.0.2\bin\java.exe "-javaagent:L:\IDEA\IntelliJ IDEA 2018.3.5\lib\idea_rt.jar=60157:L:\IDEA\IntelliJ IDEA 2018.3.5\bin" -Dfile.encoding=UTF-8 -classpath C:\Users\lwj\Desktop\数据结构与算法\out\production\algorithms Main.Tree.KruskalMST
6 10
1 3 1
1 2 6
1 4 5
2 3 5
2 5 3
3 5 6
3 4 5
3 6 4
4 6 2
6 5 6
Edge{v=0, w=2, weight=1}
Edge{v=3, w=5, weight=2}
Edge{v=1, w=4, weight=3}
Edge{v=2, w=5, weight=4}
Edge{v=1, w=2, weight=5}
总权重为:15
2.Prim算法
此算法可以称为“加点法”,每次迭代选择代价最小的边对应的点,加入到最小生成树中。算法从某一个顶点s开始,逐渐长大覆盖整个连通网的所有顶点。
- 图的所有顶点集合为VV;初始令集合u=,v=V−uu=,v=V−u;
- 在两个集合u,vu,v能够组成的边中,选择一条代价最小的边(u0,v0)(u0,v0),加入到最小生成树中,并把v0v0并入到集合u中。
- 重复上述步骤,直到最小生成树有n-1条边或者n个顶点为止。
代码如下:
public class PrimMST {
private boolean[] marked;
private Queue<Edge> mst;
private Queue<Edge> pq;
public void primMST(EdgeWeightedGraph G) {
pq = new PriorityQueue<Edge>();
marked = new boolean[G.V()];
mst = new LinkedList<Edge>();
visit(G, 0);
while (!pq.isEmpty()) {
Edge e = pq.poll();
int v = e.either();
int w = e.other(v);
if (marked[v] && marked[w]) continue;
mst.offer(e);
if (!marked[v]) visit(G, v);
if (!marked[w]) visit(G, w);
}
printMST();
}
private void visit(EdgeWeightedGraph G, int v) {
marked[v] = true;
for (Edge e : G.adj(v)) {
if (!marked[e.other(v)]) {
pq.offer(e);
}
}
}
private void printMST() {
while (!mst.isEmpty()) {
Edge e = mst.poll();
weight += e.getWeight();
System.out.println(e);
}
System.out.println("总权重为:"+weight);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
int V = sc.nextInt();
int E = sc.nextInt();
EdgeWeightedGraph edgeWeightedGraph = new EdgeWeightedGraph(V);
for (int i = 0; i < E; i++) {
Edge e = new Edge(sc.nextInt() - 1, sc.nextInt() - 1, sc.nextInt());
edgeWeightedGraph.addEdge(e);
}
PrimMST primMST = new PrimMST();
primMST.primMST(edgeWeightedGraph);
}
}
}
测试如下:
L:\jdk-11.0.2\bin\java.exe "-javaagent:L:\IDEA\IntelliJ IDEA 2018.3.5\lib\idea_rt.jar=60266:L:\IDEA\IntelliJ IDEA 2018.3.5\bin" -Dfile.encoding=UTF-8 -classpath C:\Users\lwj\Desktop\数据结构与算法\out\production\algorithms Main.Tree.PrimMST
6 10
1 3 1
1 2 6
1 4 5
2 3 5
2 5 3
3 5 6
3 4 5
3 6 4
4 6 2
6 5 6
Edge{v=0, w=2, weight=1}
Edge{v=2, w=5, weight=4}
Edge{v=3, w=5, weight=2}
Edge{v=1, w=2, weight=5}
Edge{v=1, w=4, weight=3}
总权重为:15
对比
总结
克鲁斯卡尔(Kruskal)算法因为只与边相关,则适合求稀疏图的最小生成树。而prime算法因为只与顶点有关,所以适合求稠密图的最小生成树。 无疑,Kruskal算法在效率上要比Prim算法快,因为Kruskal只需要对权重边做一次排序,而Prim算法则需要做多次排序。尽管Prim算法每次做的算法涉及的权重边不一定会涵盖连通图中的所有边,但是随着所使用的排序算法的效率的提高,Kruskal算法和Prim算法之间的差异将会清晰的显性出来。
Q.E.D.