Depth First Search With 1 cycle Print

Question

My Depth First search works perfectly but it does not deal with Cycles. I want to print one cycle too with the DFS.

printAllPaths(VertexA, VertexC) would result in something like this:

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

The code is below

  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 Class is something like this:

public class Vertex{
String value;

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

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

I know we should not have a case where it prints infinitely. But it should only print 1 cycle. I have tried many things but to no avail.

Answer 1

If you want to allow exactly one cycle then use 0,1,2 instead of state.VISITED and state.UNVISITED

instead of v.state = VISITED use v.state++ instead of v.state = UNVISITED use v.state-- instead of if(city.state == UNVISITED) use if(city.state < 2)

By increasing the value in the last condition you can also set the number of allowed cycles.

Actually it allows the algorithm to access all cities twice instead of one, so if the map has multiple cycles then there could be multiple cycles in the calculated routes but a given city can be visited at max twice in each route.

And one more thing: You also have to provide the last station to the method and exclude it in the loop otherwise there will be tons of mini-cycles in the solution like ABABC, ABCBC

Eh, here is the whole 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);
    }