Python类型错误：'Graph'对象不可下标访问——图与BFS实现问题

Hey there! Let's break down why you're hitting this error and how to fix it. That "not subscriptable" message pops up when you try to access your Graph object using bracket notation (like graph['a']) but your custom Graph class doesn't support that kind of access. Here's what's likely going wrong, and how to fix it:

What's Causing the Error? #

Chances are, your Graph class is storing vertices in a list (like self.vertices = []) instead of a dictionary, or you haven't added the necessary logic to let you look up vertices by their ID using brackets. When you try to do something like graph['b'] to grab the vertex with ID 'b', Python has no idea how to handle that for your custom Graph class—hence the error.

Step 1: Fix Your Graph Class #

Let's adjust the Graph class to store vertices in a dictionary (so we can map IDs directly to Vertex objects) and add support for subscript access if you want it. Here's a solid, error-free implementation:

class Vertex:
    def __init__(self, id):
        self.id = id  # e.g., 'a', 'b'
        self.neighbors = []  # List of connected Vertex objects, not just IDs
        self.parent = None  # Tracks the parent vertex during BFS/DFS

class Graph:
    def __init__(self):
        self.vertices = {}  # Key: vertex ID (str), Value: Vertex object

    # Add a vertex to the graph (creates it if it doesn't exist)
    def add_vertex(self, vertex_id):
        if vertex_id not in self.vertices:
            self.vertices[vertex_id] = Vertex(vertex_id)
        return self.vertices[vertex_id]

    # Add an edge between two vertices (creates vertices if needed)
    def add_edge(self, from_id, to_id):
        from_vertex = self.add_vertex(from_id)
        to_vertex = self.add_vertex(to_id)
        from_vertex.neighbors.append(to_vertex)
        # Uncomment the line below if this is an undirected graph
        # to_vertex.neighbors.append(from_vertex)

    # Optional: Let you use graph['a'] instead of graph.vertices['a']
    def __getitem__(self, vertex_id):
        return self.vertices[vertex_id]

Step 2: Adjust Your BFS Code to Match #

Now when you implement BFS, you can safely access vertices by their ID without triggering the error. Here's an example BFS function that works seamlessly with this setup:

def bfs(graph, start_id):
    start_vertex = graph[start_id]  # Uses our __getitem__ method for clean access
    visited = set()
    queue = [start_vertex]
    visited.add(start_vertex.id)

    while queue:
        current_vertex = queue.pop(0)
        print(f"Visited vertex: {current_vertex.id}")

        # Iterate through all connected neighbor vertices
        for neighbor in current_vertex.neighbors:
            if neighbor.id not in visited:
                visited.add(neighbor.id)
                neighbor.parent = current_vertex  # Set parent for path tracking
                queue.append(neighbor)

Common Mistakes to Double-Check #

• Using a list instead of a dictionary for vertices: Lists only accept integer indices, so you can't look up by string IDs like 'a'—a dictionary fixes this.
• Forgetting to implement __getitem__: If you skip this method, you'll need to use graph.vertices['a'] instead of graph['a'] to access vertices.
• Accidentally accessing the Graph directly: Make sure you're not trying to index the Graph object itself (like graph[0]) when you mean to access a vertex inside its storage.

Test this setup with a small sample to confirm it works:

# Create a sample graph
my_graph = Graph()
my_graph.add_edge('a', 'b')
my_graph.add_edge('a', 'c')
my_graph.add_edge('b', 'd')

# Run BFS starting from 'a'
bfs(my_graph, 'a')

This should run without the subscript error and correctly traverse your graph.

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