graph - 查找无向图中的所有循环

Question

我需要一个工作算法来查找无向图中的所有简单循环。我知道成本可能是指数级的，而且问题是 NP 完全问题，但我将在一个小图中(最多 20-30 个顶点)使用它，并且循环数量很少。

经过长时间的研究(主要是这里)，我仍然没有一个可行的方法。以下是我的搜索摘要:

Finding all cycles in an undirected graph

Cycles in an Undirected Graph -> 仅检测是否存在循环

Finding polygons within an undirected Graph -> 非常好的描述，但没有解决方案

Finding all cycles in a directed graph -> 仅在有向图中查找循环

Detect cycles in undirected graph using boost graph library

我找到的解决我的问题的唯一答案是:

Find all cycles in graph, redux

似乎找到一组基本的循环并对它们进行异或运算就可以解决问题。找到一组基本的循环很容易，但我不明白如何将它们组合起来以获得图中的所有循环......

Answer 1

对于无向图，标准方法是寻找所谓的循环基础:一组简单的循环，可以通过组合生成所有其他循环。这些不一定都是图中的简单循环。例如，考虑下面的图表:

    A 
  /   \
B ----- C
  \   /
    D

这里有 3 个简单的循环:A-B-C-A、B-C-D-B 和 A-B-D-C-A。然而，您可以将其中的每两个作为基础，并作为这两个的组合获得第三个。这与有向图有很大的不同，有向图由于需要观察边缘方向而无法如此自由地循环组合。

寻找无向图循环基的标准基线算法是这样的:构建一个生成树，然后对于不属于树的每条边，从该边和树上的一些边构建一个循环。这样的循环必须存在，否则边缘将成为树的一部分。

例如，上面示例图的可能生成树之一是:

    A 
  /   \
B      C
  \ 
    D

不在树中的 2 条边是 B-C 和 C-D。相应的简单循环是A-B-C-A和A-B-D-C-A。

您还可以构建以下生成树:

    A 
  /   
B ----- C
  \   
    D

对于这个生成树，简单的循环是 A-B-C-A 和 B-C-D-B。

基线算法可以通过不同的方式进行改进。据我所知，最好的改进属于 Paton(K. Paton，一种用于查找无向线性图的基本循环集的算法，Comm. ACM 12 (1969)，第 514-518 页。)。 Java 中的开源实现可在此处获取:http://code.google.com/p/niographs/ 。

我应该提到如何将循环基础中的简单循环组合起来形成新的简单循环。您首先以任意(但此后固定)顺序列出图表的所有边。然后，通过将 1 放置在属于循环的边的位置，将 0 放置在不属于循环的边的位置，用 0 和 1 的序列来表示循环。然后对序列进行按位异或 (XOR)。进行异或的原因是您想要排除属于两个循环的边，从而使组合循环变得不简单。您还需要通过检查序列的按位与是否不全为零来检查 2 个周期是否具有一些公共(public)边缘。否则 XOR 的结果将是 2 个不相交的循环，而不是一个新的简单循环。

以下是上面示例图的示例:

我们首先列出边:((AB)、(AC)、(BC)、(BD)、(CD))。那么简单循环A-B-C-A、B-D-C-B和A-B-D-C-A分别表示为(1, 1, 1, 0, 0)、(0, 0, 1, 1, 1)和(1, 1, 0, 1, 1)。例如，现在我们可以将 A-B-C-A 与 B-D-C-B 进行异或，结果是 (1, 1, 0, 1, 1)，这正是 A-B-D-C-A。或者我们可以对 A-B-C-A 和 A-B-D-C-A 进行异或，结果为 (0, 0, 1, 1, 1)。这正是 B-D-C-B。

给定一个循环基础，您可以通过检查 2 个或更多不同基础循环的所有可能组合来发现所有简单循环。此处更详细地描述了该过程:http://dspace.mit.edu/bitstream/handle/1721.1/68106/FTL_R_1982_07.pdf第 14 页。

为了完整起见，我注意到使用算法来查找有向图的所有简单循环似乎是可能的(并且效率低下)。无向图的每条边都可以用两条方向相反的有向边代替。那么有向图的算法应该可以工作。无向图的每个边都会有 1 个“假”2 节点循环，必须忽略该循环，并且无向图的每个简单循环都有顺时针和逆时针版本。用于查找有向图中所有循环的算法的 Java 开源实现可以在我已经引用的链接中找到。