Рекурсивная функция, возвращающая окончательный результат до того, как все рекурсивные вызовы выталкиваются из стека вызовов - PullRequest
Новая
       50

Рекурсивная функция, возвращающая окончательный результат до того, как все рекурсивные вызовы выталкиваются из стека вызовов

2 голосов
/ 20 мая 2019

Я не понимаю, почему этот алгоритм DFS, который я написал, не посещает последнюю вершину моего графа. Вот код:

График / класс вершин 

import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;

public class Graph {

    private HashMap<Vertex, ArrayList<Vertex>> adjacencyList;

    public Graph() {
        this.adjacencyList = new HashMap<>();
    }

    public void addVertex(Vertex vertex) {
        if (!adjacencyList.containsKey(vertex)) {
            adjacencyList.put(vertex, new ArrayList<>());
        }
    }

    public void addEdge(Vertex vertex1, Vertex vertex2) {
        this.adjacencyList.get(vertex1).add(vertex2);
        this.adjacencyList.get(vertex2).add(vertex1);
    }

    public HashMap<Vertex, ArrayList<Vertex>> getAdjacencyList() {
        return adjacencyList;
    }

    public void printAdjacencyList(Vertex vertex) {
        System.out.print(vertex.getValue() + ": ");
        for (Vertex v : adjacencyList.get(vertex)) {
            System.out.print(v.getValue());
        }
        System.out.println();
    }

    public ArrayList<Vertex> DFS_Recursive(Vertex start) {
        ArrayList<Vertex> result = new ArrayList<>();
        HashMap<Vertex, Boolean> visited = new HashMap<>();
        for (Vertex v : adjacencyList.keySet()) {
            visited.put(v, false);
        }
        return DFS_Recursive_Utility(start, result, visited);
    }

    private ArrayList<Vertex> DFS_Recursive_Utility(Vertex vertex, ArrayList<Vertex> results, HashMap<Vertex, Boolean> visited) {
        if (vertex == null) {
            return null;
        }
        visited.put(vertex, true);
        results.add(vertex);
        for (Vertex v : adjacencyList.get(vertex)) {
            if (!visited.get(v)) {
                return DFS_Recursive_Utility(v, results, visited);
            }
        }
        return results;
    }
}

class Vertex<E> {

    private E value;

    public Vertex(E value) {
        this.value = value;
    }

    public E getValue() {
        return value;
    }
}

Основной класс 

public static void main(String[] args) {

    Vertex<String> a = new Vertex<>("A");
    Vertex<String> b = new Vertex<>("B");
    Vertex<String> c = new Vertex<>("C");
    Vertex<String> d = new Vertex<>("D");
    Vertex<String> e = new Vertex<>("E");
    Vertex<String> f = new Vertex<>("F");

    Graph graph = new Graph();
    graph.addVertex(a);
    graph.addVertex(b);
    graph.addVertex(c);
    graph.addVertex(d);
    graph.addVertex(e);
    graph.addVertex(f);
    graph.addEdge(a, b);
    graph.addEdge(a, c);
    graph.addEdge(b, d);
    graph.addEdge(c, e);
    graph.addEdge(d, e);
    graph.addEdge(d, f);
    graph.addEdge(e, f);
    System.out.println();
    for (Vertex v : graph.getAdjacencyList().keySet()) {
        graph.printAdjacencyList(v);
    }
    System.out.println();
    for (Vertex v : graph.DFS_Recursive(a)) {
        System.out.print(v.getValue() + " ");
    }
}

Результат вызова DFS_Recursive (): 

A B D E C

Я прошел через отладчик IntelliJ, и когда алгоритм достигает вершины C, в стеке все еще остаются вызовы, чтобы он мог проверить оставшиеся не посещенные вершины в списке смежности E. Однако в этот момент он просто возвращает результаты ArrayList, а остальные рекурсивные вызовы игнорируются.

Есть идеи, что происходит и как это исправить?

1 Ответ

2 голосов
/ 20 мая 2019

Насколько я понимаю, ваша реализация возвращается слишком рано, так что список заполненных вершин не заполняется правильно.Измените реализацию следующим образом. 

public ArrayList<Vertex> DFS_Recursive(Vertex start) {
    ArrayList<Vertex> result = new ArrayList<>();
    HashMap<Vertex, Boolean> visited = new HashMap<>();
    for (Vertex v : adjacencyList.keySet()) {
        visited.put(v, false);
    }
    DFS_Recursive_Utility(start, result, visited);
    return result;
}


private void DFS_Recursive_Utility(Vertex vertex,
                                   ArrayList<Vertex> results,
                                   HashMap<Vertex, Boolean> visited) {
        if (vertex == null) {
            return;
        }
        visited.put(vertex, true);
        results.add(vertex);
        for (Vertex v : adjacencyList.get(vertex)) {
            if (!visited.get(v)) {
            DFS_Recursive_Utility(v, results, visited);
        }
    }
}
...