CODEWITHSUNDEEP
algorithmgraph-theorytraveling-salesmanhamiltonian-cycle
Hughes
Hughes

Reputation: 1

How to calculate all possible cycles (all nodes must be visited once) on a graph? Hamilton circle

I am trying to write a program which outputs all possible cycles starting and ending with node 1 and visiting all other nodes exactly once.

Given is a complete undirected unweighted graph with N nodes.

For example: n = 4 then 1-2-3-4, 1-2-4-3, 1-3-2-4, 1-3-4-2, 1-4-3-2, 1-4-2-3

My approach would be to use Hamilton-circle method to find out a possible combination and then iterate until all combinations are calculated. I assume the complexity is (n-1)!

class Permutation

  main {
      
    string list1 = "1"
    string list2 = "2,3,4"

    l2 = list2.length()

    init Permutation 
    permutaion.permute (list2, 0, n-1)!

    print list1 + list2
}

  permute(list2, start, end) {

  if (start==end)
     print list2

  else
     for (i=start, i<=end, i++)
        
         list2 = swap(list2, start, i)
         permute(list2, start+1, end)
         list2 = swap(list2, start, i)
}

Thank you for your time and help!

Upvotes: 0

Views: 123

Answers (0)

Related Questions