图染色局部搜索算法python

graph={'A':['B','D','C','F'], 'B':['A','D','C','G'], 'C':['A','B','E','F','D'], 'D':['A','B','C'], 'E':['C','F','G'], 'F':['C','E','A'], 'G':['B','E','H'], 'H':['G']} def color(graph, start, MAX=99): vlist = [] # 保存当前节点 vlist.append(start) colored = {} # 保存已着色节点 colored[start] = 0 while len(vlist): index = vlist.pop() for node in graph[index]: if node not in colored: print('正在为节点', node, '着色...') adjcs = graph[node] used = [] for adjc in adjcs: if adjc in colored: # not empty used.append(colored[adjc]) # choose an minim id not used by neighbors for i in range(MAX): if i not in used: colored[node] = i print('为该节点着色', i) break vlist.append(node) print(colored) color(graph,'A')