我有一个特殊的问题，一个有向图的每个顶点都有四条向外指向的路径(可以指向同一个顶点)。
开始时，我只有起始顶点，我使用DFS来发现/枚举所有顶点和边。
然后我可以使用类似Tarjan的算法将图分解成强连接的组件。
我的问题是，有没有比发现图形然后应用算法更有效的方法来做到这一点。例如，是否有一种方法将这两个部分结合起来，使它们更有效?
为了避免一开始就"发现"图，Tarjan算法需要的关键属性是，在其执行的任何时候，它应该只依赖于它迄今为止已经探索过的子图，并且它应该只通过枚举一些已经访问过的顶点的邻居来扩展这个探索过的区域。(例如，如果它要求在开始时知道图中节点或边的总数，那么你就会沉没。)从看维基百科页面算法似乎确实有这个属性,所以,您不需要执行一个单独的发现阶段开始时,你会发现每个顶点的"惰性"行for each (v, w) in E do v(列举所有的邻居和你现在一样在你发现DFS)和for each v in V do(挑v任何顶点你已经发现w在前面一步,但你还没有访问和调用strongconnect(v))。
也就是说，由于初始DFS发现阶段只需要线性时间，如果消除它可以大大加快速度，我会感到惊讶。如果您的图形太大，以至于无法放入缓存，那么它可以将总时间减半。