Python存储地铁/公交站点的数据结构选型及ego graph构建咨询

各方案适配性分析 #

• 纯链表直接排除：你的场景本质是无向图存储，不是线性序列结构。纯链表仅支持单/双向的线性邻接关系，无法灵活存储换乘站对应多条线路的多个邻接节点，后续新增站点属性、线路属性的扩展成本极高，完全不匹配需求。
• 纯字典仅适合临时原型：如果仅做最简可达性查询，用{站点ID: [邻接站点ID列表]}的字典结构可以快速跑通逻辑，但可扩展性极差：后续需要新增站点属性（站点名称、无障碍设施、首末班时间）、边属性（站间行驶时间、所属线路）时，字典结构会变得非常臃肿，多层嵌套的结构会大幅降低代码可读性和可维护性。
• 自定义类是最优选择：完全匹配你对扩展性的要求，同时满足当前的可达性查询需求：
  • 结构灵活：可自定义Station类存储站点的所有属性，邻接节点用集合存储（无需顺序，天然支持去重），换乘站直接添加多条线路的邻接站点即可，无需额外适配。
  • 扩展成本极低：后续需要新增任意站点、线路、站间关联属性时，直接给类新增属性即可，不需要改动核心的存储逻辑，比如后续要算最短路径时，仅需要把邻接集合改成Dict[Station, EdgeInfo]，EdgeInfo自定义类存储站间耗时、所属线路等信息即可。
  • 可达性查询实现简单：基于类实例直接做BFS/DFS遍历即可，不需要额外做ID映射跳转，代码可读性更高。

最简实现示例（Python） #

class Station:
    def __init__(self, station_id: int, name: str):
        self.station_id = station_id
        self.name = name
        # 无向图邻接集合，自动去重
        self.neighbors: set["Station"] = set()
    
    def add_neighbor(self, neighbor: "Station") -> None:
        # 双向添加邻接关系，无需重复调用
        self.neighbors.add(neighbor)
        neighbor.neighbors.add(self)

# 可达性查询BFS实现
def get_reachable_stations(start_station: Station) -> set[Station]:
    visited = set()
    queue = [start_station]
    visited.add(start_station)
    while queue:
        current = queue.pop(0)
        for neighbor in current.neighbors:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return visited

如果你当前仅需要快速验证逻辑，也可以先用纯字典实现原型，后续重构为自定义类结构即可，二者逻辑完全兼容。

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