在图算法中，确定节点是否被访问的最佳方法是什么？

Question

3

我最初有两种方式来实现这个功能。一种方法是将已访问的节点存储在列表中，并遍历该列表以确定节点是否已被访问过。另一种方法是使用一个布尔数组，该数组跟踪已访问和未访问的节点。那么，哪种方法更好呢？

- user793789

3

我不确定是否理解，但如果所有节点都有索引，则可能是布尔数组/位字段。 - Mooing Duck

1

“最好”是什么意思？使用最少的内存的解决方案还是具有最快查找速度的解决方案？ - Anders Lindahl

1

为什么要关闭这个问题？这个问题似乎非常适合在stackoverflow上提问。 - comingstorm

为什么关闭？他可能需要说明他正在寻找哪种最佳方案。但这个问题对很多人来说仍然有价值和实用性。 - Li haonan

2个回答

0

根据您的使用情况，为了获得更好的时间性能，您可以使用哈希映射。您还可以使用B树来存储节点O(logn)插入和查找

个人而言，我会使用基于每个节点的唯一值的哈希映射。您可以控制哈希映射的大小以反映您的需求，并且通过良好的哈希函数，可以控制碰撞。请参阅此代码示例https://github.com/himanshujindal/Reconstructing-Books-from-Google-Ngrams

- Himanshu Jindal

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- user395760 · Accepted Answer

一种微优化（更好的缓存行为，避免查找）的方法是在每个节点对象上存储标志位。明显的缺点是图算法不可重入。想要进行不同的图遍历以便在遍历过程中做出决策？那么你就不能这样做了。你还需要记得清除所有这些标志。

另一种类型是在每次遍历时维护单独的数据结构。尽管你提供的两种方法都属于这种类型，但是列表方法非常低效--每次查询的时间复杂度是O(n)。布尔数组（可能压缩成位集；这个选项非常节省空间）在时间和空间上都是简单而高效的，但需要节点具有连续的索引/标识符。这并不总是成立，并对图处理的其他部分产生影响。

如果您没有这个条件，而是用指针引用图对象，那么可以使用基于指针的映射。在高级语言（如Python）中，这非常简单（因为高度调优的哈希表/集合数据结构也很有效）。

明显的优点是图遍历是可重入的。虽然这听起来可能不是很重要，但我可以证明，在某些情况下这很有用。