Tiefe erste Suche mit 1 Zyklus Drucken

Question

Meine Tiefe Erste Suche funktioniert perfekt, aber es befasst sich nicht mit Zyklen. Ich möchte auch einen Zyklus mit dem DFS drucken.

printAllPaths(VertexA, VertexC) würde in etwa wie folgt ergeben:

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 

Der Code ist unter

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

Vertex Klasse so etwas wie dieses:

public class Vertex{ 
String value; 

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

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

Ich weiß, dass wir nicht haben sollte ein Fall, in dem es unendlich druckt. Aber es sollte nur 1 Zyklus drucken. Ich habe viele Dinge ausprobiert, aber ohne Erfolg.

Answer 1

Also von dem obigen Code habe ich das Gefühl, dass Sie ein gutes Verständnis darüber haben, wie Graphen funktionieren.

Also die obige Methode würde alle Pfade in Grafik drucken. Lass diese Methode so bleiben, wie sie ist.

Um einen Zyklus in einem Diagramm zu finden, können Sie eine neue Methode erstellen, die einfach einen Zyklus für Sie findet.

Hier ist der Pseudo-Code für sie ist, ich habe es nicht ausführen, so kann ich nicht so ist es völlig richtig, aber Sie werden die Idee sicher

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

this helps erhalten!

Answer 2

Der Algorithmus ist korrekt. Das Problem ist die Umsetzung des Staates. Die Bedingung in "if (city.state == UNVISITED)" gilt nur dann, wenn "city.state" und "UNVISITED" dieselbe Klasse sind. Wenn city.state und UNVISITED vom primitiven Typ int sind, funktioniert der Algorithmus gut.

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

    private final int state; 

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

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

Und jetzt: if(city.state.getState() == State.UNVISTED.getState()) {...}

Answer 3

Wenn Sie genau einen Zyklus ermöglichen wollen, dann 0,1,2 anstelle von state.VISITED und state.UNVISITED

statt v.state = VISITED Verwendung v.state++ statt v.state = UNVISITED Verwendung v.state-- statt if(city.state == UNVISITED) Verwenden Sie if(city.state < 2)

Durch Erhöhen des Werts in der letzten Bedingung können Sie auch die Anzahl der zulässigen Zyklen festlegen.

Eigentlich erlaubt es dem Algorithmus, auf alle Städte zweimal statt auf eins zuzugreifen. Wenn also die Karte mehrere Zyklen hat, kann es mehrere Zyklen in den berechneten Routen geben, aber eine gegebene Stadt kann maximal zweimal auf jeder Route besucht werden.

Und noch etwas: Sie können auch die letzte Station der Methode zur Verfügung stellen müssen und es in der Schleife ausschließen sonst wird es in der Lösung wie ABABC, ABCBC

Eh, hier Tonnen von Mini-Zyklen ist Der ganze Code:

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