test35(四色问题).py

# a = [[0, 1, 1, 1, 0, 0, 0],
#      [1, 0, 0, 1, 1, 0, 0],
#      [1, 0, 0, 1, 0, 1, 0],
#      [1, 1, 1, 0, 1, 1, 1],
#      [0, 1, 0, 1, 0, 0, 1],
#      [0, 0, 1, 1, 0, 0, 1],
#      [0, 0, 0, 1, 1, 1, 0]]
'''声明邻接矩阵，存储节点连接关系'''
a = [[0, 1, 1, 1, 0, 0, 0, 0, 0, 0],
     [1, 0, 1, 0, 1, 0, 0, 0, 0, 0],
     [1, 1, 0, 1, 1, 0, 1, 1, 0, 0],
     [1, 0, 1, 0, 0, 1, 1, 0, 0, 0],
     [0, 1, 1, 0, 0, 0, 0, 1, 0, 0],
     [0, 0, 0, 1, 0, 0, 1, 0, 1, 0],
     [0, 0, 1, 1, 0, 1, 0, 1, 1, 1],
     [0, 0, 1, 0, 1, 0, 1, 0, 0, 1],
     [0, 0, 0, 0, 0, 1, 1, 0, 0, 1],
     [0, 0, 0, 0, 0, 0, 1, 1, 1, 0]]
'''声明元素个数'''
n = len(a)
'''声明方案数量计数变量'''
color_nums = 0
'''声明载频标记'''
color = ['1', '2', '3', '4']
'''声明每个节点载频，初始为-1无意义'''
area = [-1 for i in range(n)]

'''判断某个节点相邻节点是否有相同的载频'''
def isok(k):
    for j in range(n):
        if a[j][k] == 1 and area[k] == area[j]:
            return False
    return True

'''深度优先搜索函数'''
def DFS(v):
    '''将记录数声明为全局变量'''
    global color_nums
    '''如果当前处理的节点编号超过总量则打印当前方案并返回'''
    if v >= n:
        print(area)
        '''增加一个方案数'''
        color_nums = color_nums + 1
        return
    else:
        '''循环4个载频，只要与相邻节点不同则处理下一个节点，否则标记为无意义，并继续循环'''
        for i in color:
            area[v] = i
            if isok(v):
                DFS(v + 1)
            area[v] = -1


DFS(0)
print("有" + str(color_nums) + "种涂色方案")