今天上系统分析与设计课，老师提到了Warshall算法做函数调用关系的Cycle Detection, 想起当年的离散，这一章还真没有什么印象了。翻开陈年旧书看看，就跟看见陌生人一样，基础还是需要在加强一下啦。今天上课提到的几个点，比如死锁，Dijkstra Algorithm，DFS，Unix多级反馈调度，Android卡顿缘由等，自己没能第一时间想出来，就留作以后闲暇时光google的题目吧。现在花了一个小时，用Java把Warshall算法实现了，总觉得用一个小时是不是有点长了。
Warshall算法要义：
邻接矩阵: 表示图关系的矩阵，看看离散数学就懂了
传递闭包：从邻接矩阵的每一个顶点出发，求出的所有顶点的到达情况，该矩阵就是传递闭包。说是闭包是因为它满足自反性、对称性和传递性。
Warshall算法就是从邻接矩阵中求出传递闭包。[more…]
例如:
邻接矩阵为：
[0, 1, 0, 0,
1, 0, 1, 0,
0, 0, 0, 1,
0, 0, 0, 0]
传递闭包为：
[1, 1, 1, 1
1, 1, 1, 1,
0, 0, 0, 1,
0, 0, 0, 0]
算法很简单，直接上一个代码描述：
[java]
public void warshallDetect(int[] matrix) {
closure = matrix;
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (closure[i, k] == 1 && closure[k, j] == 1) {closure[i, j] = 1}
}
}
}
}
[/java]
程序的意思是：
M(0): 初始矩阵，从每一点到另一个点不能有中间节点，即最初的矩阵。M(1): 在M(0)基础上，从每一个顶点出发，让第1个顶点作为中间节点，检测是否有关系。
M(2): 在M(1)基础上，从每一个顶点出发，让第2个顶点作为中间节点，检测是否有关系。
M(k): 在M(k-1)基础上，从每一个顶点出发，让第k个顶点作为中间节点，检测是否有关系。
M(n): 在M(n - 1)基础上，从每一个顶点出发，让第n个顶点作为中间节点，检测是否有关系。
最终生成一个传递闭包，检测哪些顶点有循环调用就显而易见了。