c - 确定两个节点之间是否存在路径的最有效方法是什么？

Question

我在 C 中得到了一个整数数组(旨在表示节点的二维矩阵)，它可以保存 0 或 1。给定 2 个“0”节点的坐标，我应该简单地找出它们之间是否存在 0 路径(节点相邻连接的位置 - 上、下、左、右)。

是否有比 BFS/DFS 更简单的替代方案可以用来解决我的问题？我知道使用BFS/DFS，我不仅可以确定路径是否存在，还可以找到并返回工作路径？只是想知道这对于这个问题是否太过分了。

Answer 1

我相信在一般情况下深度优先搜索(使用缓存以确保您只访问给定节点一次)通常是检查路径是否存在的最快方法。

如果您的数据是集群式的，那么首先查找集群之间的连接可能会更快。如果您需要多次执行此检查，那么构建这些集群并对其进行搜索会很有帮助。

如果您了解有关图表的更多信息，您可能可以进行优化。例如，如果您知道任何连接的节点也必须是邻居，那么您将使用 BFS 而不是 DFS。如果您的图具有某种空间(或类似)关系，那么 A* 可能比 DFS 更快。

在不了解您的具体情况的情况下，我想不出任何更有帮助的事情。说得具体一些，您可以获得更高质量的答案。

编辑:重读你的问题，听起来就像你在 map 上找到一条路径。我建议查看 A*，如果有许多长度相似的路径可能会更快。如果正确的路径比死胡同长得多，那么 DFS 可能仍然更快。

编辑2，电动布加洛:如果您在一张 map 上多次执行此检查，并且只需要知道是否存在任何路径，那么最快的解决方案可能是在 map 和标签上进行洪水填充地区。然后您需要做的就是检查您的两个点是否在同一区域。