我最初是通过两种方式来做的。一种方法是将访问过的节点存储在列表中并遍历该列表以确定之前是否已访问过节点。另一个是使用一个布尔数组来跟踪访问过和未访问过的节点。我真的很感兴趣，最好的方法是什么？
问问题
1168 次
2 回答
6
一种可用于微优化（更好的缓存行为，避免查找）的方法是在每个节点对象上存储一个标志。明显的缺点是图算法不可重入。想要在遍历过程中做不同的图遍历来做决定吗？好吧，你不能。您还必须记住之后清除所有这些标志。
另一类是在每次遍历的基础上维护一个单独的数据结构。您提供的两种方法都属于此范围，尽管列表方法效率非常低 - 每次查找的 O(n) 时间。布尔数组（可能压缩为位集；此选项非常节省空间）在时间和空间上都简单高效，但要求节点具有连续的索引/ID。这并不总是给出，并且会对图形处理的其他部分产生影响。
如果你没有那个，而是用指针引用图形对象，你可以使用基于它的映射。在 Python 等高级语言中，这非常简单（并且由于高度调整的哈希表/集合数据结构，效率也很高）。
明显的优势是图遍历是可重入的。虽然这听起来可能不多，但我可以证明有时确实会出现这种有用的情况。
于 2012-10-18T20:12:29.237 回答
0
取决于您的使用情况，为了获得更好的时间性能，您可以使用哈希映射您也可以使用 b-tree 来存储节点 O(logn) 插入和查找
就个人而言，我会使用哈希映射，基于每个节点的唯一值。您可以控制哈希图的大小以反映您的需求，并且使用良好的哈希函数可以控制冲突。查看此代码以获取示例https://github.com/himanshujindal/Reconstructing-Books-from-Google-Ngrams
于 2012-10-18T20:11:08.147 回答