logo标签列表

在有向图中寻找可达顶点

algorithmgraphgraph-algorithm
4

我想请问以下问题:

给定一个有向图（不一定是DAG），对于每个顶点v，计算从v可达的顶点数量。

使用暴力算法（n次DFS）可以在O(n^2)的时间复杂度内得到答案。是否有一种更快的方法来计算呢？我们可以使用强联通分量将给定的图转化为DAG。我尝试过利用先前计算出的值，这样我只需要访问每个顶点一次，但这根本行不通。最大的问题在于像这样的图：

  2 -> 1
  3 -> 2
  3 -> 1
  1 -> 4

我从顶点1开始运行深度优先搜索并返回结果1。然后，使用它，我可以立即计算出2的答案（在第二次深度优先搜索中我不再进入顶点1，而是使用其答案），这个答案为2。然后我到达了顶点3...该算法会汇总1和2的结果，因为我可以到达这两个顶点。但是，顶点1已经在计算顶点2的结果中计算过了。这样就得到了等于4的答案，这是不正确的。

如果从A可以到达B，则从B可到达的所有节点也可以从A到达。您可以利用这一点避免重复遍历。 - meowgoesthedog
1
确实如此，但我必须存储每个可达的顶点，这仍然是O(n^2)。 - Maras
不一定需要这样做；你可以在执行第一次深度优先搜索时记录从某个节点可达的节点数量。在随后的DFS遍历中，一旦到达已访问过的节点，就停止，并添加上从该节点可达的节点数。这样，你最多只会遍历每个节点两次（我认为是这样 - 如果你发现有矛盾，请纠正我）。 - meowgoesthedog
如果有两个顶点都已经被访问过，但它们可达的顶点完全不同，那该怎么办？ - Maras
这并不重要，因为您仍然需要遍历图中的所有节点，但是每个从节点执行的DFS遍历都会减少仍需要遍历的节点集合。 - meowgoesthedog
我感觉你还没有理解。试试这个图表：3 -> 2，3 -> 1，1 -> 2，2-> 7，4 -> 5，6 -> 4，6 - > 3。 - Maras
2个回答
4
3
我认为最好的算法运行复杂度是O(|V| * |E|)。
算法：
1 - 对图进行强连通分量(SCC)处理。
2 - 构建简化图Gr。
3 - 对于Gr中的每个顶点v以及访问过的不同SCC（包括v的SCC），运行一个dfs，并累计它们中的顶点数量（从步骤1预先计算）。
使用此算法，您可以将暴力解决方案中的|V|*|V|因子消除，其时间复杂度为O(|V| * |V| + |V| * |E|))。
这是我知道的解决此问题的最佳且简单的算法。我没有证明，但我非常确定没有更好的方法。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接