前言
在电子电路设计中，我们常常需要将多个组件的针脚连接在一起，要连接n个针脚，我们可以使用n-1根连线。很显然，我们希望所使用的连线最短。
可以将上述布线问题用一个连通无向图 G = {V, E} 来表示，V是针脚的集合，E是针脚之间的可能连接，并且为每条边 {u , v}属于E，我们为其赋权重 w 作为连接针脚u和v的代价。我们希望找到一个无环子集T，既能连接所有的针脚，又有最小代价。
因为T是无环子集，并且连通所有结点，因此T必然是一棵树，我们称这样的树是图的最小生成树。
求解最小生成树有两种方法，Kruskal算法和Prim算法。
本文中使用的图
Kruskal算法
Kruskal算法，在所有连接森林中两棵不同树的边里边，找到权重最小的边加入到森林。
简单地说，Kruskal算法将边排序，根据贪心算法思维，选择最短边。但最小生成树的结果要求是无环的，且每个顶点都需要包括，如何确保这个结果呢？
将图中的每个顶点当成一棵单独的树，如果选择的最短边为{u、v}，森林中这两棵树并未交集，则合并这两棵树到森林中。直到森林中包含所有的结点。
算法导论上的伪码如下：
Kruskal算法中的难点就在于确保无环且包含所有结点，并且是连通图。
将每个结点都看成一棵树，如果选中的边两顶点位于不同的树中，则合并这两棵树加入森林，这就间接使两个顶点相连了。如果两个已经连通的顶点已经被加入森林中，那么就不符合条件而不会被重复加入，因此也会是无环的。
/*
* 将边按权重从小到大排列
* 如果边的两个顶点在不同树中则将这两棵树合并，且加入森林
* 在森林中的顶点则是连通的，已连通的顶点在森林中，也不会重复添加边，达到无环要求
*/
public void kruskal(){
MatrixGraph graph = initUndigraph();
MatrixEdge[] array = getEdges(graph, null);
//为边排序
sort(array, 0, array.length-1);
//构造森林，森林中的元素就是一棵棵树，初始树中只包含一个顶点
ArrayList<HashSet<Vertex>> list = new ArrayList<>();
for (int i = 0; i < graph.mList.size(); i++) {
HashSet<Vertex> set = new HashSet<>();
set.add(graph.mList.get(i));
list.add(set);
}
MatrixEdge edge = null;
for (int i = 0; i < array.length; i++) {
edge = array[i];
Vertex v1 = edge.v1;
Vertex v2 = edge.v2;
int count1 = -1;
int count2 = -1;
for (int j = 0; j < list.size(); j++) {
HashSet<Vertex> set = list.get(j);
//找到顶点在森林中的位置
if (set.contains(v1)) {
count1 = j;
}
if (set.contains(v2)) {
count2 = j;
}
}
if (count1 == -1 || count2 == -1) {
return;
}else {
if (count1 != count2) {
//如果顶点分别在不同的树中，则合并这两棵树并且删除之前的旧树
//因为会合并树，所以已经连通的顶点就会在合并的树中，在同一棵树中
//count1等于count2，所以能保证无环
//最终森林中只有一棵树，且包含全部顶点
HashSet<Vertex> set1 = list.get(count1);
HashSet<Vertex> set2 = list.get(count2);
set1.addAll(set2);
if (count1 < count2) {
list.remove(count1);
list.remove(count2-1);
}else {
list.remove(count2);
list.remove(count1-1);
}
list.add(set1);
System.out.println(edge);
}
}
}
}
值得一提的是，图中两种存储方式，矩阵和链表，Kruskal算法需要对所有边排序，而邻接链表中直观获取所有边比较难，所以需要用邻接矩阵存储图。
Prim算法
Prim算法，从图中任意挑选出一个顶点放入集合list中，在list的所有顶点中选出边最短的一条边，并且将边的另一顶点也加入list中，如此重复到所有顶点都已加入到list中。
算法步骤：
- 输入：一个加权连通图，其中顶点集合为V，边集合为E
- 初始化：Vnew = {x}，其中x为集合V中的任一节点（起始点），Enew = {},为空；
- 重复下列操作，直到Vnew = V：
a： 在集合E中选取权值最小的边<u, v>，其中u为集合Vnew中的元素，而v不在Vnew集合当中，并且v∈V（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；
b： 将v加入集合Vnew中，将<u, v>边加入集合Enew中 - 输出：使用集合Vnew和Enew来描述所得到的最小生成树。
prim算法是比kruskal更简单一点。因为prim算法需要计算以某顶点为起点的最小边，所以使用邻接链表存储图更合适。
/*
* 构造新结点list，先从图中选中任意结点加入
* 不断遍历list中的结点，选择与结点相关的最短边，且将边的另一端加入到list中
* 选择的最短边的另一个结点之前不能在list中
* 最后list与图中顶点表相同则结束整个过程
*/
public void prim(){
Graph graph = initUndigraph();
Vertex start = graph.mList.get(0);
//构建新list
List<Vertex> oldList = graph.mList;
List<Vertex> newList = new ArrayList<Vertex>();
newList.add(start);
Vertex v = null;
Arc vArc = null;
//最短边的权重、对应的弧、对应的弧起点
int vMinW = Integer.MAX_VALUE;
Arc vMinArc = null;
Vertex vMinVertex = null;
while (newList.size() < oldList.size()) {
//查找出新list中最短边
for (int i = 0; i < newList.size(); i++) {
v = newList.get(i);
vArc = v.firstArc;
while (vArc != null) {
if (vMinW > vArc.weight && !newList.contains(vArc.vertex)) {
vMinW = vArc.weight;
vMinArc = vArc;
vMinVertex = v;
}
vArc = vArc.next;
}
}
//输出结果
if (vMinArc != null && vMinArc.vertex != null && !newList.contains(vMinArc.vertex)) {
System.out.println(vMinVertex.info + " " + vMinArc.weight + " " + vMinArc.vertex.info);
newList.add(vMinArc.vertex);
vMinW = Integer.MAX_VALUE;
}
}
}
所有代码均上传至本人的github，欢迎访问。从本文来看，图的不同存储方式也能带来不同的便利。
网友评论