Skip to main content
 首页 » 编程设计

python之在 Python 中返回所有可能的顶点着色组合

2025年01月19日9傻小

我需要编写一个方法 three_color(graph) 将图形作为输入,并返回图形的所有可能的顶点着色,包括那些无效的顶点着色。我们使用字典表示图形,输出应该是字典列表。

three_color({“A” : [“B”], “B” : [“A”]}) should return  
 
{“A” : 1, “B” : 1}, {“A” : 1, “B” : 2}, {“A” : 1, “B” : 3}, {“A” : 2, “B” : 1}, {“A” : 2, “B” : 2}, {“A” : 2, “B” : 3}, {“A” : 3, “B” : 1}, {“A” : 3, “B” : 2}, {“A” : 3, “B” : 3} 

我在想出如何编写此方法的解决方案时遇到问题,因为我们不允许使用除复制之外的任何库来帮助我们。

我是 python 的新手,所以我不确定是否有一个我忽略的简单解决方案。非常感谢您提供帮助或指导。 这就是我一直在尝试使用的:

def three_color(graph): 
    vertices = [] 
    colorings = [] 
    color = {} 
    for key in graph: 
        vertices.append(key) 
    for v in vertices: 
        color[v] = 1 
    colorings.append(copy.copy(color)) 
 
    for v in vertices: 
        for v2 in vertices: 
            for i in range(1,4): 
                for j in range(1,4): 
                    color[v] = i 
                    color[v2] = j 
                    colorings.append(copy.copy(color)) 
 
    #Get rid of duplicates 
    new_c = [] 
    for c in colorings: 
        if c not in new_c: 
            new_c.append(c) 
 
    return new_c 

我知道这是完全错误的,但我无法正确考虑这些 for 循环。

请您参考如下方法:

因为这是一道作业题,所以我给出一个伪代码解法,你可以自己实现,希望能学到更多。

我偏爱递归,所以我将在这个解决方案中使用它。

take a graph as an argument: 
    if the graph is empty, return the graph 
    recursively color all the elements except the first, store the result as "tail" 
    store the first element of the list as "head" 
    for every element of tail, refered to as "element": 
        add "head, color 1" + element to a final results list 
        add "head, color 2" + element to a final results list 
        add "head, color 3" + element to a final results list 
    return final results