algorithm - 计算有向图中的循环数

Question

我遇到了一个有趣的问题，即计算有向图中的周期数。

为了检测图中的循环，我们可以使用DFS，但为了检测循环数，DFS 不会有太大用处，因为某些边在某些循环中很常见。

我想弄清楚生成树在这里是否有帮助。

有什么想法吗？

Answer 1

这是一个派生结构以帮助解决循环计数问题的算法：

• 对于每个节点，导出入度（传入边的数量）和出度。
• 删除所有入度为零的节点。这些不是循环的一部分。从他们的继任者中，从入度中减去 1。从他们的前辈中，从出度中减去 1。
• 删除所有出度为零的节点，因为它们也不能成为循环的一部分。像以前一样，相应地从相邻节点中减去入度和出度。
• 重复前面的 2 个步骤，直到不再有入度或出度为零的节点。现在所有剩余的节点都是一个循环的一部分。
• 所有 indegree=1 或 outdegree=1 的节点都可以分别与其前任或后继节点组合。这些节点可以组合在一个列表中，因为它们将位于所有完全相同的循环中。

剩下的图只有入度和出度都大于或等于 2 的节点。它包含对原始图节点的引用。

• 现在在剩余图中找到强连通分量。
  • 为只能以单一可能方式（即单一循环）遍历的循环找到奇异节点。
  • 具有多个（至少 3 个）组合节点的子图表示更复杂的循环结构。可以根据循环计数的适当定义来计算循环。计数可以通过回溯来完成。