原理是临接矩阵的定义以及矩阵乘法定义。对无向图同样成立，如果你认为双向边都是环的话。手机答就不写证明了。只说一点：临接矩阵第i行第j列表示i节点与j节点的可达性。自乘Pij=sum(Aik*Akj)，意义上来说就是i节点通过某个k节点后到达j节点如果可达则是非0，否则为0。所以自乘一次后矩阵若把非零元处理成1的话Pij表示i节点经过一次以内中间节点到达j的可达性。n次方表示经过不超过n-1个中间节点的可达性，二值化后得到的结果必定会有重复，表示一切的可达性。对角线元不为0表示可以通过某些路径最终到达自身，所以是环中元。然而这个方法时间复杂度比较惨，一般没人用，除非本来就是有高速计算矩阵乘的方案（集群、分布、显卡），否则效率上远不如来个DFS遍历标记法。
■网友
一个图中可能含有若干个强连通分支，强连通分支中的点就是环上的点。一个强连通分支的邻接矩阵
的幂
，当
足够大（达到了 【高次邻接矩阵法求有向图环路的原理】
的幂敛指数
）之后具有周期性，周期
是该分支中所有环的长度的最大公约数。当幂的次数为
的整数倍时（即
），对角元上全是1。整个图的邻接矩阵
的幂，当次数足够大时也具有周期性，其周期
是各个强连通分支的周期的最小公倍数。取出现循环后的某个
（此处原算法叙述有问题，应取的是次数为周期倍数的某个幂，而这不一定是周期中的最后一个矩阵），则凡是在环上的点，相应的对角元就是1。该算法对于无向图不成立，因为无向图转化为有向图时是把每条无向边拆成两条有向边的，这两条有向边本身就形成环，而这个环是原无向图中不存在的。另外我怀疑这个算法的实用价值。求环上的点就是求强连通分支，后者有
的Tarjan算法。而要是算矩阵幂，一次矩阵乘法就是
……
■网友
泻药！蟹腰！谢邀！第一次被邀请受宠若惊，然而我只是自己搞搞子图匹配，不是研究图论的，而且我是数学渣，所以题主错爱了。但是为了不被题主打，我还是斗胆强答一次：依照描述，这个算法的输出结果不是该问题的解，也就是说这个算法是错的。如另外两位答主所言，R^n的元素（i,j）代表了第i个顶点和第j个顶点的可达性，这是没错的。此外，只要是联通的有向图，R^n一定会呈现出周期性，这也是没错的。但是第一个周期的起点却是不一定的。理解这一点，需要我们首先明白R^n的周期性是怎么来的：1）对于元素R^n(i, j)=1，如果j是环路顶点，则一定存在m大于n，满足R^n(i, j)=1。周期为经过j的所有环路的长度的最小公倍数。2）如果j不是环路顶点，首先判断，i与j之间是否存在经过环路顶点的路径，如果有则同样存在m大于n，满足R^m(i, j)=1，R^n(i, j)依然呈现出周期性。如果i与j之间不存在路过环路的路径，假设两者最远距离为k，则当n\u0026gt;k时，R^n(i, j)=0。3）综合1,2 可知，如果图上存在不经过环路顶点的路径，令其中最长的路径长度为k，则当n\u0026gt;k时，R^n会呈现出周期性。起始矩阵为R^(n+1)。而此时，各个环路顶点距离自己还有几步是不一定的，如果环路远远大于k，则原算法绝对得不到正确答案。
■网友
这本书这个作者这么写也太简练了。简单的说呢就是现在一个邻接矩阵A。 A*A的结果
中每个N呢 表示 i到j 有没有隔一个点相连。N*A就是有没有隔两个点相连。依次类推。另外无向图不成立。。无相图你就要求双连通而不是单连通。无相图这样求没啥意义。
■网友
邻接矩阵A根据Jordan分解 他的幂 有n个诺当块的幂组成. K次幂表示，从i,到j经历k步骤的联通情况（可以递归证明），如果k步走不通，必然是0. 下面就全是高等代数了，和群论了，诺当块是幂循环的 所以取最小公倍数 我们得到矩阵A的重复周期T\u0026lt;|V|，OK 这说明什么，我们可以穷举啊，只要A^k (步骤k自己到自己）都是0，我们就可以说i到i不可达啊！都去算下 这怎么可以？太低估我们数学家到智慧了. Jordan标准型的计算方法很简单 “迭代递归 解线性方程组LI v｛i+1｝=v｛i｝” 其中LI是A-lambda I.，这是由他的特征空间重数决定的，而重数对应了诺当块的周期. 回到当才的问题，怎么办呢，注意到我们只关心到对角线，一个显然的思路是剪枝，只算对角线及其依赖，但这样并不可行. 我们算 R=（I+A）^T的对角线 其中T是周期，为啥只算一个矩阵呢，因为这个矩阵包含了很多图，请幂级数展开.

来源：(未知)

【】网址：http://www.shadafang.com/c/gx032X51UR020.html

标题：高次邻接矩阵法求有向图环路的原理