Problem: Determine all Hamiltonian Circuits in a connected, undirected graph.

Inputs: positive integer n and an undirected graph containing n vertices. The graph is represented by a two-dimensional array W, which has both its rows and columns indexed from 1 to n, where W[i] [j] is true if there is an edge between the ith vertex and the jth vertex and false otherwise.

Outputs: For all paths that start at a given vertex, visit each vertex in the graph exactly once, and end up at the starting vertex. The output for each path is an array of indices vindex indexed from 0 to n - 1, where vindex[i] is the index of the ith vertex on the path. The index of the starting vertex is vindex[0].

---------------------------------------


void hamiltonian (index i)
   {
  index j;

  if (promising (i)
         if (i == n - 1)
               cout << vindex [0] through vindex [n - 1];
         else
            for (j = 2; j <=n; j++){             // Try all vertices as
         vindex [i + 1] = j;         // next one.
         hamiltonian (i + 1);
        }
   }
bool promising (index i)
   {
  index j;
  bool switch;

  if (i == n - 1 &&! W[vindex[n - 1]] [vindex [0]])
         switch = false;                                           // First vertex must be adjacent
  else if (i > 0 &&! W[vindex[i - 1]] [vindex [i]])
     switch = false;                                               // to last. ith vertex must
  else{                                                            // be adjacent to (i - 1) st.
     switch = true;
     j = 1;
     while (j < i && switch){                                      // Check if vertex is
         if (vindex[i] == vindex [j])                              // already selected.
                switch = false;
         j++;
        }
     }
  return switch;
   }