福樓里算法

介紹

福樓里算法(Fleury algorithm)在圖上求歐拉環遊的一種方法.中國郵遞員問題實際上是在具有非負權的連通網路G中找出一條最小權的通過所有邊的閉途徑.當G是歐拉圖時，問題轉化為在G中確定一條歐拉環遊(參見“歐拉跡”).福樓里算法的基本原則是:每到一點，沿該點的關聯邊中未走過的一條走，只有當沒有其他選擇時，才選未走過邊所導出的子圖中的割邊。

步驟

1.任意選取一個頂點vo，置Zero = vo.

2.假設跡.}.;=voelv}...e}v;已經選定，那么按下述方法從E}{eeZ, "..。一1，。}中選取邊。+，:

1) e,+,和。，相關聯.

2)除非沒有別的邊可選擇，否則。+,不是G=G-{eeZ,w}e;}的割邊.

3.當步驟2不能再執行時，算法終止.