六。 最小支撐樹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，到此，圖論的大概的算法算是復習完了。