Hamiltonian Cycle

Definition

Definition

The Hamiltonian Cycle Algorithm aims to find a cycle that visits every vertex in a graph exactly once and returns to the starting vertex. It's a problem of determining whether such a cycle exists in a given graph

Explanation

The algorithm explores all possible permutations of vertices to find a cycle that visits each vertex exactly once and returns to the starting vertex. It typically uses backtracking to efficiently explore the solution space

Guidance

• Start with any vertex as the current vertex
• Explore all unvisited vertices adjacent to the current vertex
• If all vertices are visited and the current vertex has an edge to the start vertex, then a Hamiltonian cycle is found
• Otherwise, mark the current vertex as visited and recursively explore the unvisited adjacent vertices
• Backtrack if no Hamiltonian cycle is found from the current vertex

Tips

• Implement efficient data structures for graph representation and vertex visitation tracking to optimize performance
• Prune unnecessary branches early in the search process to reduce computation time
• Consider heuristic approaches or domain-specific knowledge if applicable to improve search efficiency

Practice

Practice

hamiltonianCycle(graph):
  numVertices = graph.numVertices()
  path = array of size numVertices
  for each vertex in graph:
    path[0] = vertex
    if hamiltonianCycleUtil(graph, path, 1):
      return path
  return "No Hamiltonian cycle found"

hamiltonianCycleUtil(graph, path, pos):
  if pos == graph.numVertices():
    if graph.hasEdge(path[pos-1], path[0]):
      return true
    else:
      return false
  for v in graph.adjacentVertices(path[pos-1]):
    if not isVisited(v, path, pos):
      path[pos] = v
      if hamiltonianCycleUtil(graph, path, pos+1):
        return true
      path[pos] = -1
  return false

isVisited(vertex, path, pos):
  for i from 0 to pos-1:
    if path[i] == vertex:
      return true
  return false

Solution

package main

func hamiltonianCycleUtil(path []int, pos int) bool {
    if pos == numVertices {
        if graph[path[pos-1]][path[0]] == 1 {
            return true
        }
        return false
    }

    for v := 1; v < numVertices; v++ {
        if isSafe(v, path, pos) {
            path[pos] = v
            if hamiltonianCycleUtil(path, pos+1) {
                return true
            }
            path[pos] = -1
        }
    }
    return false
}

func isSafe(v int, path []int, pos int) bool {
    if graph[path[pos-1]][v] == 0 {
        return false
    }
    for i := 0; i < pos; i++ {
        if path[i] == v {
            return false
        }
    }
    return true
}

func hamiltonianCycle() {
    path := make([]int, numVertices)
    for i := range path {
        path[i] = -1
    }
    path[0] = 0
    if !hamiltonianCycleUtil(path, 1) {
        fmt.Println("No Hamiltonian Cycle exists")
        return
    }
    fmt.Println("Hamiltonian Cycle exists: ")
    for _, vertex := range path {
        fmt.Print(vertex, " ")
    }
    fmt.Println(path[0])
}

import java.util.Arrays;

public class HamiltonianCycle {

  static final int V = 6;
  static int[] path;

  static 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;
  }

  static 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)) {
          return true;
        }
        path[pos] = -1;
      }
    }

    return false;
  }

  static int hamCycle(int graph[][]) {
    path = new int[V];
    Arrays.fill(path, -1);

    path[0] = 0;
    if (!hamCycleUtil(graph, path, 1)) {
      System.out.println("No Hamiltonian Cycle exists");
      return 0;
    }

    System.out.println("Hamiltonian Cycle exists: ");
    for (int i = 0; i < V; i++) {
      System.out.print(" " + path[i] + " ");
    }

    System.out.println(" " + path[0] + " ");
    return 1;
  }
}

const V = 6;
let path = [];

function isSafe(v, graph, path, pos) {
  if (graph[path[pos - 1]][v] === 0) {
    return false;
  }

  for (let i = 0; i < pos; i++) {
    if (path[i] === v) {
      return false;
    }
  }

  return true;
}

function hamCycleUtil(graph, path, pos) {
  if (pos === V) {
    if (graph[path[pos - 1]][path[0]] === 1) {
      return true;
    } else {
      return false;
    }
  }

  for (let v = 1; v < V; v++) {
    if (isSafe(v, graph, path, pos)) {
      path[pos] = v;
      if (hamCycleUtil(graph, path, pos + 1)) {
        return true;
      }
      path[pos] = -1;
    }
  }

  return false;
}

function hamCycle(graph) {
  path = new Array(V).fill(-1);

  path[0] = 0;
  if (!hamCycleUtil(graph, path, 1)) {
    console.log("No Hamiltonian Cycle exists");
    return;
  }

  console.log("Hamiltonian Cycle exists: ");
  for (let i = 0; i < V; i++) {
    process.stdout.write(" " + path[i] + " ");
  }

  console.log(" " + path[0] + " ");
}

internal class HamiltonianCycle {
    private val V = 6
    private lateinit var path: IntArray

    private fun isSafe(v: Int, graph: Array<IntArray>, path: IntArray, pos: Int): Boolean {
        if (graph[path[pos - 1]][v] == 0) return false

        for (i in 0 until pos) if (path[i] == v) return false

        return true
    }

    private fun hamCycleUtil(graph: Array<IntArray>, path: IntArray, pos: Int): Boolean {
        if (pos == V) {
            return graph[path[pos - 1]][path[0]] == 1
        }

        for (v in 1 until V) {
            if (isSafe(v, graph, path, pos)) {
                path[pos] = v
                if (hamCycleUtil(graph, path, pos + 1)) return true
                path[pos] = -1
            }
        }

        return false
    }

    fun hamCycle(graph: Array<IntArray>) {
        path = IntArray(V) { -1 }

        path[0] = 0
        if (!hamCycleUtil(graph, path, 1)) {
            println("No Hamiltonian Cycle exists")
            return
        }

        println("Hamiltonian Cycle exists: ")
        for (i in 0 until V) print(" ${path[i]} ")

        println(" ${path[0]} ")
    }
}

V = 6

def isSafe(v, graph, path, pos):
    if graph[path[pos - 1]][v] == 0:
        return False

    for i in range(pos):
        if path[i] == v:
            return False

    return True

def hamCycleUtil(graph, path, pos):
    if pos == V:
        return graph[path[pos - 1]][path[0]] == 1

    for v in range(1, V):
        if isSafe(v, graph, path, pos):
            path[pos] = v
            if hamCycleUtil(graph, path, pos + 1):
                return True
            path[pos] = -1

    return False

def hamCycle(graph):
    path = [-1] * V
    path[0] = 0
    if not hamCycleUtil(graph, path, 1):
        print("No Hamiltonian Cycle exists")
        return

    print("Hamiltonian Cycle exists:")
    for vertex in path:
        print(vertex, end=" ")
    print(path[0])

const V: usize = 6;

fn is_safe(v: usize, graph: &[[i32; V]; V], path: &[i32], pos: usize) -> bool {
    if graph[path[pos - 1] as usize][v] == 0 {
        return false;
    }

    for i in 0..pos {
        if path[i] == v as i32 {
            return false;
        }
    }

    true
}

fn ham_cycle_util(graph: &[[i32; V]; V], path: &mut [i32], pos: usize) -> bool {
    if pos == V {
        return graph[path[pos - 1] as usize][path[0] as usize] == 1;
    }

    for v in 1..V {
        if is_safe(v, graph, path, pos) {
            path[pos] = v as i32;
            if ham_cycle_util(graph, path, pos + 1) {
                return true;
            }
            path[pos] = -1;
        }
    }

    false
}

fn ham_cycle(graph: &[[i32; V]; V]) {
    let mut path = vec![-1; V];
    path[0] = 0;
    if !ham_cycle_util(graph, &mut path, 1) {
        println!("No Hamiltonian Cycle exists");
        return;
    }

    println!("Hamiltonian Cycle exists:");
    for vertex in path {
        print!("{} ", vertex);
    }
    println!("{}", path[0]);
}

const V: number = 6;

function isSafe(
  v: number,
  graph: number[][],
  path: number[],
  pos: number,
): boolean {
  if (graph[path[pos - 1]][v] === 0) return false;

  for (let i = 0; i < pos; i++) if (path[i] === v) return false;

  return true;
}

function hamCycleUtil(graph: number[][], path: number[], pos: number): boolean {
  if (pos === V) {
    return graph[path[pos - 1]][path[0]] === 1;
  }

  for (let v = 1; v < V; v++) {
    if (isSafe(v, graph, path, pos)) {
      path[pos] = v;
      if (hamCycleUtil(graph, path, pos + 1)) return true;
      path[pos] = -1;
    }
  }

  return false;
}

function hamCycle(graph: number[][]): void {
  let path: number[] = Array(V).fill(-1);

  path[0] = 0;
  if (!hamCycleUtil(graph, path, 1)) {
    console.log("No Hamiltonian Cycle exists");
    return;
  }

  console.log("Hamiltonian Cycle exists:");
  for (let i = 0; i < V; i++) process.stdout.write(" " + path[i] + " ");

  console.log(" " + path[0] + " ");
}