Python类实现DFS时图初始化键错误问题咨询（保留DFS函数）

我要实现一个DFS算法，返回包含所有节点前驱信息的图，同时通过颜色属性识别图中的环（存在环当且仅当(u,v)是回边，当且仅当v为灰色且v.discovery < u.discovery）。

当前代码的Graph类初始化存在问题：同一个顶点会被创建两次（一次作为字典的键，一次作为邻居节点），导致对象实例不同，进而出现g.vertexes[v]的键错误。希望保持dfs和dfs_visit函数完全不变，仅修改初始化逻辑来解决该问题。

原代码如下：

# A class to represent a vertex object
class Vertex:
    def __init__(self, val, color="white", d_time=-1, f_time=-1, pred=None):
        self.val = val
        self.color = color
        self.d_time = d_time
        self.f_time = f_time
        self.pred = pred

# A class to represent a graph object
class Graph:
    def __init__(self, adjDict):
        self.vertexes = dict()
        for vertex in adjDict:
            self.vertexes[Vertex(vertex)] = [Vertex(neighbor) for neighbor in adjDict[vertex]]#problematic


def dfs(g):
    for vertex in g.vertexes:
        if vertex.color == "white":
            dfs_vist(g, vertex)
    return g


def dfs_vist(g, v, time=0):
    time += 1
    v.d_time = time
    v.color = "gray"
    for neighbor in g.vertexes[v]:
        if neighbor.color == "white":
            neighbor.pred = v
            dfs_vist(g, neighbor, time)
    v.color = "black"
    time += 1
    v.f_time = time

if __name__ == '__main__':
    graph = {
        0: [2, 4],
        1: [],
        2: [1, 5],
        3: [8],
        4: [7],
        5: [4],
        6: [3],
        7: [1],
        8: []
    }
    g = dfs(Graph(graph))
    print(g)

核心思路是先统一创建所有顶点的实例并缓存，确保同一个值的顶点只对应一个Vertex对象，再基于缓存的实例构建邻接关系，这样字典的键和邻居列表里的节点是同一个实例，就能避免键错误。

修改后的代码（dfs和dfs_visit函数完全保留）：

# A class to represent a vertex object
class Vertex:
    def __init__(self, val, color="white", d_time=-1, f_time=-1, pred=None):
        self.val = val
        self.color = color
        self.d_time = d_time
        self.f_time = f_time
        self.pred = pred

# 修改后的Graph类
class Graph:
    def __init__(self, adjDict):
        self.vertexes = dict()
        # 第一步：收集所有节点值，创建唯一的Vertex实例存入字典
        all_node_vals = set()
        for node_val in adjDict:
            all_node_vals.add(node_val)
            all_node_vals.update(adjDict[node_val])
        for val in all_node_vals:
            self.vertexes[Vertex(val)] = []
        
        # 第二步：基于已创建的实例构建邻接关系
        for node_val in adjDict:
            # 找到当前节点对应的Vertex实例
            current_vertex = next(v for v in self.vertexes if v.val == node_val)
            # 找到所有邻居对应的Vertex实例
            neighbor_vertexes = [v for v in self.vertexes if v.val in adjDict[node_val]]
            self.vertexes[current_vertex] = neighbor_vertexes

def dfs(g):
    for vertex in g.vertexes:
        if vertex.color == "white":
            dfs_vist(g, vertex)
    return g


def dfs_vist(g, v, time=0):
    time += 1
    v.d_time = time
    v.color = "gray"
    for neighbor in g.vertexes[v]:
        if neighbor.color == "white":
            neighbor.pred = v
            dfs_vist(g, neighbor, time)
    v.color = "black"
    time += 1
    v.f_time = time

if __name__ == '__main__':
    graph = {
        0: [2, 4],
        1: [],
        2: [1, 5],
        3: [8],
        4: [7],
        5: [4],
        6: [3],
        7: [1],
        8: []
    }
    g = dfs(Graph(graph))
    # 打印节点信息验证结果
    for vertex in g.vertexes:
        print(f"节点{vertex.val}: 颜色={vertex.color}, 发现时间={vertex.d_time}, 完成时间={vertex.f_time}, 前驱={vertex.pred.val if vertex.pred else None}")

1. 先收集所有出现过的节点值（包括邻接字典的键和所有邻居），为每个值创建唯一的Vertex实例，确保同一个节点值对应同一个对象
2. 再遍历原邻接字典，通过节点值匹配到对应的Vertex实例，构建正确的邻接关系
3. 这样g.vertexes[v]中的v就是字典中存在的键，不会再出现键错误，同时完全保留了原dfs和dfs_visit函数的逻辑

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