当每个任务有前后置关系时,需要找到一种满足前后置关系的路线,将任务完成。
如果将每个任务看成一个节点,任务之间的前后置关系表示为有向图时,这种路线顺序叫做为图进行拓扑排序。也叫关键路径分析。
这里的图用邻接矩阵法表示,算法的关键是:
1 找到一个没有后继的顶点
2 在图中删除它,放入结果数组中
3 重复 步骤 1 ,步骤 2 直到图中没有多余的节点。
如果图中出现环装结构,则算法无法进行,因为此时任务之间循环成为前置。
关于邻接矩阵法请参见:Graph 图-邻接表法。
要注意的是:满足前后置关系的路径可能不止一条。这里仅仅得到其中的一条。
关键API:
int noNext():返回没有后继的节点的下标。
remove(int index):删除指定下标的节点,同时在邻接矩阵中删除相对应的行与列。
main:提供简单的测试。
代码如下:
1
class Vertex
{ //图中的节点
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
10
class Topology
{ //用邻接矩阵法表示的图
11
private Vertex[] vertexs;
12
private Object[][] adjMat; //记载是否联通
13
private int length = 0;
14
private static Object CONN = new Object(); //标致是否联通
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; //标志联通
30
}
31
32
void remove(int index)
{ //移除指定的顶点
33
remove(vertexs,index); //在顶点数组中删除指定位置的下标
34
for(Object[] bs: adjMat) remove(bs,index); //邻接矩阵中删除指定的列
35
remove(adjMat,index); //在邻接矩阵中删除指定的行
36
length--;
37
}
38
39
private void remove(Object[] a, int index)
{ //在数组中移除指定的元素,后面的元素补上空位
40
for(int i=index; i<length-1; i++) a[i] = a[i+1];
41
}
42
43
int noNext()
{ //寻找没有后继的节点
44
int result = -1;
45
OUT:
46
for(int i=0; i<length; i++)
{
47
for(int j=0; j<length; j++)
{
48
if(adjMat[i][j] == CONN)continue OUT; //如果有后继则从外循环继续寻找
49
}
50
return i; //如果没有与任何节点相连,则返回该节点下标
51
}
52
return -1; //否则返回-1
53
}
54
55
Object[] topo()
{
56
Object[] result = new Object[length]; //准备结果数组
57
int index;
58
int pos = length;
59
while(length > 0)
{
60
index = noNext(); //找到第一个没有后继的节点
61
assert index != -1 : "图中存在环";
62
result[--pos] = vertexs[index]; //放入结果中
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
}