newHanilton.java

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

public class Main {

    //起始點
    static int origin = 0;
    static 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是否已走訪過
    static boolean[] passNode = new boolean[5];
    //是否全部節點都走過
    static boolean finshAll = false;

    public static void main(String[] args) {


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

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



    }

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

        //剩下最後一個node 直接判斷他有無跟原點連接
        if(alreadyPassNode.size() == graph.length-1){
            //若是有 直接把它加到alreadyPassNode裡面
            if(graph[nowNode][origin] == 1) {

                //將最後的節點也加到此次路徑中
                alreadyPassNode.add(nowNode);
                for(int i:alreadyPassNode) {
                    System.out.print(i + "->");
                }
                System.out.println();

                finshAll = true;
            }
        }else {

            //走訪表
            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, alreadyPassNode);
                  
                    //設false尋找下一點
                    passNode[j] = false;
                    alreadyPassNode.remove(alreadyPassNode.size() - 1);
                    if (finshAll) {
                        finshAll = false;
                        return;
                    }

                }

            }
        }

    }
}