如何檢測圖是否是哈密爾頓的

Question

我有一個任務的問題，要求實現接口方法isHamiltonian，我試圖通過使用遞歸來解決問題。

的想法是簡單地嘗試所有路徑從一個節點，如果滿足條件，只有一次

的最後一個節點直接連接到第一節點

• 旅行的所有節點的路徑

我會說這是哈密爾頓語。

我嘗試了這些代碼，但它不工作

public static boolean isHamiltonian(Graph g) throws InvalidGraphException { 
    if (g == null || !(g instanceof GraphI) || ((GraphI) g).getDirected()) { 
     throw new InvalidGraphException(); 
    } 

    NodeI[] nodes = (NodeI[]) g.nodes(); 
    if (nodes.length < 3) 
     return false; 

    return isHamiltonian(nodes[0], nodes[0], new HashSet<NodeI>()); 
} 

private static boolean isHamiltonian(NodeI start, NodeI n, HashSet<NodeI> hs) { 
    hs.add(n); 
    NodeI[] nodes = n.getReachableNeighbours(); 
    boolean connectedWithStart = false; 
    for (int i = 0; i < nodes.length; i++) { 
     if (nodes[i].compareTo(start) == 0) { 
      connectedWithStart = true; 
      break; 
     } 
    } 
    if (hs.size() == n.getGraph().nodes().length && connectedWithStart) { 
     return true; 
    } 
    for (int i = 0; i < nodes.length; i++) { 
     if (!hs.contains(nodes[i])) 
      isHamiltonian(start, nodes[i], hs); 
    } 

    return false; 
} 

Answer 1

在我看來，你的回溯問題。你貪婪地向你的hs添加節點來建立你的路徑，但是當你沒有做出一個循環/沒有任何路要走的時候，你不會刪除它們。

我要做的第一件事是在最後的return false之前放hs.remove(n)。然後我還會保存isHamiltonian(start,nodes[i],hs)的結果並在其爲真時退出。像這樣的東西

boolean result = isHamiltonian(start,nodes[i],hs); 
if(result)return true;` 

這應該解決了很多。我認爲這個詳盡的搜索會很慢。

編輯：整個事情應該是這樣的：

private static boolean isHamiltonian(NodeI start, NodeI n, HashSet<NodeI> hs) { 
    hs.add(n); 
    NodeI[] nodes = n.getReachableNeighbours(); 
    boolean connectedWithStart = false; 
    for (int i = 0; i < nodes.length; i++) { 
     if (nodes[i].compareTo(start) == 0) { 
      connectedWithStart = true; 
      break; 
     } 
    } 
    if (hs.size() == n.getGraph().nodes().length && connectedWithStart) { 
     return true; 
    } 
    for (int i = 0; i < nodes.length; i++) { 
     if (!hs.contains(nodes[i])){ 
      boolean result=isHamiltonian(start, nodes[i], hs); 
      if(result)return true; 
     } 
    } 
    hs.remove(n); 
    return false; 
} 

問題本身是NP難的，所以不要指望一般圖形快速的解決方案。請閱讀some basic algorithms並決定是否值得花時間爲您的應用程序實施。