Hamilton Circuit

Java code:

import java.util.LinkedList;
import java.util.List;

public class HamiltonCircuit {
    static boolean[][] graph =
        {{false, true, false, false, true, false, false, false, false, false, false, false},
         {true, false, true, false, false, false, true, true, false, false, false, false},
         {false, true, false, true, false, false, false, true, false, false, false, false},
         {false, false, true, false, false, false, false, false, true, false, false, false},
         {true, false, false, false, false, true, false, false, false, true, false, false},
         {false, false, false, false, true, false, true, false, false, false, true, false},
         {false, true, false, false, false, true, false, true, false, false, false, false},
         {false, true, true, false, false , false, true, false, true, false, false, false},
         {false, false, false, true, false, false, false, true, false, false, false, true},
         {false, false, false, false, true, false, false, false, false, false, true, false},
         {false, false, false, false, false, true, false, false, false, true, false, true},
         {false, false, false, false, false, false, false, false, true, false, true, false}};
    static boolean[] isGone = new boolean[graph.length];
    static List<Integer> path = new LinkedList<Integer>();
    
    public static void main(String[] args) {
        for (int i=0; i<graph.length; i++)
            findCircuit(i);
    }

    private static void findCircuit(int vertex) {
        if (path.size() == graph.length) {
            if (graph[vertex][path.get(0)]) {
                for (int v: path)
                    System.out.print(v + 1 + " ");
                System.out.print((path.get(0) + 1) + "\n\n");
            }
        }
        else {
            isGone[vertex] = true;
            path.add(vertex);
            for (int i=0; i<graph.length; i++) {
                if (graph[vertex][i] && !isGone[i])
                    findCircuit(i);
            }
            isGone[vertex] = false;
            path.remove(path.size() - 1);
        }
    }
}

範例輸入輸出:

---

Hamilton Circuit 是要在圖上找一個點當作起點，接著把圖上所有的點走訪一遍後回到原點。程式的作法是把所有點都當作起點看看，然後想辦法把每個點都先走過一遍，最後再看看終點能不能回到起點。

因為此程式是解決課本第5章的第26題，所以輸入參數已經寫死在程式裡，之所以沒有範例輸入輸出，是因為這題找不到Hamilton Circuit(如果我的程式沒有錯的話)。