java - すべての可能なパスを見つけるための DFS

Question

グラフ内のあるノードから別のノードへのパスを見つける次の Java コードがあります。それを変更して、すべての可能なパスを表示できるようにします。ここでは 1 つのパスのみを示しており、サイクルとしては?

出力: パス: [1, 2, 3, 4, 1]

ノード 1 と 4 の間のパスの場合、正しい出力は次のようになります。

最初のパス: 1 -> 2 -> 3 -> 4

2 番目のパス: 1 -> 3 -> 4

コード：

import java.util.Iterator;
import java.util.Set;
import java.util.Stack;
import java.util.TreeSet;
import java.util.List;
import java.util.ArrayList;

public class Graph {

    Stack<Integer> pilha = new Stack<Integer>();


    private int numVertex;
    private boolean[][] adj;

    public Graph(int numVertex, int numEdges) {
        this.numVertex = numVertex;
        this.adj = new boolean[numVertex][numVertex];
    }

    public void addEdge(int start, int end){
        adj[start-1][end-1] = true;
        adj[end-1][start-1] = true;
    }

    List<Integer> visited = new ArrayList<Integer>();
    public void DFS(Graph G, int startVertex){
        int i=0;
        pilha.push(startVertex);

        while (!pilha.empty()) {
            int v = pilha.peek();
            Boolean hasNeighbor = false;
            for (i = 1; i <= G.numVertex; i++) {
                if(G.adj[i-1][v-1] != false) {
                    hasNeighbor = true;
                    pilha.push(i);
                    G.adj[i-1][v-1] = false;
                    G.adj[v-1][i-1] = false;
                    break;
                }
            }
            if (!hasNeighbor) {
                visited.add(0, pilha.pop());
            }
        }
        System.out.println("Path: " + visited);
    }



    public static void main(String[] args) {
        Graph g = new Graph(4, 4);
        g.addEdge(1, 2);
        g.addEdge(2, 3);
        g.addEdge(1, 3);
        g.addEdge(3, 4);
        g.DFS(g, 1);    
    }
}