1

这是一个简单的图形着色问题，我使用了预定义的图形。输出为节点“a”和“f”提供了相同的颜色。我如何让它们与众不同？

#initialising colours
colours = ['Green', 'Red', 'Yellow', 'Black', 'White']

#initialising vertices
vertices = ['a', 'b', 'c', 'd', 'e','f']

#dictionary to store neighbours. Adajacent sides are treated as values to the key vertice
neighbours = {}
neighbours['a'] = ['b', 'c','d','e']
neighbours['b'] = ['a', 'f', 'd']
neighbours['c'] = ['a', 'f', 'd']
neighbours['d'] = ['a', 'f', 'b']
neighbours['e'] = ['a', 'c', 'f']
neighbours['f'] = ['b', 'c', 'd', 'e']

存储最终输出的字典

colours_of_vertices = {}

检查相邻顶点是否具有相同颜色的函数

def promising(vertice, colour):
    for neighbour in neighbours.get(vertice): 
        colour_of_neighbour = colours_of_vertices.get(neighbour)
        if colour_of_neighbour == colour:
            return False

    return True

将颜色分配给顶点的函数

def get_colour_for_vertice(vertice):
    for colour in colours:
        if promising(vertice, colour):
            return colour

驱动程序

def main():
    for vertice in vertices:
        colours_of_vertices[vertice] = get_colour_for_vertice(vertice)

    print (colours_of_vertices)


main()
4

0 回答 0