我正在寻找一种有效的方法来实现加权无向图，只知道提前的边数。
样本输入：
N（边数）
AB x（x 是从 A 到 B 的距离）
。
.
我曾考虑使用 Node* 的邻接列表（我需要知道邻居）并将节点存储在动态哈希表中（我不知道我将采用多少个节点，所以我需要一个动态 - 搜索/插入 - 容器）。
有更好的方法吗？
对不起，我的英语不好！:D
问问题
201 次
1 回答
0
给定您输入的格式，一个非常合理的方法是使用列表的哈希表，其中键是节点，值是（节点，距离）对的列表。或者，如果您有一个密集图并且希望能够快速确定从一个节点到另一个节点的距离，最好有一个哈希表的哈希表，其中顶级哈希表将节点映射到第二个哈希表，然后将原始节点具有边缘的每个节点映射到其成本。这仍然可以让您遍历节点的传出边，但可以更快地查找距离。
另一个想法（取决于用例）是从构建第一个数据结构（列表的哈希表）开始，然后通过构建邻接矩阵对其进行后期处理。如果您不需要遍历节点的传出边并且需要快速随机访问节点之间的距离，这将很有用。它类似于哈希表的哈希表，但可能更节省空间。
希望这可以帮助！
于 2013-01-17T16:55:53.150 回答