哈密頓圖（Hamiltonian graph），又稱哈密爾頓圖，是圖論中的一個概念。這種圖最早由天文學家哈密頓提出，其定義為：從圖中任意一點出發，路途中經過圖中每一個結點當且僅當一次，最終回到起點，形成一個封閉的環。這種封閉的環被稱為哈密頓回路。一個圖成為哈密頓圖需要滿足兩個條件：首先是封閉的環，即所有結點都被訪問且最終回到起點；其次是連通圖，即圖中的任意兩點可達。哈密頓路徑則是指從圖中的任意一點出發，經過圖中每一個結點一次且僅一次的通路。如果這個通路最終回到起點，它就被稱作哈密頓回路。具有哈密頓回路的圖被稱為哈密頓圖，而具有哈密頓路徑但不具有哈密頓回路的圖則被稱為半哈密頓圖。平凡圖，即只有一個結點的圖，也被認為是哈密頓圖。哈密頓圖的概念在圖論和網絡設計中有著廣泛的應用，例如在電路設計、物流優化等領域。盡管哈密頓圖的概念看似簡單，但實際上尋找一個圖的哈密頓回路是一個NP完全問題，對于大規模的圖，尋找哈密頓回路的算法往往需要耗費大量的計算資源。哈密頓圈算法是用于解決哈密頓回路問題的一種算法。這類算法通常采用遞歸、回溯等方式，通過不斷嘗試和驗證路徑來尋找滿足條件的哈密頓回路。但由于哈密頓回路問題的復雜性，目前還沒有一種能夠高效解決所有情況的算法。盡管如此，科學家們仍在不斷探索更高效的哈密頓圈算法。例如，利用動態規劃、分支定界等方法，可以針對特定類型的圖設計更高效的算法。這些算法在解決特定問題時表現出了良好的性能，但它們往往依賴于問題的具體特征，不能適用于所有情況。