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)
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.
class HamiltonianCycle
{
final int V = 5;
int path[];
boolean isSafe(int v, int graph[][], int path[], int pos)
{
if (graph[path[pos - 1]][v] == 0)
return false;
for (int i = 0; i < pos; i++)
if (path[i] == v)
return false;
return true;
}
boolean hamCycleUtil(int graph[][], int path[], int pos)
{
if (pos == V)
{
if (graph[path[pos - 1]][path[0]] == 1)
return true;
else
return false;
}
for (int v = 1; v < V; v++)
{
if (isSafe(v, graph, path, pos))
{
path[pos] = v;
if (hamCycleUtil(graph, path, pos + 1) == true)
return true;
path[pos] = -1;
}
}
return false;
}
int hamCycle(int graph[][])
{
path = new int[V];
for (int i = 0; i < V; i++)
path[i] = -1;
path[0] = 0;
if (hamCycleUtil(graph, path, 1) == false)
{
System.out.println("\nSolution does not exist");
return 0;
}
printSolution(path);
return 1;
}
}
bool isSafe(int v, bool graph[V][V], int path[], int pos)
{
if (graph [ path[pos-1] ][ v ] == 0)
return false;
for (int i = 0; i < pos; i++)
if (path[i] == v)
return false;
return true;
}
bool hamCycleUtil(bool graph[V][V], int path[], int pos)
{
if (pos == V)
{
if ( graph[ path[pos-1] ][ path[0] ] == 1 )
return true;
else
return false;
}
for (int v = 1; v < V; v++)
{
if (isSafe(v, graph, path, pos))
{
path[pos] = v;
if (hamCycleUtil (graph, path, pos+1) == true)
return true;
path[pos] = -1;
}
}
return false;
}
bool hamCycle(bool graph[V][V])
{
int *path = new int[V];
for (int i = 0; i < V; i++)
path[i] = -1;
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.java
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/
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.
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;
}
|
Read full article from
Backtracking | Set 6 (Hamiltonian Cycle) | GeeksforGeeks
