Python实现有向图Vertex类邻接表出现指针引用错误如何修复

问题描述 #

通过编写Vertex类实现Python有向图结构，每个顶点包含name属性、存储邻接Vertex实例的adjacent邻接列表属性。
异常表现：将node b设为node a的邻接节点时，node b的对象引用会同时出现在节点a的邻接列表、节点b自身的邻接列表中，不符合有向图设计预期。
原始实现代码如下：

class Vertex:

    def __init__(self, name, adjacent=[]):
        self.name = name
        self.adjacent = adjacent

    def add_adjacent(self, vertex):
        
        self.adjacent.append(vertex)
        
        
class Graph:
    # directed graph
    def __init__(self, edge_list):
        vertices = {}
        for o, d in edge_list:
            
            if o not in vertices:
                v = Vertex(o)
                vertices[o] = v
            else:
                v = vertices[o]
                
            if d not in vertices:
                u = Vertex(d)
                vertices[d] = u
            else:
                u = vertices[d]
            

            if u not in v.adjacent:
                print(v.name, ' adds ', u.name)
                v.add_adjacent(u)
            
        self.vertices = vertices
    
    def get_vertex_names(self):
        return list(self.vertices.keys())
    
    def get_adjacent(self, vertex):
        return self.vertices[vertex].adjacent
    


# test Vertex
edges = [
           ['a', 'b'],
           ['a', 'c'],
           ['a', 'd'],
           ['b', 'c'],
           ['c', 'b'],
         ]

g = Graph(edges)

问题根因 #

这是Python非常经典的可变默认参数陷阱：
Python中函数的默认参数仅在函数定义阶段初始化一次，不会在每次调用时重新生成。如果默认参数是列表、字典这类可变对象，所有未显式传入该参数的实例，都会共享同一个对象引用。
代码里Vertex构造方法的adjacent=[]就是问题源头：所有调用Vertex(name)创建的顶点实例，self.adjacent都指向内存里的同一个列表。往任意一个顶点的邻接表追加元素，本质都是修改这个全局共享的列表，自然会出现邻接节点串到其他顶点邻接表里的异常。

修复方法 #

修改Vertex类构造方法，将可变默认参数替换为None，在构造逻辑内为每个实例单独初始化空列表，从根源避免多实例共享同一个邻接表对象。
修复后的Vertex类代码：

class Vertex:
    def __init__(self, name, adjacent=None):
        self.name = name
        self.adjacent = adjacent if adjacent is not None else []

    def add_adjacent(self, vertex):
        self.adjacent.append(vertex)

其余Graph逻辑、测试代码无需改动，修复后各顶点邻接表完全符合有向图预期：

• 顶点a邻接节点：b、c、d
• 顶点b邻接节点：c
• 顶点c邻接节点：b
• 顶点d邻接表为空

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