检查随机图形着色是否正确 (Python)

Question

所以我正在尝试一种不同的图形着色方法，我所做的基本上是为图形的节点随机分配颜色，而我想做的是，在分配这些颜色之后，检查颜色是否正确（没有具有相同颜色的相邻节点）换句话说，遍历节点及其各自的颜色并确保没有相邻节点具有相同的颜色。

这是我到目前为止所做的：

def approx_color(graph):
      colors = [1,2,3,4,5,6,7,8,9]
      xr = random.randint(0, len(graph.nodes))
      s_c = []
      for i in range(len(graph.nodes)):
          s_c.append(random.choice(colors))
      colored = dict(zip(graph.nodes,s_c))
      print(colored)

编辑：

"graph"变量是由networkx库生成的图，graph.nodes()graph.edges()是图的节点和边的列表

Answer 1

第一部分可以直接使用random.choices()

def approx_color(graph):
    colors = [1,2,3,4,5,6,7,8,9]
    s_c = random.choices(colors, k=graph.order())
    colored = dict(zip(graph.nodes(), s_c))

如果没有两个相邻顶点的颜色相同，则图形着色是正确的。所以你只需要遍历节点并检查它们的邻居。
所以你可以定义一个函数来检查条件是否有效。

for u in graph.nodes():
    for v in graph.neighbors(u):
        if colored[u] == colored[v]:
            return False
return True

检查随机图形着色是否正确 (Python)

Check if a random graph coloring is correct (Python)

python

graph

approximation

networkx

graph-coloring