深度首次搜索1個週期打印

我的深度首次搜索完美，但它不涉及週期。我想用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個週期。我嘗試了很多東西，但無濟於事。

來源

2017-08-24 maverick30

所以從上面的代碼我覺得你對圖表的工作原理有了很好的理解。

所以上面的方法會打印圖中的所有路徑。讓該方法保持原樣。

爲了在圖表中查找循環，您可以創建一個新的方法，爲您找到一個循環。

這裏是它的僞代碼，我還沒有運行它，所以我不能那麼它是完全正確的，但你會得到的想法肯定

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

希望這有助於！

來源

2017-08-24 14:23:25 zenwraight

該算法是正確的。問題在於國家的執行。「if（city.state == UNVISITED）」中的條件只有在city.state和UNVISITED是同一個類的情況下才成立。如果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()) {...}

來源

2017-08-24 14:28:26 DoctorLOL

如果你想允許只有一個週期，然後使用0,1,2，而不是state.VISITED和state.UNVISITED

，而不是v.state = VISITED使用v.state++ 代替v.state = UNVISITED使用v.state-- 代替if(city.state == UNVISITED)使用if(city.state < 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); 
    }

來源

2017-08-24 14:43:18 Selindek

深度首次搜索1個週期打印

回答

相關問題