四 拓扑排序
考虑一个任务安排的例子，比如有很多任务T1,T2,....
这些任务又是相互关联的，比如Tj完成前必须要求Ti已完成，这样T1,T2....序列关于这样的先决条件构成一个图，其中如果Ti必须要先于Tj完成，那么<Ti,Tj>就是该图中的一条路径，路径长度为1的就是一条边。
拓扑排序就是把这些任务按照完成的先后顺序排列出来。显然，这样的顺序可能不是唯一的，比如Tk，Tl如果没有在一条路径上，那么他们之间的顺序是任意的。
拓扑排序至少有两种解法
1）首先找出入度（连接到改点的边的数目）为零的顶点放入队列，然后依次遍历这些顶点，每次访问到其中的一个顶点时，把该定点关联到的其它顶点的边移去，也就是使得关联顶点的入度减1.如果减1后该定点入度也变为0了，那么把该定点加入队列下次从他开始处理，直到没有入度为0的定点了。
这里要注意，如果给定的图有回路那么，可能不会处理完所有顶点就退出了。
实现如下：
private final void calculateInDegrees(int[] inDegrees)
{
Arrays.fill(inDegrees, 0);
for(int v=0;v<numVertexes;v++)
{
for(Edge e=firstEdge(v);isEdge(e);e=nextEdge(e))
{
inDegrees[toVertex(e)]++;
}
}
}
/**
*
* @param sortedVertexes
*/
public void topologySort(int[] sortedVertexes)
{
//first calculate the inDegrees
int[] inDegrees=new int[numVertexes];
calculateInDegrees(inDegrees);
Arrays.fill(visitTags, false);
_IntQueue queue=new _IntQueue();
for(int v=0;v<numVertexes-1;v++)
{
if(inDegrees[v]==0)queue.add(v);
}
int index=0;
while(!queue.isEmpty())
{
int from=queue.remove();
System.out.println("visit:"+from);
sortedVertexes[index++]=from;
for(Edge e=firstEdge(from);isEdge(e);e=nextEdge(e))
{
if(--inDegrees[toVertex(e)]==0)
{
queue.add(toVertex(e));
}
}
}
if(index<numVertexes)
{
throw new IllegalArgumentException("There is a loop");
}
}
这里一开始计算了各个顶点的入度，计算的时候，每条边需要访问一次。
如果是相邻矩阵的存储方式，计算入度只需要计算每列的非零个数。
一般也可以静态的给出。
2）借助于图的深度优先周游，每次在回退到改顶点的时候把该顶点送入结果数组。
这样得到的数组恰好就是拓扑排序的逆序，因为最底层的节点是最先回退到的。
实现：
/**
*
* @param sortedVertexes
*/
public void topologySort_byDFS(int[] sortedVertexes)
{
Arrays.fill(visitTags, false);
int num=0;
for(int i=0;i<numVertexes;i++)
{
if(!visitTags[i])num=do_topsort(i,sortedVertexes,num);
}
}
private final int do_topsort(int v, int[] sortedVertexes, int num) {
visitTags[v]=true;
for(Edge e=firstEdge(v);isEdge(e);e=nextEdge(e))
{
if(!visitTags[toVertex(e)])num=do_topsort(toVertex(e),sortedVertexes,num);
}
num++;
sortedVertexes[numVertexes-num]=v;
return num;
}
/**
* Given graph :
*
* C1 → C3 ← C2
* ↓ ↓ ↓
* C8 C4 C5
* ↓ ↓ ↓
* C9 → C7 ← C6
*/
public static void testTopologySort()
{
DefaultGraph g=new DefaultGraph(9);
g.setEdge(0, 1, 0);
g.setEdge(2, 1, 0);
g.setEdge(0, 3, 0);
g.setEdge(1, 4, 0);
g.setEdge(2, 5, 0);
g.setEdge(3, 6, 0);
g.setEdge(4, 7, 0);
g.setEdge(5, 8, 0);
g.setEdge(6, 7, 0);
g.setEdge(8, 7, 0);
g.assignLabels(new String[]{"C1","C3","C2","C8","C4","C5","C9","C7","C6"});
int[] sorted=new int[g.vertexesNum()];
// g.topologySort(sorted);
g.topologySort_byDFS(sorted);
System.out.println("Topology Sort Result==============:");
for(int i=0;i<sorted.length;i++)System.out.print(g.getVertexLabel(sorted[i])+",");
System.out.println();
}
五 最短路径问题
最短路径问题分两类，一类是单源最短路径问题，就是从指定顶点出发到其他各点的最短距离，还有一类是
每两个顶点之间的最短距离，当然第二类也可以通过对每个顶点做一次单源最短路径求解，但是还有一种更优雅的方法（Floyd算法），这种方法一般使用相邻矩阵的实现方式，对每个顶点看它是不是能作为其它没两对顶点间的直接中间节点，如果能，那么再看是不是通过它的两两顶点的距离是不是减小了，若果是就更新这两对顶点间的距离，这样通过每次“贪婪的”找出局部最优解来得到全局最优解，可以算是一个动态规划的解法。
首先我们需要一个辅助类来保存距离，以及回溯路径的类：
public static class Dist implements Comparable<Dist>
{
public int preV;
public int curV;
public int distance;
public Dist(int v)
{
this.curV=v;
this.preV=-1;
this.distance=Integer.MAX_VALUE;
}
@Override
public int compareTo(Dist other) {
return distance-other.distance;
}
}
下面给出第二类最短路径的解法（Floyd算法）Java实现：
@Override
public void floyd(Dist[][] dists) {
for(int i=0;i<numVertexes;i++)
{
dists[i]=new Dist[numVertexes];
for(int j=0;j<numVertexes;j++)
{
dists[i][j]=new Dist(-1);//
dists[i][j].preV=-1;
if(i==j)
dists[i][j].distance=0;
else
dists[i][j].distance=Integer.MAX_VALUE;
}
}
for(int v=0;v<numVertexes;v++)
{
for(Edge e=firstEdge(v);isEdge(e);e=nextEdge(e))
{
int to=toVertex(e);
dists[v][to].distance=e.getWeight();
dists[v][to].preV=v;
}
}
for(int v=0;v<numVertexes;v++)
{
for(int i=0;i<numVertexes;i++)
for(int j=0;j<numVertexes;j++)
{
if((dists[i][v].distance!=Integer.MAX_VALUE)&&(dists[v][j].distance!=Integer.MAX_VALUE)&&(dists[i][v].distance+dists[v][j].distance<dists[i][j].distance))
{
dists[i][j].distance=dists[i][v].distance+dists[v][j].distance;
dists[i][j].preV=v;
}
}
}
}
/**
* 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 testFloyd() {
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"});
Dist[][] dists=new Dist[15][15];
g.floyd(dists);
System.out.println("Shortes path from S-T ("+dists[0][14].distance+")is:");
Stack<String> stack=new Stack<String>();
int i=0;
int j=14;
while(j!=i)
{
stack.push(g.getVertexLabel(j));
j=dists[i][j].preV;
}
stack.push(g.getVertexLabel(i));
while(!stack.isEmpty())
{
System.out.print(stack.pop());
if(!stack.isEmpty())System.out.print("->");
}
System.out.println();
}
单源最短路径问题的解法有Dijstra提出，所以也叫Dijstra算法。
它把顶点分为两个集合一个是已求出最短距离的顶点集合V1，另一类是暂未求出的顶点集合V2，而可以证明下一个将求出来（V2中到出发点最短距离值最小）的顶点的最短路径上的顶点除了该顶点不在V1中外其余顶点都在V1中。
如此，先把出发点放入V1中（出发点的最短距离当然也就是0），然后每次选择V2中到出发点距离最短的点加入V1，并把标记改点的最短距离.直到V2中没有顶点为止，详细的形式化证明见：
Dijstra算法证明
这里的实现我们使用最小值堆来每次从V2中挑出最短距离。
先给出最小值堆的实现：
package algorithms;
import java.lang.reflect.Array;
public class MinHeap<E extends Comparable<E>>
{
private E[] values;
int len;
public MinHeap(Class<E> clazz,int num)
{
this.values=(E[])Array.newInstance(clazz,num);
len=0;
}
public final E removeMin()
{
E ret=values[0];
values[0]=values[--len];
shift_down(0);
return ret;
}
//insert to tail
public final void insert(E val)
{
values[len++]=val;
shift_up(len-1);
}
public final void rebuild()
{
int pos=(len-1)/2;
for(int i=pos;i>=0;i--)
{
shift_down(i);
}
}
public final boolean isEmpty()
{
return len==0;
}
/**
* When insert element we need shiftUp
* @param array
* @param pos
*/
private final void shift_up(int pos)
{
E tmp=values[pos];
int index=(pos-1)/2;
while(index>=0)
{
if(tmp.compareTo(values[index])<0)
{
values[pos]=values[index];
pos=index;
if(pos==0)break;
index=(pos-1)/2;
}
else break;
}
values[pos]=tmp;
}
private final void shift_down(int pos)
{
E tmp=values[pos];
int index=pos*2+1;//use left child
while(index<len)//until no child
{
if(index+1<len&&values[index+1].compareTo(values[index])<0)//right child is smaller
{
index+=1;//switch to right child
}
if(tmp.compareTo(values[index])>0)
{
values[pos]=values[index];
pos=index;
index=pos*2+1;
}
else
{
break;
}
}
values[pos]=tmp;
}
}
下面是基于最小值堆的最短路劲算法以及一个测试方法：
public void dijstra(int fromV,Dist[] dists)
{
MinHeap<Dist> heap=new MinHeap<Dist>(Dist.class,numVertexes*2);
for(int v=0;v<numVertexes;v++)
{
dists[v]=new Dist(v);
}
Arrays.fill(visitTags, false);
dists[fromV].distance=0;
dists[fromV].preV=-1;
heap.insert(dists[fromV]);
int num=0;
while(num<numVertexes)
{
Dist dist=heap.removeMin();
if(visitTags[dist.curV])
{
continue;
}
visitTags[dist.curV]=true;
num++;
for(Edge e=firstEdge(dist.curV);isEdge(e);e=nextEdge(e))
{
if(!visitTags[toVertex(e)]&&e.getWeight()+dist.distance<dists[toVertex(e)].distance)
{
dists[toVertex(e)].distance=e.getWeight()+dist.distance;
dists[toVertex(e)].preV=dist.curV;
heap.insert(dists[toVertex(e)]);
}
}
}
}
/**
* 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 testDijstra()
{
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"});
Dist[] dists=new Dist[15];
g.dijstra(0, dists);
System.out.println("Shortes path from S-T ("+dists[14].distance+")is:");
Stack<String> stack=new Stack<String>();
for(int v=dists[14].curV;v!=-1;v=dists[v].preV)
{
stack.push(g.getVertexLabel(v));
}
while(!stack.isEmpty())
{
System.out.print(stack.pop());
if(!stack.isEmpty())System.out.print("->");
}
System.out.println();
}