Подтвердить что ты не робот

Внедрение BFS, DFS и Dijkstra

Верно ли, что реализация BFS, DFS и Dijkstra почти одинакова, за исключением того, что BFS использует очередь, DFS использует стек, а Dijkstra использует очередь с минимальным приоритетом?

Точнее. Можем ли мы использовать следующий код для всех BFS, DFS и Dijkstra, причем Q является очередью для BFS, а стек для DFS и мини-приоритетной очереди для Dijkstra? Спасибо!

Init d[]=Inf; // distance from the node s
Init c[]='w'; // color of nodes: 'w':undiscovered, 'g':discovered, 'b':fully explored
Init p[]=null; // previous node in the path
c[s]='g';
d[s]=0;
Q.push(s);
while(!Q.empty()) {
    u = Q.front();
    Q.pop();
    for v in adj[u] {
        if(c(v)=='w') {
            c[v]='g';
            if(d[u]+w(u,v)<d[v]) {
                d[v]=d[u]+w(u,v);
                p[v]=u;
            }
            Q.push(v);
        }
    }
    c[u]='b';
}
4b9b3361

ОТВЕТЫ

Ответ 1

Да

Скажем, у нас есть этот график и мы хотим найти кратчайшие расстояния, начинающиеся с A:

Graph

Вот простой интерфейс NodeCollection, который позволяет выполнять операции, необходимые для обхода:

interface NodeCollection<E> {
    void offer(E node);
    E extract();
    boolean isEmpty();
}

И реализации очереди очереди, стека и приоритета. Обратите внимание, что этот интерфейс и классы не обязательно должны быть общими:

static class NodeQueue<E> implements NodeCollection<E> {
    private final Queue<E> queue = new LinkedList<E>();
    @Override public void offer(E node) { queue.offer(node); }
    @Override public E extract() { return queue.poll(); }
    @Override public boolean isEmpty() { return queue.isEmpty(); }
}

static class NodeStack<E> implements NodeCollection<E> {
    private final Stack<E> stack = new Stack<E>();
    @Override public void offer(E node) { stack.push(node); }
    @Override public E extract() { return stack.pop(); }
    @Override public boolean isEmpty() { return stack.isEmpty(); }
}

static class NodePriorityQueue<E> implements NodeCollection<E> {
    private final PriorityQueue<E> pq = new PriorityQueue<E>();
    @Override public void offer(E node) { pq.add(node); }
    @Override public E extract() { return pq.poll(); }
    @Override public boolean isEmpty() { return pq.isEmpty(); }
}

Обратите внимание, что для PriorityQueue для работы, как ожидалось, класс Node должен предоставить метод compareTo(Node):

static class Node implements Comparable<Node> {
    final String name;
    Map<Node, Integer> neighbors;
    int dist = Integer.MAX_VALUE;
    Node prev = null;
    char color = 'w';

    Node(String name) {
        this.name = name;
        this.neighbors = Maps.newHashMap();
    }

    @Override public int compareTo(Node o) {
        return ComparisonChain.start().compare(this.dist, o.dist).result();
    }
}

Теперь вот класс Graph. Обратите внимание, что метод traverse принимает экземпляр NodeCollection, который будет использоваться для хранения узлов во время обхода.

static class Graph {
    Map<String, Node> nodes = Maps.newHashMap();

    void addEdge(String fromName, String toName, int weight) {
        Node from = getOrCreate(fromName);
        Node to = getOrCreate(toName);
        from.neighbors.put(to, weight);
        to.neighbors.put(from, weight);
    }

    Node getOrCreate(String name) {
        if (!nodes.containsKey(name)) {
            nodes.put(name, new Node(name));
        }
        return nodes.get(name);
    }

    /**
     * Traverses this graph starting at the given node and returns a map of shortest paths from the start node to
     * every node.
     *
     * @param startName start node
     * @return shortest path for each node in the graph
     */
    public Map<String, Integer> traverse(String startName, NodeCollection<Node> collection) {
        assert collection.isEmpty();
        resetNodes();

        Node start = getOrCreate(startName);
        start.dist = 0;
        collection.offer(start);

        while (!collection.isEmpty()) {
            Node curr = collection.extract();
            curr.color = 'g';
            for (Node neighbor : curr.neighbors.keySet()) {
                if (neighbor.color == 'w') {
                    int thisPathDistance = curr.dist + curr.neighbors.get(neighbor);
                    if (thisPathDistance < neighbor.dist) {
                        neighbor.dist = thisPathDistance;
                        neighbor.prev = curr;
                    }
                    collection.offer(neighbor);
                }
            }
            curr.color = 'b';
        }

        Map<String, Integer> shortestDists = Maps.newTreeMap();
        for (Node node : nodes.values()) {
            shortestDists.put(node.name, node.dist);
        }
        return shortestDists;
    }

    private void resetNodes() {
        for (Node node : nodes.values()) {
            node.dist = Integer.MAX_VALUE;
            node.prev = null;
            node.color = 'w';
        }
    }
}

Наконец, здесь используется метод main, который трижды обходит один и тот же граф один раз с каждым из типов NodeCollection:

private static Graph initGraph() {
    Graph graph = new Graph();
    graph.addEdge("A", "B", 2);
    graph.addEdge("B", "C", 2);
    graph.addEdge("C", "D", 2);
    graph.addEdge("D", "E", 2);
    graph.addEdge("E", "F", 2);
    graph.addEdge("F", "L", 2);

    graph.addEdge("A", "G", 10);
    graph.addEdge("G", "H", 10);
    graph.addEdge("H", "I", 10);
    graph.addEdge("I", "J", 10);
    graph.addEdge("J", "K", 10);
    graph.addEdge("K", "L", 10);

    return graph;
}

public static void main(String[] args) {
    Graph graph = initGraph();
    System.out.println("Queue (BFS):\n" + graph.traverse("A", new NodeQueue<Node>()));
    System.out.println("Stack (DFS):\n" + graph.traverse("A", new NodeStack<Node>()));
    System.out.println("PriorityQueue (Dijkstra):\n" + graph.traverse("A", new NodePriorityQueue<Node>()));
}

И результаты!

Queue (BFS):
{A=0, B=2, C=4, D=6, E=8, F=10, G=10, H=20, I=30, J=40, K=22, L=12}
Stack (DFS):
{A=0, B=2, C=4, D=66, E=64, F=62, G=10, H=20, I=30, J=40, K=50, L=60}
PriorityQueue (Dijkstra):
{A=0, B=2, C=4, D=6, E=8, F=10, G=10, H=20, I=30, J=32, K=22, L=12}

Обратите внимание, что DFS иногда принимает верхнюю ветвь сначала, получая разные, но симметричные результаты.

Вот какие результаты будут выглядеть на графике:

Results

Ответ 2

По вопросу BFS против DFS: да и нет, но больше "нет", чем "да".

Если все, о чем вы заботитесь, это порядок прямого обхода, то есть порядок, в котором алгоритм обнаруживает новые вершины графа, тогда да: вы можете взять классический алгоритм BFS, заменить очередь FIFO на стек LIFO, а вы получит алгоритм псевдо-DFS.

Однако я называю его псевдо-DFS-алгоритмом, потому что он не совсем то же самое, что классический DFS.

Алгоритм DFS, полученный таким образом, действительно будет генерировать подлинный порядок обнаружения вершин DFS. Тем не менее, он все равно будет отличаться от классического DFS в некоторых других regadrs. Вы можете найти описание классического DFS в любой книге по алгоритмам (или Wikipedia), и вы увидите, что структура алгоритма заметно отличается от структуры BFS. Это делается по какой-то причине. Классический DFS предлагает некоторые дополнительные преимущества, помимо создания правильного порядка обнаружения вершин DFS. Эти дополнительные преимущества включают

  • Снижение потребления пиковой памяти.. В классической реализации DFS размер стека в каждый момент времени равен длине пути от начала поиска до текущей вершины. В псевдо-DFS размер стека в каждый момент времени равен сумме степеней всех вершин от начала поиска до текущей вершины. Это означает, что потребление пиковой памяти псевдо-DFS-алгоритма будет потенциально значительно выше.

    В качестве крайнего примера рассмотрим граф "снежинки", состоящий из одной вершины в центре, непосредственно связанной с 1000 вершинами, окружающими ее. Классический DFS будет пересекать этот график с максимальной глубиной стека 1. Между тем, псевдо-DFS начнется, нажав все 1000 вершин в стек (в режиме BFS), что приведет к максимальной глубине стека 1000. Это довольно большая разница.

  • Откат. Классический алгоритм DFS - это подлинный рекурсивный алгоритм. В качестве рекурсивного алгоритма в дополнение к порядку прямого обхода (то есть порядку обнаружения вершин), он также предоставляет вам обратный порядок обхода (обратный поиск). В классическом DFS вы посещаете каждую вершину несколько раз: первый раз, когда вы открываете ее в первый раз, тогда, когда вы возвращаетесь назад из одной из своих вершин-потомков, чтобы перейти к следующей вершине потомка и, наконец, в последний раз, когда вы обработали всех своих потомков. Многие алгоритмы, основанные на DFS, основаны на поиске и обработке этих посещений. Например, топологический алгоритм сортировки является классическим DFS, который выводит вершины в порядке их последнего посещения DFS. Алгоритм псевдо-DFS, как я сказал выше, предоставляет только ясный доступ к первому событию (обнаружение вершин), но не регистрирует события возврата.

Ответ 3

Да, это правда. Много полезных алгоритмов имеют похожие шаблоны. Например, для собственных векторов графа, алгоритм Итерации мощности, если вы измените начальный вектор и вектор ортогонализации, вы получите целое семейство полезных, но связанных алгоритмов. В этом случае он называется проекцией ABS.

В этом случае все они построены на примитиве "инкрементное добавление" -to-a-tree. Именно так, как мы выбираем, что ребро/вершина для добавления определяет тип дерева и, следовательно, тип навигации.