A brute-force algorithm for this problem generates all possible orderings of the n nodes and checks whether each ordering yields a Hamiltonian circuit. That is, if we list all possible combinations without repetition for the prior example, we need to examine 7x6x5x4x3x2x1 = 5040 cases:

A B C D E F G A C D E F G B A D E F G B C A E F G B C D A F G B C D E A G B C D E F ...

There are *n!* (*n* factorial) possible orderings.

Hence the time complexity of the brute-force algorithm is at least ~~O~~(*n!*) in the worst case.

** What kind of problem solving method is this?

CS1104 Main Page

Last Updated 2002/01/02

© L.Heath, 2000, upgraded by J.A.N. Lee on the date above.