DFS Backtracking с Java

Question

У меня проблемы с возвратом DFS в матрице смежности. Вот мой код: (я добавил тест в основную на тот случай, если кто-то захочет его протестировать)

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<Integer> visited = new ArrayList<Integer>();

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

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

        for(i=1; i<G.numVertex; i++){
            pilha.push(i);
            if(G.adj[i-1][startVertex-1] != false){
                G.adj[i-1][startVertex-1] = false;
                G.adj[startVertex-1][i-1] = false;
                DFS(G,i);
                break;
            }else{
                visited.add(pilha.pop());
            }
            System.out.println("Stack: " + pilha);
        }
        return -1;
    }

    Stack<Integer> 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);    

    }
}

Я пытаюсь решить проблему пути Эйлера. программа решает основные графики, но когда ей нужно вернуться назад, она просто этого не делает. Я думаю, что проблема может быть в манипуляциях со стеком или в рекурсивном вызове dfs. Я много чего перепробовал, но до сих пор не могу понять, почему он не возвращается. Кто-нибудь может мне помочь?

Answer 1

Вот правильная версия DFS.И заменить посещенных List на hashset.

Set<Integer> visited = new HashSet<Integer>();

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

    visited.add(startVertex);

    if(visited.size() == G.numVertex){
        System.out.println("FOUND PATH");
        System.out.println("Stack: " + 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("Stack: " + pilha);
    }

    visited.remove(startVertex);

    return result;
}

Answer 2

Я проверял это только с одним, так что не верь моему коду.

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

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

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

Кроме того, вместо того, чтобы публиковать один и тот же вопрос несколько раз, когда вы пытаетесь его решить, вам, вероятно, следует отредактировать один и тот же вопрос.