c++ - 有向图 - 如何计算图中每个其他顶点可到达的顶点数？

Question

在有向图中如何有效地计算图中每个其他顶点可达的顶点数？

Answer 1

如果图中没有环，则只能有一个这样的顶点，并且它的入度为零，并且没有其他顶点的入度为零。然后你必须运行 DFS 来检查是否所有其他顶点都可以从它到达。所以答案要么是 1，要么是 0，这取决于 DFS 的结果。

如果存在环路，则环路中的所有顶点都具有该属性，或者都不具有。

如果您检测到一个循环，请用一个顶点替换循环中的所有顶点，并为该顶点保留一个标签，说明它代表了多少个顶点。使用与上述相同的过程。即，检查入度并从新节点运行 DFS。答案将是零或标签。

可以使用 DFS 来检测循环。

图中可能有多个循环。在那种情况下，你必须消除所有这些。您可以在 DFS 的一次线性传递中消除所有这些，但这很棘手。您也可以使用 btilly 在他的回答中建议的 Tarjan 算法。