1       public List
     
       getHamiltonianPath(int v) { 2         // A path starts from v. (i, next[i]) represents an edge in  3         // the path. isVisited[i] tracks whether i is currently in the  4         // path. 5         int[] next = new int[getSize()];        6         for (int i = 0; i < next.length; i++) 7           next[i] = -1; // Indicate no subpath from i is found yet 8          9         boolean[] isVisited = new boolean[getSize()]; 10         11         // The vertices in the Hamiltionian path are stored in result12         List
      
        result = null;13 14         // To speed up search, reorder the adjacency list for each 15         // vertex so that the vertices in the list are in increasing 16         // order of their degrees17         for (int i = 0; i < getSize(); i++)18           reorderNeigborsBasedOnDegree(neighbors.get(i));19         20         if (getHamiltonianPath(v, next, isVisited)) {21           result = new ArrayList
       
        (); // Create a list for path        22           int vertex = v; // Starting from v23           while (vertex != -1) {24             result.add(vertex); // Add vertex to the result list25             vertex = next[vertex]; // Get the next vertex in the path26           }27         }28         29         return result; // return null if no Hamiltionian path is found30       }31 32       /** Reorder the adjacency list in increasing order of degrees */33       private void reorderNeigborsBasedOnDegree(List
        
          list) {34         for (int i = list.size() - 1; i >= 1; i--) {35           // Find the maximum in the list[0..i]36           int currentMaxDegree = getDegree(list.get(0));37           int currentMaxIndex = 0;38 39           for (int j = 1; j <= i; j++) {40             if (currentMaxDegree < getDegree(list.get(j))) { 41               currentMaxDegree = getDegree(list.get(j));42               currentMaxIndex = j;43             }44           }45 46           // Swap list[i] with list[currentMaxIndex] if necessary;47           if (currentMaxIndex != i) {48             int temp = list.get(currentMaxIndex);49             list.set(currentMaxIndex, list.get(i));50             list.set(i, temp);51           }52         }53       }54       55       /** Return true if all elements in array isVisited are true */56       private boolean allVisited(boolean[] isVisited) {57         boolean result = true;58         59         for (int i = 0; i < getSize(); i++) 60           result = result && isVisited[i];61         62         return result;63       }64       65       /** Search for a Hamiltonian path from v */66       private boolean getHamiltonianPath(int v, int[] next,67           boolean[] isVisited) {68         isVisited[v] = true; // Mark vertex v visited69 70         if (allVisited(isVisited)) 71           return true; // The path now includes all vertices, thus found72           73         for (int i = 0; i < neighbors.get(v).size(); i++) {74           int u = neighbors.get(v).get(i);75           if (!isVisited[u] && 76               getHamiltonianPath(u, next, isVisited)) {77             next[v] = u; // Edge (v, u) is in the path78             return true; 79           }80         }81 82         isVisited[v] = false; // Backtrack, v is marked unvisited now83         return false; // No Hamiltonian path exists from vertex v84       }
        
       
      
     

 对于一个给定的网络，确定起点后，如果存在一条路径，最后又回到原出发点,且满足每个顶点只被访问一次的情况下能穿过这个网络，我们就说这个网络存在哈密顿路径。