是否有一种算法可以在有向图中检查一个顶点(比方说 V2)是否可以从顶点 V1 到达，而无需遍历所有顶点？
最佳答案
您可能无需遍历所有边就可以找到到该节点的路径，如果是这样，您可以尽快给出肯定的答案。仅遍历所有边就可以确认该节点不可到达(除非有一些您未声明的其他约束可用于更早地消除这种可能性)。
编辑:我应该补充一点，这取决于您需要多久进行一次查询以及您的图表有多大(和密集)。如果你需要在一个相对较小的图上做大量的查询，那么预处理图中的数据以产生一个矩阵，在任何 V1 和 V2 的交点处有一个位来指示是否存在连接可能是有意义的从 V1 到 V2。这并不能避免遍历图，但可以避免在查询时遍历图。即，它基本上是一种贪婪算法，假设您最终将使用足够多的组合，最简单的方法是遍历所有组合并存储结果。根据图的大小，预处理步骤可能会很慢，但一旦完成，执行查询就会变得非常快(常数时间，通常是一个非常小的常数)。
关于algorithm - 检查顶点是否可达的算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/3302134/