algorithm - フルーリーのアルゴリズムの時間計算量

Question

フルーリーのアルゴリズム (オイラー回路を取得するために使用される) の時間計算量を調べるのを手伝ってくれませんか?

Answer 1

フルーリーのアルゴリズムは、ブリッジ エッジの識別方法を指定するまで完全ではありません。Tarjan は、すべてのブリッジを識別するための線形時間アルゴリズムを提供したため ( http://en.wikipedia.org/wiki/Bridge_(graph_theory)を参照)、削除された各エッジの後に Tarjan のアルゴリズムを再実行する単純な実装は O(E^2 ）。ブリッジのセットを再計算するためのより良い方法はおそらくありますが、より優れた O(E) アルゴリズムもあります。( http://www.algorithmist.com/index.php/Euler_tour#Fleury.27s_algorithmを参照してください。私のサイトではありません:))

Answer 2

ここで： http ：//roticv.rantx.com/book/Eulerianpathandcircuit.pdf とりわけ、それがO（E）、線形エッジカウントであることを読むことができます。