The problem of finding a Hamiltonian cycle is to find a cycle that visits every vertex in a graph exactly once and returns to the starting vertex. This problem is NP-complete, meaning no efficient solution is known for all cases.

Program Overview

In this program, we will use a backtracking approach to find a Hamiltonian cycle in a graph represented by an adjacency matrix. The algorithm explores all possible paths, and if it finds a path that forms a Hamiltonian cycle, it returns true.

Go Program Code

// HamiltonianCycle.go - Find a Hamiltonian cycle in a graph

package main

import (
    "fmt"
)

// Function to check if a vertex v can be added to the Hamiltonian cycle
func isSafe(v int, graph [][]int, path []int, pos int) bool {
    // 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.
    for i := 0; i < pos; i++ {
        if path[i] == v {
            return false
        }
    }

    return true
}

// Utility function to solve the Hamiltonian Cycle problem using backtracking
func hamiltonianCycleUtil(graph [][]int, path []int, pos int) bool {
    // Base case: If all vertices are included in the cycle
    if pos == len(graph) {
        // Check if there is an edge from the last vertex to the first vertex
        if graph[path[pos-1]][path[0]] == 1 {
            return true
        }
        return false
    }

    // Try different vertices as the next candidate in the cycle
    for v := 1; v < len(graph); v++ {
        if isSafe(v, graph, path, pos) {
            path[pos] = v

            // Recur to add the next vertex to the path
            if hamiltonianCycleUtil(graph, path, pos+1) {
                return true
            }

            // If adding vertex v doesn't lead to a solution, remove it (backtrack)
            path[pos] = -1
        }
    }

    return false
}

// Function to solve the Hamiltonian Cycle problem and print the cycle
func hamiltonianCycle(graph [][]int) {
    path := make([]int, len(graph))
    for i := range path {
        path[i] = -1
    }

    // Start with the first vertex
    path[0] = 0

    // Start the recursive backtracking function to find the Hamiltonian cycle
    if !hamiltonianCycleUtil(graph, path, 1) {
        fmt.Println("No Hamiltonian cycle found")
    } else {
        fmt.Println("Hamiltonian cycle found:", path)
    }
}

func main() {
    // Example adjacency matrix representation of the graph
    graph := [][]int{
        {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},
    }

    hamiltonianCycle(graph)
}
    

Explanation of the Program Structure

• Graph Representation: The graph is represented using an adjacency matrix, where graph[i][j] equals 1 if there is an edge between vertex i and vertex j, and 0 otherwise.
• isSafe Function: This function checks whether it is safe to add a vertex to the Hamiltonian cycle. It verifies two conditions: whether the vertex is adjacent to the previously added vertex and whether the vertex has already been included in the cycle.
• hamiltonianCycleUtil Function: This function performs the recursive backtracking. It tries to construct the Hamiltonian cycle by exploring all possible vertices. It uses the isSafe function to determine whether a vertex can be added to the cycle.
• hamiltonianCycle Function: This function initializes the path array and calls the recursive utility function. If a Hamiltonian cycle is found, it prints the cycle; otherwise, it prints that no Hamiltonian cycle exists.

Example Output

Hamiltonian cycle found: [0 1 2 4 3]
    

In the example above, the Hamiltonian cycle starts from vertex 0 and visits vertices 1, 2, 4, 3, and returns to vertex 0, forming a valid Hamiltonian cycle.

Conclusion

This Go program provides a backtracking solution to find a Hamiltonian cycle in a graph. The approach works for small graphs but may not be efficient for large graphs due to the exponential number of possible paths.