#include<stdio.h> 

#define V 5 

void printSolution(int path[]); 

/* A utility function to check if the vertex v can be added at 
   index 'pos' in the Hamiltonian Cycle constructed so far (stored 
   in 'path[]') 

用来检测当前顶点个数为pos，走到顶点v是否可以加入当前回路中  
*/
bool isSafe(int v, bool graph[V][V], int path[], int pos) 
{ 
    /* Check if this vertex is an adjacent vertex of the previously 
       added vertex. 
       上一次加入的顶点和这个顶点v是否相连  
     */
    if (graph [ path[pos-1] ][ v ] == 0) 
        return false; 

    /* Check if the vertex has already been included. 
      This step can be optimized by creating an array of size V 
      判断顶点是否已经在回路中，这里可以用一个visited数组来优化。
      */
    for (int i = 0; i < pos; i++) 
        if (path[i] == v) 
            return false; 

    return true; 
} 

/* A recursive utility function to solve hamiltonian cycle problem 

*/
bool hamCycleUtil(bool graph[V][V], int path[], int pos) 
{ 
    /* base case: If all vertices are included in Hamiltonian Cycle 
    顶点数够了
    */
    if (pos == V) 
    { 
        // And if there is an edge from the last included vertex to the 
        // first vertex 
        //看回路第一个顶点和最后一个顶点是否相连，相连则满足条件
        if ( graph[ path[pos-1] ][ path[0] ] == 1 ) 
           return true; 
        else
          return false; 
    } 

    // Try different vertices as a next candidate in Hamiltonian Cycle. 
    // We don't try for 0 as we included 0 as starting point in in hamCycle() 

    //0作为回路初始顶点
    for (int v = 1; v < V; v++) 
    { 
        /* Check if this vertex can be added to Hamiltonian Cycle */

        //判断1到V顶点是否可以加入回路
        if (isSafe(v, graph, path, pos)) 
        { 
            path[pos] = v;  //可以，就加入回路

            /* recur to construct rest of the path */
            if (hamCycleUtil (graph, path, pos+1) == true)  //递归剩下的路径
                return true; 

            /* If adding vertex v doesn't lead to a solution, 
               then remove it 
                如果顶点v加入后不构成回路，则弹出来。   
            */
            path[pos] = -1; 
        } 
    } 

    /* If no vertex can be added to Hamiltonian Cycle constructed so far, 
       then return false */
    return false; 
} 

/* This function solves the Hamiltonian Cycle problem using Backtracking. 
  It mainly uses hamCycleUtil() to solve the problem. It returns false 
  if there is no Hamiltonian Cycle possible, otherwise return true and 
  prints the path. Please note that there may be more than one solutions, 
  this function prints one of the feasible solutions. */

/*回溯法求汉密尔顿回路，如果不存在返回false，如果存在返回true并打印回路，可能有多重方案，只打印一种*/
bool hamCycle(bool graph[V][V]) 
{ 
    int *path = new int[V]; 
    for (int i = 0; i < V; i++) 
        path[i] = -1; //初始化path数组

    /* Let us put vertex 0 as the first vertex in the path. If there is 
       a Hamiltonian Cycle, then the path can be started from any point 
       of the cycle as the graph is undirected */
    path[0] = 0; //加入0号顶点
    if ( hamCycleUtil(graph, path, 1) == false ) 
    { 
        printf("\nSolution does not exist"); 
        return false; 
    } 

    printSolution(path); 
    return true; 
} 

/* A utility function to print solution 
   打印此回路
*/

void printSolution(int path[]) 
{ 
    printf ("Solution Exists:"
            " Following is one Hamiltonian Cycle \n"); 
    for (int i = 0; i < V; i++) 
        printf(" %d ", path[i]); 

    // Let us print the first vertex again to show the complete cycle 
    printf(" %d ", path[0]); 
    printf("\n"); 
} 

// driver program to test above function 
int main() 
{ 
   /* Let us create the following graph 
      (0)--(1)--(2) 
       |   / \   | 
       |  /   \  | 
       | /     \ | 
      (3)-------(4)    */
   bool graph1[V][V] = {{0, 1, 0, 1, 0}, 
                      {1, 0, 1, 1, 1}, 
                      {0, 1, 0, 0, 1}, 
                      {1, 1, 0, 0, 1}, 
                      {0, 1, 1, 1, 0}, 
                     }; 

    // Print the solution 
    hamCycle(graph1); 

   /* Let us create the following graph 
      (0)--(1)--(2) 
       |   / \   | 
       |  /   \  | 
       | /     \ | 
      (3)       (4)    */
    bool graph2[V][V] = {{0, 1, 0, 1, 0}, 
                      {1, 0, 1, 1, 1}, 
                      {0, 1, 0, 0, 1}, 
                      {1, 1, 0, 0, 0}, 
                      {0, 1, 1, 0, 0}, 
                     }; 

    // Print the solution 
    hamCycle(graph2); 

    return 0; 
}