當(dāng)每個(gè)任務(wù)有前后置關(guān)系時(shí)，需要找到一種滿(mǎn)足前后置關(guān)系的路線(xiàn)，將任務(wù)完成。
如果將每個(gè)任務(wù)看成一個(gè)節(jié)點(diǎn)，任務(wù)之間的前后置關(guān)系表示為有向圖時(shí)，這種路線(xiàn)順序叫做為圖進(jìn)行拓?fù)渑判颉Ｒ步嘘P(guān)鍵路徑分析。
這里的圖用鄰接矩陣法表示，算法的關(guān)鍵是：
1 找到一個(gè)沒(méi)有后繼的頂點(diǎn)
2 在圖中刪除它，放入結(jié)果數(shù)組中
3 重復(fù) 步驟 1 ，步驟 2 直到圖中沒(méi)有多余的節(jié)點(diǎn)。
如果圖中出現(xiàn)環(huán)裝結(jié)構(gòu)，則算法無(wú)法進(jìn)行，因?yàn)榇藭r(shí)任務(wù)之間循環(huán)成為前置。
關(guān)于鄰接矩陣法請(qǐng)參見(jiàn)：Graph 圖－鄰接表法。
要注意的是：滿(mǎn)足前后置關(guān)系的路徑可能不止一條。這里僅僅得到其中的一條。
關(guān)鍵API：
int noNext()：返回沒(méi)有后繼的節(jié)點(diǎn)的下標(biāo)。
remove(int index)：刪除指定下標(biāo)的節(jié)點(diǎn)，同時(shí)在鄰接矩陣中刪除相對(duì)應(yīng)的行與列。
main：提供簡(jiǎn)單的測(cè)試。
代碼如下：
1
class Vertex 
{ //圖中的節(jié)點(diǎn)
2
private Object value;
3
Vertex(Object value) {
4 this.value = value;
5
}
6 Object value() { return value; }
7 @Override public String toString() { return "" + value; }
8
}
9
10class Topology { //用鄰接矩陣法表示的圖
11 private Vertex[] vertexs;
12 private Object[][] adjMat; //記載是否聯(lián)通
13 private int length = 0;
14 private static Object CONN = new Object(); //標(biāo)致是否聯(lián)通
15
16 Topology(int size) {
17 vertexs = new Vertex[size];
18 adjMat = new Object[size][size];
19 }
20
21 void add(Object value) {
22 assert length <= vertexs.length;
23 vertexs[length++] = new Vertex(value);
24 }
25
26 void connect(int from, int to) {
27 assert from < length;
28 assert to < length;
29 adjMat[from][to] = CONN; //標(biāo)志聯(lián)通
30 }
31
32 void remove(int index) { //移除指定的頂點(diǎn)
33 remove(vertexs,index); //在頂點(diǎn)數(shù)組中刪除指定位置的下標(biāo)
34 for(Object[] bs: adjMat) remove(bs,index); //鄰接矩陣中刪除指定的列
35 remove(adjMat,index); //在鄰接矩陣中刪除指定的行
36 length--;
37 }
38
39 private void remove(Object[] a, int index) { //在數(shù)組中移除指定的元素，后面的元素補(bǔ)上空位
40 for(int i=index; i<length-1; i++) a[i] = a[i+1];
41 }
42
43 int noNext() { //尋找沒(méi)有后繼的節(jié)點(diǎn)
44 int result = -1;
45OUT:
46 for(int i=0; i<length; i++) {
47 for(int j=0; j<length; j++) {
48 if(adjMat[i][j] == CONN)continue OUT; //如果有后繼則從外循環(huán)繼續(xù)尋找
49 }
50 return i; //如果沒(méi)有與任何節(jié)點(diǎn)相連，則返回該節(jié)點(diǎn)下標(biāo)
51 }
52 return -1; //否則返回-1
53 }
54
55 Object[] topo() {
56 Object[] result = new Object[length]; //準(zhǔn)備結(jié)果數(shù)組
57 int index;
58 int pos = length;
59 while(length > 0) {
60 index = noNext(); //找到第一個(gè)沒(méi)有后繼的節(jié)點(diǎn)
61 assert index != -1 : "圖中存在環(huán)";
62 result[--pos] = vertexs[index]; //放入結(jié)果中
63 remove(index); //從圖中把它刪除
64 }
65 return result;
66 }
67
68 public static void main(String[] args) {
69 Topology g = new Topology(20);
70 g.add('a');
71 g.add('b');
72 g.add('c');
73 g.add('d');
74 g.add('e');
75 g.add('f');
76 g.add('g');
77 g.add('h');
78
79 g.connect(0,3);
80 g.connect(0,4);
81 g.connect(1,4);
82 g.connect(2,5);
83 g.connect(3,6);
84 g.connect(4,6);
85 g.connect(5,7);
86 g.connect(6,7);
87
88 for(Object o: g.topo()) System.out.print(o + " ");
89 System.out.println();
90 }
91}