6

我在编写一个返回在无向图上形成简单循环的所有路径的算法时遇到了一些麻烦。

我首先考虑的是从顶点 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 不同），则该路径将被丢弃。

  • 继续，直到探索了所有可能的路径。

我目前在试图避免多次发现同一个循环时遇到问题，我试图通过查看新邻居是否已经是另一条现有路径的一部分来解决这个问题，以便两条路径组合（如果独立）建立一个循环。

我的问题是：我是否遵循正确/更好/更简单的逻辑来解决这个问题。？

我会很感激你的意见

4

2 回答 2

4

根据@eminsenay 对其他问题的回答，我使用了由 Frank Meyer 开发的elementaryCycles库，来自 web_at_normalisiert_dot_de，它实现了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;
}

}
于 2013-01-13T15:44:11.203 回答
3

我是根据您想找到无弦循环来回答这个问题的，但是可以对其进行修改以找到带有和弦的循环。

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

  • 对于所有三元组，(v,s,t)：
    • v,s,t 中的任何一个组成一个三角形，在这种情况下，输出它并继续下一个三元组。
    • 否则，删除除 s 和 t 之外的 v 及其邻居，并枚举所有 st-path。

查找所有 st-path 可以通过动态规划来完成。

于 2013-01-04T15:02:40.517 回答