实现Kosaraju算法时的有向加权图反转（邻接表方式）问题

问题1：GraphNode的可变默认参数陷阱 #

Python中可变类型作为函数默认参数时，会在函数定义时创建一次，所有实例共享同一个对象。你的GraphNode类中neighbors=[]会导致所有节点的neighbors指向同一个列表，操作时会互相干扰。

修复方式：

class GraphNode:
    def __init__(self, val, neighbors=None) -> None:
        self.val = val
        # 避免可变默认参数问题，使用None作为默认值，内部初始化空列表
        self.neighbors = neighbors if neighbors is not None else []

问题2：反转逻辑中的冗余边去重 #

你代码里的visited_edge_set完全没必要，反转图需要把原图的每条有向边u→v转换成v→u，每条边都要处理一次，去重判断会导致大量反转边被漏掉，直接去掉这部分逻辑即可。

问题3：无需DFS的简化反转实现 #

其实反转邻接表不需要用DFS遍历，直接遍历原图的所有节点和它们的邻居，逐个生成反转边即可，逻辑更直观，也避免DFS可能带来的遗漏：

修改后的invert_graph方法：

def invert_graph(self):
    node_map = {}
    # 先创建所有反转图的节点
    for node in self.nodes:
        if node.val not in node_map:
            node_map[node.val] = GraphNode(node.val)
    # 遍历每条原边，生成反转边
    for node in self.nodes:
        original_node = node_map[node.val]
        for (neigh, weight) in node.neighbors:
            reversed_node = node_map[neigh.val]
            # 原边是node→neigh，反转后是neigh→node，所以给reversed_node的邻居加original_node
            reversed_node.neighbors.append((original_node, weight))
    self.nodes = list(node_map.values())

完整修复后的代码 #

class GraphNode:
    def __init__(self, val, neighbors=None) -> None:
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []

class Graph:
    def __init__(self, nodes=None) -> None:
        # 同样修复Graph的可变默认参数问题
        self.nodes = nodes if nodes is not None else []

    def invert_graph(self):
        node_map = {}
        # 初始化所有反转节点
        for node in self.nodes:
            if node.val not in node_map:
                node_map[node.val] = GraphNode(node.val)
        # 生成反转边
        for node in self.nodes:
            curr_reversed_node = node_map[node.val]
            for (neigh, weight) in node.neighbors:
                neigh_reversed_node = node_map[neigh.val]
                neigh_reversed_node.neighbors.append((curr_reversed_node, weight))
        self.nodes = list(node_map.values())
    
if __name__ == "__main__":
    zero = GraphNode(0)
    one = GraphNode(1)
    two = GraphNode(2)
    three = GraphNode(3)
    four = GraphNode(4)
    five = GraphNode(5)
    six = GraphNode(6)
    zero.neighbors = [(two, 2), (four, 3)]
    one.neighbors = [(three, 1)]
    two.neighbors = [(six, 6)]
    three.neighbors = [(four, 4)]
    four.neighbors = [(one, 1), (six, 4)]
    six.neighbors = [(five, 2)]
    arr = [zero,one,two,three,four,five,six]
    g = Graph(arr)
    g.invert_graph()
    # 打印验证反转结果
    for node in g.nodes:
        print(f"Node {node.val} neighbors: {[(n.val, w) for n, w in node.neighbors]}")

验证结果 #

运行后打印的反转图邻居应为：

• Node 0 neighbors: []
• Node 1 neighbors: [(4, 1)]
• Node 2 neighbors: [(0, 2)]
• Node 3 neighbors: [(1, 1)]
• Node 4 neighbors: [(0, 3), (3, 4)]
• Node 5 neighbors: [(6, 2)]
• Node 6 neighbors: [(2, 6), (4, 4)]

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