鄰接矩陣演算法

『壹』 概要描述一個演算法，判斷一個用鄰接矩陣表示的連通圖是否具有歐拉迴路。該演算法效率類型如何

演算法如下：
設鄰接矩陣維度為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)的吧