用途:以 Python 实现常用图遍历与寻路算法,原子职责为高效执行图遍历与路径查找,覆盖无权与带权图场景。
主要能力:邻接表与带权邻接表表示;递归与迭代版 DFS;BFS 遍历及无权图最短路径长度;Dijkstra 单源最短路与带路径重建版本;Union-Find(路径压缩与按秩合并,支持连通分量、环检测、Kruskal);Kahn 算法拓扑排序并检测环;附 pytest 单元测试模板。复杂度:DFS/BFS/拓扑排序为 O(V+E),Dijkstra 为 O((V+E) log V),Union-Find 单次操作近似 O(α(n))。
使用方式:按资料中的类型别名 Graph=Dict[int, List[int]]、WeightedGraph=Dict[int, List[Tuple[int, int]]] 构造图,直接调用对应函数,如 dijkstra(graph, start) 返回距离字典,dijkstra_with_path 返回 (distance, path),UnionFind(n) 后调用 union/find/connected/get_components。
适用场景:无权图最短路、带非负权最短路、连通分量统计、任务依赖排序。
限制:Dijkstra 不允许负权,遇负权会抛出 ValueError,需改用 Bellman-Ford;拓扑排序遇环返回空列表;资料未提供安装命令、平台与收费信息,暂未提供。