最快的连续循环检测
Fastest Continual Cycle Detection
我正在尝试构建一个有向图实现，我可以从中添加和删除 nodes/edges，并且我可以查询是否有任何节点参与循环。通过参与，我的意思是存在从该节点返回到自身的路径。现在，每当我查询单个节点时，我都必须在该节点上 运行 DFS，如果我可以再次到达该节点，那么我 return。但是，我想通过允许用户一次查询多个节点来扩展我的查询功能，所以我想使用比简单地多次 运行ning DFS 更复杂的东西。有人有什么建议吗？
对于那里的任何人，我最终使用了 Tarjan 的强连通分量算法。我通过算法跟踪每个 运行 期间访问了哪些节点，如果我查询已经访问过的节点，我将跳过该节点。最终，对于单个查询，我最多访问图中的每个节点一次。
我正在尝试构建一个有向图实现，我可以从中添加和删除 nodes/edges，并且我可以查询是否有任何节点参与循环。通过参与，我的意思是存在从该节点返回到自身的路径。现在，每当我查询单个节点时，我都必须在该节点上 运行 DFS，如果我可以再次到达该节点，那么我 return。但是，我想通过允许用户一次查询多个节点来扩展我的查询功能，所以我想使用比简单地多次 运行ning DFS 更复杂的东西。有人有什么建议吗？
对于那里的任何人，我最终使用了 Tarjan 的强连通分量算法。我通过算法跟踪每个 运行 期间访问了哪些节点，如果我查询已经访问过的节点，我将跳过该节点。最终，对于单个查询，我最多访问图中的每个节点一次。