java - 深度优先搜索 1 循环打印

Question

我的深度优先搜索工作得很好，但它不处理循环。我也想用 DFS 打印一个周期。

printAllPaths(VertexA, VertexC) 会产生如下结果:

A B C D C //with cycle since C repeated
A B C 
A D C 
A D E B C 
A E B C

代码如下

  void printAllPathsUtil(Vertex v, Vertex d, ArrayList<Vertex> path){

        v.state = VISITED;
        path.add(v);

        if (v == d) {
            for (Vertex p : path) {
                System.out.print("Print: " + p.value + " ");
            }
            System.out.println();
        }
        else {
            for (Vertex city : v.outboundCity){

                if (city.state == UNVISITED) {

                    printAllPathsUtil(city, d, path);
                }
            }
        }
        path.remove(v);
        v.state = UNVISITED;
    }


    void printAllPaths(Vertex v, Vertex u){
        clearStates();
        ArrayList<Vertex> path = new ArrayList<>();
        printAllPathsUtil(v, u, path);
    }

顶点类是这样的:

public class Vertex{
String value;

Vertex previous = null;
int minDistance = Integer.MAX_VALUE;

List<Vertex> inboundCity;
List<Vertex> outboundCity;
State state;
}

我知道我们不应该出现无限打印的情况。但它应该只打印 1 个周期。我尝试了很多东西但无济于事。

Answer 1

所以从上面的代码我觉得你对图表的工作原理有了很好的理解。

所以上面的方法会打印图中的所有路径。让那个方法保持原样。

为了在图中找到环，您可以创建一个新方法来简单地为您找到环。

这是它的伪代码，我还没有运行它，所以我不能，所以它是完全正确的，但你肯定会明白这一点

ArrayList<Vertex> dfsCycle(Vertex v, ArrayList<Vertex> path) {
 if(v.state = VISITED) {
   System.out.println("Yayy found a cycle");
  return path;
 }
 path.add(v);
 for(Vertex city : v.outboundCity) {
   dfsCycle(city,path);
 }
 return path;
}

希望这对您有所帮助!