DFS Retour arrière avec Java

Question

J'ai des problèmes avec le backtracking DFS dans une matrice d'adjacence. Voici mon code: (j'ai ajouté le test dans le main au cas où quelqu'un voudrait le tester)

public class Graph {

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

    public Graph(int numVertex, int numEdges) {
        this.numVertex = numVertex;
        this.numEdges = numEdges;
        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 visited = new ArrayList();

    public Integer DFS(Graph G, int startVertex){
        int i=0;

        if(pilha.isEmpty())
            pilha.push(startVertex);

        for(i=1; i pilha = new Stack();

    public static void main(String[] args) {

        Graph g = new Graph(6, 9);

        g.addEdge(1, 2);
        g.addEdge(1, 5);
        g.addEdge(2, 4);
        g.addEdge(2, 5);
        g.addEdge(2, 6);
        g.addEdge(3, 4);
        g.addEdge(3, 5);
        g.addEdge(4, 5);
        g.addEdge(6, 4);

        g.DFS(g, 1);    

    }
}

J'essaie de résoudre le problème du chemin d'Euler. le programme résout les graphes de base mais lorsqu'il doit faire du backtracking, il ne le fait tout simplement pas. Je pense que le problème pourrait être dans les manipulations de la pile ou dans l'appel récursif de DFS. J'ai essayé beaucoup de choses, mais je n'arrive toujours pas à comprendre pourquoi il ne fait pas de backtracking. Quelqu'un peut-il m'aider ?

Answer 1

Je n'ai testé ceci qu'avec un seul élément, donc ne faites pas confiance à mon code.

public class Graph {
    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 visited = new ArrayList();
    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("Chemin : " + visited);
    }

    Stack pilha = new Stack();

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

Aussi, au lieu de poster la même question plusieurs fois en essayant de la résoudre, vous devriez probablement éditer la même question.

Answer 2

Voici la version correcte de DFS. Et remplacez visited List par hashset.

Set visited = new HashSet();

public Integer DFS(Graph G, int startVertex){
    int i=0;

    visited.add(startVertex);

    if(visited.size() == G.numVertex){
        System.out.println("CHEMIN TROUVÉ");
        System.out.println("Pile: " + pilha);
        return 1;
    }
    int result = -1;
    if(pilha.isEmpty())
        pilha.push(startVertex);

    for(i=1; i<=G.numVertex; i++){
        if(G.adj[startVertex-1][i-1] == true && visited.contains(i) == false){
            pilha.push(i);
            //visited.add(i);
            result = DFS(G, i);
            if(result == 1){
                return 1;
            }
            pilha.pop();
            //visited.remove(i);
        }
        System.out.println("Pile: " + pilha);
    }

    visited.remove(startVertex);

    return result;
}