Backtracking | Set 6 (Hamiltonian Cycle) | GeeksforGeeks
Related: Eulerian path and circuit
Hamiltonian Path in an undirected graph is a path that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a Hamiltonian Path such that there is an edge (in graph) from the last vertex to the first vertex of the Hamiltonian Path. Determine whether a given graph contains Hamiltonian Cycle or not. If it contains, then print the path.
Create an empty path array and add vertex 0 to it. Add other vertices, starting from the vertex 1. Before adding a vertex, check for whether it is adjacent to the previously added vertex and not already added. If we find such a vertex, we add the vertex as part of the solution. If we do not find a vertex then we return false.
public void solve(int vertex) throws Exception {
/** solution **/
if (graph[vertex][0] == 1 && pathCount == graph.length)
//Solution found
/** all vertices selected but last vertex not linked to 0 **/
if (pathCount == graph.length)
return;
for (int v = 0; v < graph.length; v++) {
/** if connected **/
if (graph[vertex][v] == 1) {
/** add to path **/
path[pathCount++] = v;
/** remove connection **/
graph[vertex][v] = 0;
graph[v][vertex] = 0;
/** if vertex not already selected solve recursively **/
if (!isPresent(v))
solve(v);
/** restore connection **/
graph[vertex][v] = 1;
graph[v][vertex] = 1;
/** remove path **/
path[--pathCount] = -1;
}
}
}
/** function to check if path is already selected **/
public boolean isPresent(int v) {
for (int i = 0; i < pathCount - 1; i++)
if (path[i] == v)
return true;
return false;
}
http://webhome.cs.uvic.ca/~wendym/courses/320/14spring/hamilton/Hamilton.java
Different between Eulerian Path/Cycle(visit every edge)
Eulerian Path is a path in graph that visits every edge exactly once. Eulerian Circuit is an Eulerian Path which starts and ends on the same vertex.
https://reeestart.wordpress.com/2016/06/09/graph-hamilton-cycle/
Read full article from Backtracking | Set 6 (Hamiltonian Cycle) | GeeksforGeeks
Related: Eulerian path and circuit
Hamiltonian Path in an undirected graph is a path that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a Hamiltonian Path such that there is an edge (in graph) from the last vertex to the first vertex of the Hamiltonian Path. Determine whether a given graph contains Hamiltonian Cycle or not. If it contains, then print the path.
For example, a Hamiltonian Cycle in the following graph is {0, 1, 2, 4, 3, 0}. There are more Hamiltonian Cycles in the graph like {0, 3, 4, 2, 1, 0}
(0)--(1)--(2) | / \ | | / \ | | / \ | (3)-------(4)
And the following graph doesn’t contain any Hamiltonian Cycle.
(0)--(1)--(2) | / \ | | / \ | | / \ | (3) (4)
class HamiltonianCycle{ final int V = 5; 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[]') */ boolean isSafe(int v, int graph[][], int path[], int pos) { /* Check if this vertex is an adjacent vertex of the previously added vertex. */ 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 */ for (int i = 0; i < pos; i++) if (path[i] == v) return false; return true; } /* A recursive utility function to solve hamiltonian cycle problem */ boolean hamCycleUtil(int graph[][], 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() for (int v = 1; v < V; v++) { /* Check if this vertex can be added to Hamiltonian Cycle */ 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 */ 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. */ int hamCycle(int graph[][]) { path = new int[V]; for (int i = 0; i < V; i++) path[i] = -1; /* 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; if (hamCycleUtil(graph, path, 1) == false) { System.out.println("\nSolution does not exist"); return 0; } printSolution(path); return 1; }}/* 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[]') */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. */ 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 */ 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() for (int v = 1; v < V; v++) { /* Check if this vertex can be added to Hamiltonian Cycle */ 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 */ path[pos] = -1; } } /* If no vertex can be added to Hamiltonian Cycle constructed so far, then return false */ return false;}bool hamCycle(bool graph[V][V]){ int *path = new int[V]; for (int i = 0; i < V; i++) path[i] = -1; /* 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; if ( hamCycleUtil(graph, path, 1) == false ) { printf("\nSolution does not exist"); return false; } printSolution(path); return true;}//path记录路径，visited记录顶点是否访问过，len记录当前路径的长度
bool hamCycleRecall(int graph[V][V], int path[V], bool visited[V],int len){
if(len == V){ //访问到最后一个顶点
if( graph[ path[V-1] ][0] == 1) //有到0点的边
return true;
else
return false;
}
//遍历其它顶点
for(int v = 1; v<V; v++){
//如果没访问过，并且有边相连
if(!visited[v] && graph[ path[len-1] ][v] ==1){
visited[v] = true;
path[len] = v;
//找到了就直接返回
if( hamCycleRecall(graph, path, visited, len+1) )
return true;
path[len] = -1;
visited[v] = false;
}
}
return false;
}
//查找从第一个顶点0开始，能否找到一条哈密顿回路。
bool hamCycle(int graph[V][V]){
int path[V] = {-1};
bool visited[V] = {0};
path[0] = 1; //第一个顶点标记为访问过
visited[V] = 0;
//第一个顶点已确定，len从1开始
if( hamCycleRecall(graph, path,visited, 1) == false){
printf("\nSolution does not exist");
return false;
}
printSolution(path);
return true;
}
https://github.com/ajitkoti/Algorithms/blob/master/src/com/interview/algorithms/graph/HamiltonianCycle.javapublic void solve(int vertex) throws Exception {
/** solution **/
if (graph[vertex][0] == 1 && pathCount == graph.length)
//Solution found
/** all vertices selected but last vertex not linked to 0 **/
if (pathCount == graph.length)
return;
for (int v = 0; v < graph.length; v++) {
/** if connected **/
if (graph[vertex][v] == 1) {
/** add to path **/
path[pathCount++] = v;
/** remove connection **/
graph[vertex][v] = 0;
graph[v][vertex] = 0;
/** if vertex not already selected solve recursively **/
if (!isPresent(v))
solve(v);
/** restore connection **/
graph[vertex][v] = 1;
graph[v][vertex] = 1;
/** remove path **/
path[--pathCount] = -1;
}
}
}
/** function to check if path is already selected **/
public boolean isPresent(int v) {
for (int i = 0; i < pathCount - 1; i++)
if (path[i] == v)
return true;
return false;
}
http://webhome.cs.uvic.ca/~wendym/courses/320/14spring/hamilton/Hamilton.java
Different between Eulerian Path/Cycle(visit every edge)
Eulerian Path is a path in graph that visits every edge exactly once. Eulerian Circuit is an Eulerian Path which starts and ends on the same vertex.
https://reeestart.wordpress.com/2016/06/09/graph-hamilton-cycle/
Hamilton cycle is a cycle that visits each VERTEX in the graph only once.
Note the difference with Euler Cycle, which is a cycle that visits each EDGE only once. Vertices in an Euler Cycle can be visited multiple times.
[Algorithm]
Unlike Euler Cycle, which has to satisfy some conditions, Hamilton Cycle is a backtracking problem.
Unlike Euler Cycle, which has to satisfy some conditions, Hamilton Cycle is a backtracking problem.
public static List<Integer> hamiltonCycle(Map<Integer, Set<Integer>> graph) { List<Integer> result = new ArrayList<>(); int[] visited = new int[graph.size()]; result.add(0); visited[0] = 1; backtracking(graph, visited, 0, result); result.add(0); return result;}private static boolean backtracking(Map<Integer, Set<Integer>> graph, int[] visited, int v, List<Integer> result) { if (result.size() == graph.size()) { if (graph.get(result.get(result.size() - 1)).contains(result.get(0))) { return true; } return false; } for (int adj : graph.get(v)) { if (visited[adj] == 0) { result.add(adj); visited[adj] = 1; if (backtracking(graph, visited, adj, result)) { return true; } visited[adj] = 0; result.remove(result.size() - 1); } } return false;} |
