在一个无向图中，找到形成简单循环的所有路径。

Question

我在编写一个算法，用于返回无向图上形成简单循环的所有路径，但是遇到了一些问题。

首先，我考虑从顶点A开始所有的循环，对于下面的图来说，这将是：

A,B,E,G,F A,B,E,D,F A,B,C,D,F A,B,C,D,E,G,F

其他的循环包括：

B,C,D,E F,D,E,G

但是这些可以通过再次调用算法，从B和D开始分别找到。

我的当前方法是从A开始构建所有可能的路径，访问A的所有邻居，然后访问邻居的邻居等等，同时遵循以下规则：

每当存在多个邻居时，就会发现一个分叉，并创建并探索一个从A开始的新路径。 如果任何一个创建的路径访问原始顶点，则该路径为循环。 如果任何一个创建的路径两次访问同一个顶点（与A不同），则该路径被丢弃。 继续直到所有可能的路径都被探索完毕。

我目前遇到的问题是如何避免找到相同的循环超过一次，我正在尝试通过查看新邻居是否已经是另一个现有路径的一部分来解决这个问题，以便如果它们是独立的，则合并这两条路径会组成一个循环。

我的问题是：我是否在遵循解决此问题的正确/更好/更简单的逻辑？

感谢您的评论。

- Jose Ospina

---

请参阅https://dev59.com/Gm445IYBdhLWcg3wDV8P。看似简单的图形很容易拥有最坏情况下指数级数量的循环。你为什么需要这样做？ - Gene

您提供的链接中的链接是用于有向图的。但现在我开始思考一个解决方案，即通过使用这些算法，将每个边替换为两个有向边，并忽略仅由两个顶点构成的所有循环。我想要一个布局算法的循环，我知道它很重，但我只处理少量小于50个节点。 - Jose Ospina

我尝试了@eminsenay在[链接]（https://dev59.com/PXRB5IYBdhLWcg3wtJGF）中提到的有向图算法，可以从[链接] http://normalisiert.de/code/java/elementaryCycles.zip下载。我将每个边缘更改为两个有向边缘，并且它几乎很好地工作，它给我相同的循环两次，每个方向一个。我是否必须比较所有返回的周期以查看它们中的任何一个是否等效于另一个？它们可以从不同的节点开始并且也是等效的周期。 - Jose Ospina

也许在链接中有一个简化版本的算法（在上面的elemenetaryCycles.zip文件中用Java实现），适用于无向图，不考虑长度为2的循环并忽略循环的方向...它应该会更快，因为存在较少的循环… - Jose Ospina

Answer 1

根据@eminsenay对其他问题的回答，我使用了由Frank Meyer开发的elementaryCycles库，该库实现了Johnson的算法。

然而，由于这个库是用于有向图的，所以我添加了一些例程来：

• 从JGraphT无向图构建邻接矩阵（Meyer的库需要）
• 过滤结果以避免长度为2的循环
• 删除重复的循环，因为Meyer的库是针对有向图的，每个无向循环都是两个有向循环（一个在每个方向上）。

代码如下：

package test;

import java.util.*;

import org.jgraph.graph.DefaultEdge;
import org.jgrapht.UndirectedGraph;
import org.jgrapht.graph.SimpleGraph;


public class GraphHandling<V> {

private UndirectedGraph<V,DefaultEdge>     graph;
private List<V>                         vertexList;
private boolean                         adjMatrix[][];

public GraphHandling() {
    this.graph             = new SimpleGraph<V, DefaultEdge>(DefaultEdge.class);
    this.vertexList     = new ArrayList<V>();
}

public void addVertex(V vertex) {
    this.graph.addVertex(vertex);
    this.vertexList.add(vertex);
}

public void addEdge(V vertex1, V vertex2) {
    this.graph.addEdge(vertex1, vertex2);
}

public UndirectedGraph<V, DefaultEdge> getGraph() {
    return graph;
}

public List<List<V>>     getAllCycles() {
    this.buildAdjancyMatrix();

    @SuppressWarnings("unchecked")
    V[] vertexArray                 = (V[]) this.vertexList.toArray();
    ElementaryCyclesSearch     ecs     = new ElementaryCyclesSearch(this.adjMatrix, vertexArray);

    @SuppressWarnings("unchecked")
    List<List<V>>             cycles0    = ecs.getElementaryCycles();

    // remove cycles of size 2
    Iterator<List<V>>         listIt    = cycles0.iterator();
    while(listIt.hasNext()) {
        List<V> cycle = listIt.next();

        if(cycle.size() == 2) {
            listIt.remove();
        }
    }

    // remove repeated cycles (two cycles are repeated if they have the same vertex (no matter the order)
    List<List<V>> cycles1             = removeRepeatedLists(cycles0);

    for(List<V> cycle : cycles1) {
        System.out.println(cycle);    
    }


    return cycles1;
}

private void buildAdjancyMatrix() {
    Set<DefaultEdge>     edges        = this.graph.edgeSet();
    Integer             nVertex     = this.vertexList.size();
    this.adjMatrix                     = new boolean[nVertex][nVertex];

    for(DefaultEdge edge : edges) {
        V v1     = this.graph.getEdgeSource(edge);
        V v2     = this.graph.getEdgeTarget(edge);

        int     i = this.vertexList.indexOf(v1);
        int     j = this.vertexList.indexOf(v2);

        this.adjMatrix[i][j]     = true;
        this.adjMatrix[j][i]     = true;
    }
}
/* Here repeated lists are those with the same elements, no matter the order, 
 * and it is assumed that there are no repeated elements on any of the lists*/
private List<List<V>> removeRepeatedLists(List<List<V>> listOfLists) {
    List<List<V>> inputListOfLists         = new ArrayList<List<V>>(listOfLists);
    List<List<V>> outputListOfLists     = new ArrayList<List<V>>();

    while(!inputListOfLists.isEmpty()) {
        // get the first element
        List<V> thisList     = inputListOfLists.get(0);
        // remove it
        inputListOfLists.remove(0);
        outputListOfLists.add(thisList);
        // look for duplicates
        Integer             nEl     = thisList.size();
        Iterator<List<V>>     listIt    = inputListOfLists.iterator();
        while(listIt.hasNext()) {
            List<V>     remainingList     = listIt.next();

            if(remainingList.size() == nEl) {
                if(remainingList.containsAll(thisList)) {
                    listIt.remove();    
                }
            }
        }

    }

    return outputListOfLists;
}

}

- Jose Ospina

Answer 2

我回答这个问题是基于你想要寻找无弦环，但可以修改以查找带有弦的环。

这个问题简化为在两个顶点s和t之间找到所有（包含）最小路径。

对于所有三元组(v, s, t)：

• 如果v，s，t形成一个三角形，则输出它并继续下一个三元组；
• 否则，除了s和t之外，删除v及其邻居，并枚举所有s-t路径。

可以通过动态规划来找到所有s-t路径。

- Pål GD

---

谢谢回答，我还有点迷失。这是我的理解：在上面的图中，让A和B分别对应你的算法中的s和t，然后：1）让C为v，没有三角形，移除C和H，从A到B的路径为{A-B、A-F-D-E-B、A-F-G-E-B}。2）让D为v，没有三角形，移除D、C、F和E，从A到B的路径为{A-B}。3）让E为v，没有三角形，移除E、D和G，从A到B的路径为{A-B}……以此类推……那么我何时才能找到循环呢？ - Jose Ospina

在我的例子中，s、v、t是一个环中连续的顶点。如果你从图中移除v，并找到一条从s到t的路径，那么通过添加v，你就可以得到一个环。在你的例子中，让s=A，v=B，t=C。现在，如果你从图中移除v=B并在s=A和t=C之间找到路径，当你将v=B重新加入图中时，你会得到环。 - Pål GD

所以，正如你所提到的，我首先选择s = A，v = B和t = C，删除B、E和H，从A到C只找到了一条路径：{A-F-D-C}。（仍然缺少三个循环，所以我假设我需要从A开始所有可能的连续三元组），因此我选择s = A，v = B和t = E，删除B、C和H，从A到E的路径是：{A-F-D-E，A-F-G-E} 找到了两个更多的循环，不错。然后，对于s = A，v = B和t = H，从A到H没有路径。然后，对于s = A，v = F和t = D，删除F和G，从A到D的路径是：{A-B-C-D}，{A-B-E-D}（哎呀，重复的循环，我怎么知道？）.... 可能我现在还漏掉了其他东西..... 安心 - Jose Ospina

谢谢您的回答，我明白您的理论是正确的，但我正在寻找一些可以直接实现的库或算法。因为“通过动态规划来查找所有s-t路径”留下了很大的空间。最终，我使用了现有的针对有向图的代码，并进行了少量修改以处理无向图。 - Jose Ospina