[Algorithm]Power of Adjacent Matrix in Graph

图的邻接矩阵表示法大家应该都很熟，给定图G(边无权重)，其邻接矩阵m[u][v]表示是否存在从顶点u到达v的边。比如给定图如下：

其邻接矩阵m为：

我们有一个很有意思的结论：

• m的k次方，m^k[u][v]代表从u到v长度为k的路径的条数

还是拿图G举例，显然长度为2的路径只有1到3，m^2为：

长度为3的路径不存在，m^3为：

那么为什么这个结论成立呢？我们可以用数学归纳法证明，假设邻接矩阵m的长宽均为n，对于m^k：

1. 当k = 1的时候，显而易见结论是成立的
2. 假设当k = i的时候，结论成立，也就是说m^i[u][v]代表从u到v长度为i的路径的数目
3. m^(i + 1) = m ^ k * m, m^(i + 1)[u][v] = m^i[u][0] * m[0][v] + m^i[u][1] * m[1][v] + ... + m^i[n][0] * m[n][v]。这其实就是我们DP的递推表达式，也就是说我们枚举所有的中间节点c，算出所有从u到c长度为i的路径 * c到v长度为1的路径，答案就是从u到v长度为i + 1的路径的数量。所以对k = i + 1的时候也成立。证明完毕。

这个结论其实有很多的用处。比如我们要求一个有向图的传递闭包，我们定义一个有向图G<V, E>，V = {1, 2, 3..., n}}的传递闭包T为，对于任意在V里面的u和v，如果在G中存在一条从u到v的路径，则T[i][j] = 1，否则T[i][j] = 0。那么在一个顶点数为n的图当中，如果存在从u到v的路径，那么其最短路径一定小于等于n - 1。

这个结论其实很好理解，最坏的情况是从u开始经过所有其他的节点到v，所以长度为n - 1。假设u到v存在路径且最短路径大于n - 1，那么从u到v经过的节点一定有重复的，那么代表我们至少经过了一个环，我们把环去掉可以得到一条更短的路径，所以和假设矛盾。

所以我们只需要求m^1 + m ^ 2 + m^3 + ... + m^n - 1，我们可以求得所有从u到v长度小于等于n - 1的路径的数目。如果m[u][v] = 0, T[u][v] = 0, 代表不存在从u到v的路径; 否则T[u][v] = 1。

我们用图G'举例：

其邻接矩阵m为：

m^1 + m ^ 2 + m^3 + m^4 + m^5为：

 从而我们可以求得传递闭包T：

一般在求m的k次方的时候我们都可以采用矩阵快速幂的算法，这样时间复杂度只需要O(m^3 * log k)，关于矩阵快速幂的讨论可以参考这篇文章。

这个结论还有其他很多用途，比如对于一个图，我们想求所有节点数为3的环的话，我们可以对邻接矩阵M求3次方，对角线M^3[i][i]表示的就是所有从i回到i长度为3的路径，也就是i所在的有三个节点的环。注意我们要对对角线的和除以6，因为同一个环会被算6次，假设1,2,3为环上的三个点：

• 1->2->3, 1->3->2 会在M^3[1][1]被算两次
• 2->1->3, 2->3->1 会在M^3[2][2]被算两次
• 3->2->1, 3->1->2 会在M^3[3][3]被算两次

所以总共为6次。所以答案为sum(M^3[i][i]) / 6，where 0 <= i < n，n为节点的总数。