圖形的走訪

圖形的走訪問題分為四類：

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

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

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

演算法

圖形的走訪方法有深度優先搜尋法和廣度(寬度)優先搜尋法。

參閱

• 圖形
• 圖形學
• 樹的走訪
• 走訪性