检查随机图形颜色是否正确(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