Python 2+Numpy实现二分图检测时的ValueError问题求助

Let's break down why you're hitting that ValueError and fix the code step by step:

Root Cause of the Error #

The error happens because you're using a class-level visited list (shared across all grafo instances) and initializing it with a boolean value. When you pop elements from this list later, you end up getting True instead of a vertex index integer. Using a boolean to index a NumPy array triggers the ambiguous truth value error, since NumPy doesn't know how to interpret a boolean as an index for a multi-element array.

Key Issues in Your Code #

• Shared visited list: Defining visited = [] at the class level means every grafo object uses the same list. Your __init__ method adds True to this list, which contaminates the vertex indices you need for traversal.
• Extra element in color: self.color = [-1] * self.size creates a list matching your vertex count, but self.color.append(0) adds an extra element that's never used, leading to potential index confusion.
• Incorrect visited initialization: Adding True to visited in __init__ serves no purpose—this list should only hold vertex indices during traversal.

Fixed Code #

from __future__ import print_function
import numpy as np

class grafo:
    def __init__(self, n):
        self.vertices = []
        # Explicitly set dtype to int to avoid float conversion issues
        self.adjacency = np.zeros((n, n), dtype=int)
        self.size = n
        # Make visited an instance variable (each graph has its own list)
        self.visited = []
        # Color list matches vertex count exactly
        self.color = [-1] * self.size

    def isBipartita(self):
        # Handle disconnected graphs by checking all uncolored vertices
        for init in range(self.size):
            if self.color[init] == -1:
                self.color[init] = 1
                self.visited.append(init)
                while self.visited:
                    i = self.visited.pop()
                    # Self-loops instantly make a graph non-bipartite
                    if self.adjacency[i][i] == 1:
                        return "NO"
                    for f in range(self.size):
                        if self.adjacency[i][f] == 1:
                            # Color unvisited neighbor with opposite color
                            if self.color[f] == -1:
                                self.color[f] = 1 - self.color[i]
                                self.visited.append(f)
                            # Conflict means non-bipartite
                            elif self.color[f] == self.color[i]:
                                return "NO"
        # No conflicts found
        return "YES"

    def __str__(self):
        return str(self.adjacency)

# PROGRAM
lenV = raw_input("Enter number of vertices: ")
lenV = int(lenV)
inputs = []
for i in range(lenV):
    inputs.append(raw_input("Enter row {} of adjacency matrix: ".format(i+1)))

print("\n-> Inputs:")
print(inputs)

print("\n-> Adjacency matrix:")
G = grafo(lenV)
for x in range(lenV):
    tempList = list(inputs[x])
    for y in range(lenV):
        # Convert input chars to integers for proper array storage
        G.adjacency[x][y] = int(tempList[y])

print(G)
print("\nIs bipartite? ", G.isBipartita())

Additional Improvements #

• Explicit NumPy dtype: Setting dtype=int ensures your adjacency matrix stores integers instead of floats, avoiding any weird equality checks with 1.0 vs 1.
• Disconnected graph support: The original code only checked starting from vertex 0—this fix iterates over all uncolored vertices to cover disconnected components.
• Simplified logic: Cleaned up nested conditionals to make the traversal logic easier to follow.

Testing Your Examples #

• 3x3 matrix (011/101/110): This graph contains a triangle, so it's not bipartite. The fixed code returns NO.
• 4x4 matrix (0101/1010/0101/1010): This is a valid bipartite graph (split into {0,2} and {1,3}), so the code returns YES.

内容的提问来源于stack exchange，提问作者Alan Maldonado