算法如下：
設(shè)鄰接矩陣維度為n*n,將鄰接矩陣進行標準化轉(zhuǎn)為概率轉(zhuǎn)移矩陣,方法是每一行元素除以行和保證每行和為1（由于連通,每行和一定大于零,所以除法可實現(xiàn)）
首先判斷矩陣對角線上是否有>0的元素,如有證明有歐拉回路（自環(huán)）,否則進行下一步
第二步將矩陣平方,判斷矩陣對角線上是否有>0的元素,如有證明有歐拉回路（兩個節(jié)點的環(huán)）,否則進行下一步
以此類推,直到計算矩陣的n次方,判斷對角線上是否有>0的元素,如有證明有歐拉回路,此時仍沒有>0的元素證明該連通圖沒有歐拉回路
這個方法的依據(jù)是,如果將鄰接矩陣標準化為概率轉(zhuǎn)移矩陣,那么對矩陣進行k次方,得到的矩陣第(i,j)個元素的意義就是通過k步使得從i走到j(luò)的概率,那么對角線(i,i)代表的就是從i經(jīng)k步回到i的概率,這個概率大于零就代表有一條回路.對于一個共有n個節(jié)點的有歐拉回路的連通圖,最短的歐拉回路結(jié)點個數(shù)一定小于等于n,所以如果n次方后還沒有出現(xiàn)回路概率就可以判斷沒有回路了
算法效率類型我不太清楚是怎么算的……不過這個算法方面,標準化矩陣的部分運算復(fù)雜度不超過n,之后至多進行n步,每一步的矩陣冪大概可以到O(n)復(fù)雜度,判斷至多也就是O(n),所以這個復(fù)雜度不超過O(n^2)的吧