概要描述一个算法,判断一个用邻接矩阵表示的连通图是否具有欧拉回路.该算法效率类型如何?

题目

概要描述一个算法,判断一个用邻接矩阵表示的连通图是否具有欧拉回路.该算法效率类型如何?

答案

算法如下：
设邻接矩阵维度为n*n,将邻接矩阵进行标准化转为概率转移矩阵,方法是每一行元素除以行和保证每行和为1（由于连通,每行和一定大于零,所以除法可实现）
首先判断矩阵对角线上是否有>0的元素,如有证明有欧拉回路（自环）,否则进行下一步
第二步将矩阵平方,判断矩阵对角线上是否有>0的元素,如有证明有欧拉回路（两个节点的环）,否则进行下一步
以此类推,直到计算矩阵的n次方,判断对角线上是否有>0的元素,如有证明有欧拉回路,此时仍没有>0的元素证明该连通图没有欧拉回路
这个方法的依据是,如果将邻接矩阵标准化为概率转移矩阵,那么对矩阵进行k次方,得到的矩阵第(i,j)个元素的意义就是通过k步使得从i走到j的概率,那么对角线(i,i)代表的就是从i经k步回到i的概率,这个概率大于零就代表有一条回路.对于一个共有n个节点的有欧拉回路的连通图,最短的欧拉回路结点个数一定小于等于n,所以如果n次方后还没有出现回路概率就可以判断没有回路了
算法效率类型我不太清楚是怎么算的……不过这个算法方面,标准化矩阵的部分运算复杂度不超过n,之后至多进行n步,每一步的矩阵幂大概可以到O(n)复杂度,判断至多也就是O(n),所以这个复杂度不超过O(n^2)的吧