NumPy矩阵节点着色报错求助：ValueError歧义真值问题

核心错误原因 #

报错ValueError: The truth value of an array with more than one element is ambiguous. Use a.any() or a.all()的直接原因是：

• 你当前的graph是numpy矩阵类型，graph[i][j]返回的是单元素numpy数组而非标量值，直接用它参与布尔判断（and逻辑）会触发numpy的歧义判断错误。
• 除此之外，代码还存在两个致命逻辑问题：
  1. 从文件读取后生成的new_mat是边的列表（每行是一条边的两个节点），不是图的邻接矩阵，导致后续着色逻辑完全错误。
  2. 代码中硬编码了100作为节点数，但输入文件DSJC125.9.col的实际节点数是125，硬编码会导致节点覆盖不全或越界。

分步修复方案 #

1. 修复邻接矩阵生成逻辑 #

修改get_instances函数，生成正确的无向图邻接矩阵：

import re
import numpy as np

def get_instances(chemin):
    nb_noeud = 0
    nb_arret = 0
    edges = []
    with open(chemin, "r") as f:
        for line in f:
            line = line.strip()
            if not line:
                continue
            # 提取节点数和边数
            if line.startswith('p'):
                parts = line.split()
                nb_noeud = int(parts[2])
                nb_arret = int(parts[3])
            # 提取边信息并转换为0索引
            elif line.startswith('e'):
                parts = re.findall(r'\b\d+\b', line)
                u = int(parts[0]) - 1
                v = int(parts[1]) - 1
                edges.append((u, v))
    
    # 初始化邻接矩阵（0=无边，1=有边）
    adj_matrix = np.zeros((nb_noeud, nb_noeud), dtype=int)
    for u, v in edges:
        adj_matrix[u][v] = 1
        adj_matrix[v][u] = 1  # 无向图双向赋值
    return nb_arret, nb_noeud, adj_matrix

# 读取文件生成邻接矩阵
nb_arret, nb_noeud, graph = get_instances('/content/DSJC125.9.col.txt')

2. 修复isSafe函数的布尔判断问题 #

将数组提取为标量，并优化循环逻辑（仅检查当前节点的邻接节点）：

def isSafe(graph, color, v):
    # 检查当前节点v的所有邻接节点是否同色
    for i in range(len(graph)):
        if graph[v][i] == 1 and color[i] == color[v]:
            return False
    return True

3. 移除硬编码的节点数 #

将所有100替换为实际节点数nb_noeud，修改着色核心函数：

def graphColoring(graph, m, v, color):
    # 所有节点完成着色则输出结果
    if v == nb_noeud:
        printSolution(color)
        return True
    
    # 尝试为当前节点分配每种颜色
    for c in range(1, m + 1):
        if isSafe(graph, color, v):
            color[v] = c
            # 递归处理下一个节点
            if graphColoring(graph, m, v + 1, color):
                return True
            # 回溯：撤销当前颜色分配
            color[v] = 0
    return False

def printSolution(color):
    print("Solution Exists: Following are the assigned colors")
    for i in range(nb_noeud):
        print(f"Node {i+1}: Color {color[i]}", end=" | ")
    print()

4. 修正驱动代码 #

if __name__ == '__main__':
    m = 10  # 稠密图DSJC125.9的色数远小于100，先尝试较小值
    color = [0] * nb_noeud
    
    if not graphColoring(graph, m, 0, color):
        print(f"Solution does not exist with {m} colors")

关键说明 #

• 节点索引转换：原始文件节点从1开始编号，转为0索引更符合Python数组操作习惯，避免索引越界。
• 算法效率优化：原isSafe遍历所有节点对的效率极低，修改后仅检查当前节点的邻接节点，性能大幅提升。
• 颜色数选择：DSJC125.9是稠密图，实际色数约为12，无需设置100这么大的值。

内容的提问来源于stack exchange，提问作者Neima Mohamed