有向圖的拓撲排序
摘要：
拓撲排序是可以用圖模擬的另一種操作方式。
他可用於表示一種情況，即某些專案或事件必須按照某種順序排列發生。
基本思想：
步驟1、找到一個沒有後繼的頂點
步驟2、從圖中刪除這個頂點，在列表的前面插入頂點標記...
拓撲排序是可以用圖模擬的另一種操作方式。
- 他可用於表示一種情況，即某些專案或事件必須按照某種順序排列發生。
基本思想：
- 步驟1、找到一個沒有後繼的頂點
-
步驟2、從圖中刪除這個頂點，在列表的前面插入頂點標記
以下為java原始碼：
/**
* @author hasee
* @TIME 2017年5月4日
* 有向圖的拓補排序
* 步驟1、找到一個沒有後繼的頂點
* 步驟2、從圖中刪除這個頂點，在列表的前面插入頂點標記
*/
public class TopoApp {
//測試
public static void main(String[] args) {
// TODO Auto-generated method stub
Graph02 theGraph = new Graph02();
theGraph.addVertex('A');
theGraph.addVertex('B');
theGraph.addVertex('C');
theGraph.addVertex('D');
theGraph.addVertex('E');
theGraph.addVertex('F');
theGraph.addVertex('G');
theGraph.addVertex('H');
theGraph.addEdge(0, 3);//AD
theGraph.addEdge(0, 4);//AE
theGraph.addEdge(1, 4);//BE
theGraph.addEdge(2, 5);//CF
theGraph.addEdge(3, 6);//DG
theGraph.addEdge(4, 6);//EG
theGraph.addEdge(5, 7);//FH
theGraph.addEdge(6, 7);//GH
theGraph.topo();
}
}
/**
* 有一種拓撲圖是拓撲排序是做不到的，那就是有環的情況，所以需要判斷是否為環
*/
/**
* @author hasee
* @TIME 2017年5月4日
* 儲存頂點資訊的類
*/
class Vertex{
public char label;
public Vertex(char lab){
this.label = lab;
}
}
class Graph02{
private final int MAX_VRERTS = 20;
private Vertx vertxList[];//包含所有的節點資訊
private int adjMat[][];//鄰接矩陣
private int nVert;//當前vertxList的指向下標
private char sortedArray[];//儲存
//初始化
public Graph02(){
vertxList = new Vertx[MAX_VRERTS];
adjMat = new int[MAX_VRERTS][MAX_VRERTS];
nVert = 0;
for(int j=0;j<MAX_VRERTS;j++)
for(int k = 0;k<MAX_VRERTS;k++)
adjMat[j][k] = 0;
sortedArray = new char[MAX_VRERTS];
}
/**
* @param lab
*/
public void addVertex(char lab){
vertxList[nVert++] = new Vertx(lab);
}
/**
* @param start
* @param end
* 鄰接矩陣，和之前的無向圖區分，單向
*/
public void addEdge(int start,int end){
adjMat[start][end] = 1;
}
/**
* @param v
* 展示節點數值
*/
public void display(int v){
System.out.println(vertxList[v].lable);
}
/**
* 主要工作是在whil迴圈中完成的
* 1、呼叫noSuccessor找到任意一個沒有後繼的頂點
* 2、如果找到這樣一個頂點把它放到陣列sortedArray中，並且從圖中刪除
* 3、如果沒有這樣的頂點則，則此圖必然存在環
* */
public void topo(){
int orig_nVerts=nVert;//記住有多多少中下標
while(nVert>0){
int currentVerts = noSuccessor();//找到一個後繼頂點下標
if(currentVerts== -1){
System.out.println("圖中存在環！！");
return;
}
//從後往前儲存要刪除的頂點
sortedArray[nVert-1] = vertxList[currentVerts].lable;
deleteVertx(currentVerts);//在圖中刪除這個頂點
}
//如果沒有環就輸出所有的有向圖頂點
for(int i=0;i<orig_nVerts;i++)
System.out.print(sortedArray[i]+" ");
}
/**
* @return
* noSuccessor方法使用鄰接矩陣找到沒有後繼的的頂點，在外層迴圈中，沿著每一行考察每個頂點
* 在每一行中，用內層迴圈掃描值為1的列，如果找一個就說明頂點後面有後繼，然後跳出內層迴圈考察下一個頂點
* 只有一整行都沒有找到，則說明這個頂點沒有後繼，並返回它的行號。如果沒有這樣的頂點就返回-1說明這是個環
*/
public int noSuccessor(){
boolean isEdge;
for(int row = 0;row<nVert;row++){
isEdge =false;
for(int col =0;col<nVert;col++){
if(adjMat[row][col]>0){
isEdge = true;
break;
}
if(!isEdge)
return row;
}
}
return -1;
}
/**
* @param delVert
* 刪除一個頂點很簡單，頂點從vertxList陣列中刪除，後面的頂點向前移動填補空位。同樣的，頂點的行列從鄰接矩陣中刪除
* 下面的行和右面的列移動來填補空位。這些操作有deleteVertx 、moveRow、moveColLeft來完成
*/
public void deleteVertx(int delVert){
if(delVert != nVert -1){//如果不是最後的頂點
//從陣列中刪除,後面的頂點向前移
for(int j=delVert;j<nVert-1;j++)
vertxList[j] = vertxList[j+1];
for(int row =delVert; row<nVert-1;row++)
moveRowUp(row,nVert);
for(int col=delVert;col<nVert-1;col++)
moveColLeft(col,nVert-1);
}
nVert--;//陣列下標減一
}
/**
* @param row
* @param length
* 將後面的行向上移一位
*/
private void moveRowUp(int row,int length){
for(int col=0;col<length;col++)
adjMat[row][col] = adjMat[row+1][col];
}
/**
* @param col
* @param length
* 將後面的列向左移一位
*/
private void moveColLeft(int col,int length){
for(int row = 0;row<length;row++)
adjMat[row][col] = adjMat[row][col+1];
}
}
測試結果：
H G F E D C B A