奥行き最初の検索で1サイクル印刷

Question

奥行きの最初の検索は完全に機能しますが、サイクルは処理されません。私はDFSで1サイクルも印刷したい。

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; 
} 

必ず希望のためのアイデアを得るでしょう！

Answer 2

アルゴリズムは正しいです。問題は国家の実装です。 "if（city.state == UNVISITED）"の条件は、city.stateとUNVISITEDが同じクラスである場合にのみtrueです。 city.stateとUNVISITEDがプリミティブ型intの場合、アルゴリズムは正常に動作します。

public enum State { 
    VISITED (1), 
    UNVISITED (2); 

    private final int state; 

    State(int state) { 
     this.state = state; 
    } 

    public int getState() { 
     return this.state; 
    } 
} 

そして今：if(city.state.getState() == State.UNVISTED.getState()) {...}

Answer 3

あなたは正確に一つのサイクルを許可したい場合は、v.state-- の代わりif(city.state == UNVISITED)代わりv.state = UNVISITED使用するのではなく、v.state = VISITED使用v.state++ の代わりにstate.VISITEDとstate.UNVISITED

の0,1,2を使用使用if(city.state < 2)

最後の条件の値を大きくすることで、許容されるサイクル数を設定することもできます。

実際にはアルゴリズムが1つではなく2回すべての都市にアクセスできるため、マップに複数のサイクルがある場合、計算されたルートに複数のサイクルが存在する可能性がありますが、各都市で最大2回、

そしてもう一つ：あなたは、メソッドへの最後の駅を提供し、ループでそれを除外する必要がありそうABABCのような溶液中でのミニサイクルのトンがあるだろう、ABCBC

えは、ここにあります全体のコード：

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

     v.state++; 
     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!= prev && city.state < 2) { 

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


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