algorithm - 一次创建一个图并找到强连接的组件（不仅仅是 Tarjan！）

Question

我有一个特殊的问题，即有向图的每个顶点恰好有四个向外指向的路径（它们可以指向同一个顶点）。

一开始，我只有起始顶点，我使用 DFS 发现/枚举所有顶点和边。

然后我可以使用 Tarjan 算法之类的东西将图形分解为强连接的组件。

我的问题是，有没有比发现图形然后应用算法更有效的方法。例如，有没有办法将这两个部分结合起来以提高效率？

Answer 1

为了避免必须在一开始就“发现”图，Tarjan 算法需要的关键属性是，在其执行的任何时候，它应该只依赖于它迄今为止探索过的子图，并且它应该只扩展这个通过枚举一些已经访问过的顶点的邻居来探索区域。（例如，如果一开始就需要知道图中的节点或边的总数，那么您就会陷入困境。）从查看维基百科页面看来，该算法确实具有此属性，所以不，您不需要在开始时执行单独的发现阶段-您可以在行中“懒惰地”发现每个顶点for each (v, w) in E do（就像您当前在发现 DFS 中所做的那样枚举 v 的所有邻居）和for each v in V do（只需选择 v 作为您在上一步中已发现为 aw 的任何顶点，但您尚未通过调用 访问该顶点strongconnect(v)）。

也就是说，由于您最初的 DFS 发现阶段无论如何只需要线性时间，如果消除它会大大加快速度，我会感到惊讶。但是，如果您的图表太大以至于无法放入缓存中，则总时间可能会减半。