六。 最小支撑树MST
给定一个简单有向图，要求权值最小的生成树，即求最小支撑树问题。
所谓生成树，就是说树的顶点集合等于给定图的顶点集合，且边集合包含于图的边集合。
也就说找出构成树的，经过所有顶点的，且权值最小的边集。
树的定义是要求无回路的，然后是要求连通的。
有两个比较经典的算法是：
1）Prim算法： 该算法的思想跟Dijstra算法非常相似，Dijstra算法中每次求出下一个顶点时依据的是离初始顶点最近的，而Prim算法则找离V1整个集合最近的，也就是从V1中某个节点出发到该顶点的边的权值最小。
其原理也是每次找局部最优，最后构成全局最优。
实现如下
@Override
public Edge[] prim() {
MinHeap<Edge> heap=new MinHeap<Edge>(Edge.class,numEdges);
Edge[] edges=new Edge[numVertexes-1];
//we start from 0
int num=0;//record already how many edges;
int startV=0;
Arrays.fill(visitTags, false);
Edge e;
for(e=firstEdge(startV);isEdge(e);e=nextEdge(e))
{
heap.insert(e);
}
visitTags[startV]=true;
while(num<numVertexes-1&&!heap.isEmpty())//tree's edge number was n-1
{
e=heap.removeMin();
startV=toVertex(e);
if(visitTags[startV])
{
continue;
}
visitTags[startV]=true;
edges[num++]=e;
for(e=firstEdge(startV);isEdge(e);e=nextEdge(e))
{
if(!visitTags[toVertex(e)])//can't add already visit vertex, this may cause cycle
heap.insert(e);
}
}
if(num<numVertexes-1)
{
throw new IllegalArgumentException("not connected graph");
}
return edges;
}
/**
* A Graph example
* we mark the vertexes with 0,1,2,
.14 from left to right , up to down
* S-8-B-4-A-2-C-7-D
* | | | | |
* 3 3 1 2 5
* | | | | |
* E-2-F-6-G-7-H-2-I
* | | | | |
* 6 1 1 1 2
* | | | | |
* J-5-K-1-L-3-M-3-T
*
*/
public static void testPrimMST() {
DefaultGraph g=new DefaultGraph(15);
g.setEdge(0, 1, 8);
g.setEdge(1, 0, 8);//its a undirected graph
g.setEdge(1, 2, 4);
g.setEdge(2, 1, 4);
g.setEdge(2, 3, 2);
g.setEdge(3, 2, 2);
g.setEdge(3, 4, 7);
g.setEdge(4, 3, 7);
g.setEdge(0, 5, 3);
g.setEdge(5, 0, 3);
g.setEdge(1, 6, 3);
g.setEdge(6, 1, 3);
g.setEdge(2, 7, 1);
g.setEdge(7, 2, 1);
g.setEdge(3, 8, 2);
g.setEdge(8, 3, 2);
g.setEdge(4, 9, 5);
g.setEdge(9, 4, 5);
g.setEdge(5, 6, 2);
g.setEdge(6, 5, 2);
g.setEdge(6, 7, 6);
g.setEdge(7, 6, 6);
g.setEdge(7, 8, 7);
g.setEdge(8, 7, 7);
g.setEdge(8, 9, 2);
g.setEdge(9, 8, 2);
g.setEdge(10, 5, 6);
g.setEdge(5, 10, 6);
g.setEdge(11, 6, 1);
g.setEdge(6, 11, 1);
g.setEdge(12, 7, 1);
g.setEdge(7, 12, 1);
g.setEdge(13, 8, 1);
g.setEdge(8, 13, 1);
g.setEdge(14, 9, 2);
g.setEdge(9, 14, 2);
g.setEdge(10, 11, 5);
g.setEdge(11, 10, 5);
g.setEdge(11, 12, 1);
g.setEdge(12, 11, 1);
g.setEdge(12, 13, 3);
g.setEdge(13, 12, 3);
g.setEdge(13, 14, 3);
g.setEdge(14, 13, 3);
g.assignLabels(new String[]{"S","B","A","C","D","E","F","G","H","I","J","K","L","M","T"});
Edge[] edges=g.prim();
int total=0;
for(int i=0;i<edges.length;i++)
{
System.out.println(edges[i].toString(g));
total+=edges[i].getWeight();
}
System.out.println("MST total cost:"+total);
}
2)Kruskal算法：
该算法开始把，每个节点看成一个独立的两两不同的等价类，每次去权值最小的边，如果关联这条边的两个顶点在同一个等价类里那么这条边不能放入MST（最小生成树）中，否则放入MST中，并把这两个等价类合并成一个等价类。
继续从剩余边集里选最小的边，直到最后剩余一个等价类了。
该算法涉及等价类的合并/查找,一般用父指针树来实现。下面先给出父指针树实现的并查算法。
带路径压缩的算法，其查找时间代价可以看做是常数的。
package algorithms;
/**
* @author yovn
*
*/
public class ParentTree {
private static class PTreeNode
{
int parentIndex=-1;
int numChildren=0;//only make sense in root
void setParent(int i) {
parentIndex=i;
}
}
PTreeNode[] nodes;
int numPartions;
public ParentTree(int numNodes)
{
nodes=new PTreeNode[numNodes];
numPartions=numNodes;
for(int i=0;i<numNodes;i++)
{
nodes[i]=new PTreeNode();
nodes[i].parentIndex=-1;//means root
}
}
/**
* use path compress
* @param i
* @return
*/
public int find(int i)
{
if(nodes[i].parentIndex==-1)
{
return i;
}
else
{
nodes[i].setParent(find(nodes[i].parentIndex));//compress the path
return nodes[i].parentIndex;
}
}
public int numPartions()
{
return numPartions;
}
public boolean union(int i,int j)
{
int pi=find(i);
int pj=find(j);
if(pi!=pj)
{
if(nodes[pi].numChildren>nodes[pj].numChildren)
{
nodes[pj].setParent(pi);
nodes[pj].numChildren+=nodes[pi].numChildren;
nodes[pi].numChildren=0;
}
else
{
nodes[pi].setParent(pj);
nodes[pi].numChildren+=nodes[pj].numChildren;
nodes[pj].numChildren=0;
}
numPartions--;
return true;
}
return false;
}
}
从边集里权最小的边，我们又可以借助最小值堆来完成。有了父指针树以及最小值堆，现实Kruskal算法就很简单了：
@Override
public Edge[] kruskal() {
Edge[] edges=new Edge[numVertexes-1];
ParentTree ptree=new ParentTree(numVertexes);
MinHeap<Edge> heap=new MinHeap<Edge>(Edge.class,numEdges);
for(int i=0;i<numVertexes;i++)
{
for(Edge e=firstEdge(i);isEdge(e);e=nextEdge(e))
{
heap.insert(e);
}
}
int index=0;
while(ptree.numPartions()>1)
{
Edge e=heap.removeMin();
if(ptree.union(fromVertex(e),toVertex(e)))
{
edges[index++]=e;
}
}
if(index<numVertexes-1)
{
throw new IllegalArgumentException("Not a connected graph");
}
return edges;
}
OK，到此，图论的大概的算法算是复习完了。