实施BFS,DFS和Dijkstra

Question

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

Answer 1

是

假设我们有这个图表,并希望找到最短距离,从A:

这是一个简单的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方法,它遍历同一个图3次,每种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有时会首先采用顶部分支,从而产生不同但对称的结果.

以下是图表上的结果:

Answer 2

是的，这是真的。许多有用的算法都有类似的模式。例如，对于图特征向量、幂迭代算法，如果更改起始向量和正交化向量，您将获得一整套有用但相关的算法。在这种情况下，它称为 ABS 投影。

在这种情况下，它们都构建在树原语的“增量添加”之上。我们选择要添加的边/顶点的方式决定了树的类型，从而决定了导航的类型。