我正在寻找 Prim 算法的图形的良好表示。
例如表示 BFS 的图
typedef std::unordered_map<int, std::queue<int> > gr;
优雅简洁，它将每个顶点映射到邻居队列。
对于 Dijkstra，它有点复杂（权重在表示中）
typedef std::pair<int, double> to_weighted_edge;
typedef std::unordered_map<int, std::vector<to_weighted_edge> > gr;
- 使用优先队列。
然而，如果在 Prim 的算法中遵循类似的结构，则还需要存储每条边的源，并且如果图形表示如下：
typedef std::pair < std::pair<int,int>, double> from_to_weighted_edge;
typedef std::unordered_map<int, std::vector<from_to_weighted_edge> > gr;
然后存储了冗余信息（源/来自顶点）。
欢迎任何有关 Prim 算法的 C++ 中最佳图形表示的建议！
ps：当然可以将图表示为，std::vector<from_to_weighted_edge>但不会有 O(1) 的邻居查找，这是所有常见图表示的共同特征。