algorithm - 多图中的循环检测

Question

我想在无向多图中列出所有循环。

Tarjan 的强连通分量算法是为有向图编写的。它适用于多图吗？如果没有，是否有无向多图的循环列表算法？

Answer 1

有几种方法可以将您的问题减少到 Tarjan，具体取决于您希望如何计算周期。

首先，对图表应用两个转换：

1. 通过用一对相反的有向边替换每个无向边来转换为有向图。
2. 对于每对节点，将指向相同方向的边折叠成一条边。

您将得到一个有向图。应用 Tarjan 算法。

现在，根据您对周期的看法，您可能完成也可能不完成。如果一个循环是一组节点（恰好拥有所需的边），那么您可以直接从转换后的图中读取循环。

如果一个循环是一组边（共享所需的节点），那么您需要“展开”上面步骤 2 中引入的边。对于每个折叠的边，沿着它替换的一组真实边进行枚举。对每个折叠循环中的每个边缘都这样做将在组合爆炸中产生所有实际循环。请注意，这将产生您需要修剪的虚假两个周期。

为了说明，假设原始图有三个节点和A，两条边在和之间，一条在和之间，一条在和之间。折叠图将是一个三角形，有一个循环。BCABBCAC

找到三个节点之间的循环后，遍历每个边组合以恢复完整的循环集。这里有两个循环：都包括AtoC和BtoC边。A他们选择的B边缘不同。

B如果原始图在和之间也有两条边C，则将有四个扩展图。扩展循环的总数是边数的乘积：4 == 2 * 2 * 1。