graph-algorithm - 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):

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

以及队列、堆栈和优先级队列的实现。请注意，此接口(interface)和类并不需要是通用的:

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类(class)。请注意 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 有时会先采用顶部分支，从而产生不同但对称的结果。

以下是图表上的结果: