如何修改图结构代码，将节点/顶点用字母或名称替代数字？

问题根源 #

原代码通常依赖列表作为邻接表存储结构，只能用数字作为索引访问，字符串无法直接作为列表索引，导致传入字母/名称节点时触发报错。解决核心是通过双向键值映射，将字符串节点与内部数字索引绑定，内部用数字处理逻辑，对外保持字符串接口的兼容性。

改造方案 #

核心改动点 #

• 新增两个双向映射字典：node_to_idx（字符串节点→数字索引）、idx_to_node（数字索引→字符串节点）
• 维护计数器next_idx，用于自动分配新的数字索引
• 所有对外暴露的方法（addEdge、DFS等）先完成字符串到数字索引的转换，处理逻辑完成后再转回字符串格式返回

完整改造代码 #

class Graph:
    def __init__(self):
        self.adj = []  # 内部用数字索引维护的邻接表
        self.node_to_idx = {}
        self.idx_to_node = {}
        self.next_idx = 0

    def _get_or_create_idx(self, node):
        """获取节点对应的数字索引，不存在则自动创建新索引"""
        if node not in self.node_to_idx:
            self.node_to_idx[node] = self.next_idx
            self.idx_to_node[self.next_idx] = node
            self.adj.append([])  # 为新索引初始化空邻接列表
            self.next_idx += 1
        return self.node_to_idx[node]

    def addEdge(self, u, v):
        """添加边，支持字符串或数字节点格式"""
        u_idx = self._get_or_create_idx(u)
        v_idx = self._get_or_create_idx(v)
        self.adj[u_idx].append(v_idx)

    def _dfs_helper(self, idx, visited, result):
        """内部DFS辅助函数，仅处理数字索引"""
        visited[idx] = True
        result.append(self.idx_to_node[idx])
        for neighbor_idx in self.adj[idx]:
            if not visited[neighbor_idx]:
                self._dfs_helper(neighbor_idx, visited, result)

    def DFS(self, start_node):
        """对外DFS接口，支持字符串起始节点"""
        if start_node not in self.node_to_idx:
            raise ValueError(f"节点 {start_node} 不存在于图中")
        start_idx = self.node_to_idx[start_node]
        visited = [False] * self.next_idx
        result = []
        self._dfs_helper(start_idx, visited, result)
        return result

# 测试用例
if __name__ == "__main__":
    g = Graph()
    # 添加字符串节点的边
    g.addEdge('A', 'B')
    g.addEdge('A', 'C')
    g.addEdge('B', 'D')
    g.addEdge('C', 'D')
    g.addEdge('D', 'E')

    # 执行DFS遍历
    print("从节点A开始的DFS遍历结果：", g.DFS('A'))
    # 输出示例：从节点A开始的DFS遍历结果： ['A', 'B', 'D', 'E', 'C']

关键细节说明 #

• _get_or_create_idx方法：封装了节点索引的创建与获取逻辑，确保无论是传入字符串还是已存在的数字节点，都能正确完成映射
• 内部辅助方法与对外接口分离：_dfs_helper专注处理数字索引的遍历逻辑，对外的DFS方法负责节点格式转换，返回用户友好的字符串结果
• 兼容原有数字节点使用：如果继续传入数字节点，只要不与字符串映射的索引冲突，也能正常工作（建议统一使用一种节点格式避免混淆）

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