Hamiltonian.java

import java.util.ArrayList;
import java.util.List;

public class Main {

    //起始點
    static int origin = 0;
    //紀錄已經找到的路徑
    static List<List<Integer>> alreadyFindPath = new ArrayList<>();

    public static void main(String[] args) {

        int graph[][] = {{0, 1, 1, 0, 1},
                {1, 0, 1, 1, 1},
                {1, 1, 0, 1, 0},
                {0, 1, 1, 0, 1},
                {1, 1, 0, 1, 0},
        };

        //存著node是否已走訪過
        boolean[] passNode = new boolean[5];

        //單次中已經經過的路徑
        List<Integer> alreadyPassNode = new ArrayList<>();

        //開始找
        hamiltonian(graph, origin,passNode,alreadyPassNode);

        //純打印
        for(List<Integer> list : alreadyFindPath) {
            for(int i:list) {
                System.out.print(i + "->");
            }
            System.out.println();
        }

    }

    static void hamiltonian(int [][] graph,int nowNode, boolean[] passNode, List<Integer> alreadyPassNode){

        //剩下最後一個node 直接判斷他有無跟原點連接
        if(alreadyPassNode.size() == passNode.length-1){
            
            //若是有 直接把它加到alreadyPassNode裡面
            if(graph[nowNode][origin] == 1) {
                
                //將最後的節點也加到此次路徑中
                alreadyPassNode.add(nowNode);
                //因為已找完且確定跟原點有連接 所以直接把原點加進來,較方便印出來就是走回原點的樣子
                alreadyPassNode.add(origin);
                //將這次找到的path存起來
                alreadyFindPath.add(alreadyPassNode);
                passNode[nowNode] = true;
            }else{
                //清空記錄此次走訪的資料
                alreadyPassNode.clear();
                for(int i = 0;i<passNode.length;i++){
                    passNode[i]=false;
                }
            }
        }

        //走訪表
        for(int j = 0; j < graph[nowNode].length; j++){
            //去判斷有沒有路,且此節點走過了沒有
            if(graph[nowNode][j] == 1 && passNode[j] == false){
                //設為已走過
                passNode[nowNode] = true;
                //加到此次路徑中
                alreadyPassNode.add(nowNode);
                //遞迴再找下一個node
                hamiltonian(graph,j,passNode,alreadyPassNode);
            }

        }

    }
}