圖形的走訪問題分為四類:
- 走訪完所有的邊而不能有重複,即所謂「歐拉路徑問題」(又名一筆畫問題);
- 走訪完所有的頂點而沒有重複,即所謂「哈密頓路徑問題」。
- 走訪完所有的邊而可以有重複,即所謂「中國郵遞員問題」;
- 走訪完所有的頂點而可以重複,即所謂「旅行推銷員問題」。
對於第一和第三類問題已經得到了完整的解決,而第二和第四類問題則只得到了部分解決。
演算法
圖形的走訪方法有深度優先搜尋法和廣度(寬度)優先搜尋法。
參閱
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.