hamilton.py

树的算法

#!/usr/bin/env python
# -*- coding: GB2312 -*-
# Last modified:

"""
halmilton question
"""


__revision__ = '0.1'

def isOK(k,x,c):
    for i in range (0,k):
        if x[k]==x[i] or not c[x[k]][x[k-1]]:
            return 0
    return 1

def hamilton(n, x, c):
    for i in range(0,n):
        x[0]=i
        k=1
        while k>0:
            while k<n and x[k]<n and not isOK(k,x,c):
                 x[k]=x[k]+1
            if x[k]<n:
                if k==n-1:
                    if c[x[0]][x[k]]:
                        print "%d,%d,%d,%d,%d" % (x[0],x[1],x[2],x[3],x[4])
                    k=k-1
                    x[k]=x[k]+1
                else:
                    k=k+1
                    x[k]=0
            else:
                k=k-1
                x[k]=x[k]+1


if __name__=="__main__":
    c=[ [0,1,0,1,0],
        [1,0,1,1,1],
        [0,1,0,1,1],
        [1,1,1,0,1],
        [0,1,1,1,0] ]
    x=[0,0,0,0,0]

    n=5
    hamilton(n,x,c)

# zou@ICT-FFC822E11FE:~/Code/algorithm$ python hamilton.py
# 0,1,2,4,3
# 0,1,4,2,3
# 0,3,2,4,1
# 0,3,4,2,1