四 拓撲排序
考慮一個任務安排的例子，比如有很多任務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();
}