圖的遍歷

圖的遍歷問題分為四類：

• 遍歷完所有的邊而不能有重複，即所謂「歐拉路徑問題」（又名一筆畫問題）；
• 遍歷完所有的頂點而沒有重複，即所謂「哈密頓路徑問題」。
• 遍歷完所有的邊而可以有重複，即所謂「中國郵遞員問題」；
• 遍歷完所有的頂點而可以重複，即所謂「旅行推銷員問題」。

對於第一和第三類問題已經得到了完滿的解決，而第二和第四類問題則只得到了部分解決。

第一類問題就是研究所謂的歐拉圖的性質，而第二類問題則是研究所謂的哈密頓圖的性質。

算法

圖的遍歷方法有深度優先搜索法和廣度(寬度)優先搜索法。

參閱

• 圖
• 圖論
• 樹的遍歷
• 遍歷性