插入并迅速
答
图邻接列表的一个好实现是使用动态分配的整数向量。
假设您的图中至多有N个节点。您可以将图存储在一个由N个动态分配的整数向量组成的数组中。 它看起来像这样:
矢量[N]
从节点x插入一个边缘节点Y使用:
矢量[X] .push(Y)
这如果图很稀疏(没有很多边),可以快速找到节点的所有输出边。
如果您想查找x和y之间是否存在边,则必须通过vector [x]并搜索它。如果你想加快速度,那么如果节点数很少(小于1000是合理的),你可以使用2维布尔数组。
如果你有很多节点并且想要加速这个操作,你可以使用散列表。
答
根据我的hash_map
这功课吗?在现实世界中,答案是“取决于”。 – 2010-09-21 14:09:16
直接取决于插入和查找的比例;它也可以取决于插入和查找的类型(插入或寻找数据时可能会有一些有用的关联) – Unreason 2010-09-21 14:16:41
没有作业,我想了解图形邻接列表的最佳实现。 – Avinash 2010-09-21 14:19:17