笔试和面试中，常用的图算法除了深度优先搜索、广度优先搜索，还有如下五种：

• 单源最短路径的（堆优化）Dijkstra 算法
• 多源最短路径的 Floyd-Warshall 算法
• 最小生成树的 Kruskal 算法
• 最小生成树的 Prim 算法
• 拓扑排序的 Kahn 算法

下面分别给出算法原理简析和代码实现。

堆优化的 Dijkstra 算法

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // A -> B 2
        // A -> C 6
        // B -> C 3
        Map<Character, Map<Character, Integer>> graph = new HashMap<>();
        graph.put('A', new HashMap<>());
        graph.get('A').put('B', 2);
        graph.get('A').put('C', 6);
        graph.put('B', new HashMap<>());
        graph.get('B').put('C', 3);
        graph.put('C', new HashMap<>());
        Map<Character, Integer> res = heapDijkstra(graph, 'A');
        for (char c : res.keySet()) {
            System.out.println("from A to " + c + ": " + res.get(c));
        }
    }

    private static Map<Character, Integer> heapDijkstra(Map<Character, Map<Character, Integer>> graph, char src) {
        Map<Character, Integer> distances = new HashMap<>();
        PriorityQueue<Map.Entry<Character, Integer>> pq = new PriorityQueue<>(Comparator.comparingInt(Map.Entry::getValue));
        distances.put(src, 0);
        pq.add(new AbstractMap.SimpleEntry<>(src, 0));
        while (!pq.isEmpty()) {
            Map.Entry<Character, Integer> entry = pq.poll();
            char vertex = entry.getKey();
            int distance = entry.getValue();
            if (distances.get(vertex) < distance) continue;
            Map<Character, Integer> neighbors = graph.get(vertex);
            for (char neighbor : neighbors.keySet()) {
                int newDistance = distance + neighbors.get(neighbor);
                if (!distances.containsKey(neighbor) || newDistance < distances.get(neighbor)) {
                    distances.put(neighbor, newDistance);
                    pq.add(new AbstractMap.SimpleEntry<>(neighbor, newDistance));
                }
            }
        }
        return distances;
    }
}

为快速求出当前最小的距离，使用堆。这里避免了堆的 remove 操作，堆中可能有已过时的数据，每次弹出堆的根，要进行额外判断。从堆中弹出的顶点 + 距离，只要不过时，可以证明，就是起点到该顶点的最短路径长度。

Floyd-Warshall 算法

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Map<Character, Map<Character, Integer>> graph = new HashMap<>();
        graph.put('A', new HashMap<>());
        graph.get('A').put('B', 1);
        graph.get('A').put('D', 3);
        graph.put('B', new HashMap<>());
        graph.get('B').put('C', 1);
        graph.get('B').put('D', 2);
        graph.put('C', new HashMap<>());
        graph.get('C').put('A', 2);
        graph.get('C').put('D', 4);
        graph.put('D', new HashMap<>());
        floydWarshall(graph);
    }

    private static void floydWarshall(Map<Character, Map<Character, Integer>> graph) {
        Map<Character, Integer> map = new HashMap<>();
        int n = 0;
        for (char c : graph.keySet()) {
            map.put(c, n++);
        }
        int[][] distances = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(distances[i], Integer.MAX_VALUE);
            distances[i][i] = 0;
        }
        for (char c : graph.keySet()) {
            for (char c2 : graph.get(c).keySet()) {
                distances[map.get(c)][map.get(c2)] = graph.get(c).get(c2);
            }
        }
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                if (distances[i][k] == Integer.MAX_VALUE) continue;
                for (int j = 0; j < n; j++) {
                    if (distances[k][j] == Integer.MAX_VALUE) continue;
                    distances[i][j] = Math.min(distances[i][j], distances[i][k] + distances[k][j]);
                }
            }
        }
        System.out.print(" ");
        for (char c : graph.keySet()) {
            System.out.print(" " + c);
        }
        System.out.println();
        for (char c : graph.keySet()) {
            System.out.print(c);
            for (char c2 : graph.keySet()) {
                int d = distances[map.get(c)][map.get(c2)];
                System.out.print(" " + (d == Integer.MAX_VALUE ? "X" : d));
            }
            System.out.println();
        }
    }
}

输入的图最好是邻接矩阵的形式。否则需要设置从顶点到数组下标的映射。

Kruskal 算法

最小生成树问题仅针对无向图。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Map<Character, Map<Character, Integer>> graph = new HashMap<>();
        graph.put('A', new HashMap<>());
        graph.get('A').put('B', 1);
        graph.get('A').put('C', 2);
        graph.get('A').put('D', 3);
        graph.put('B', new HashMap<>());
        graph.get('B').put('A', 1);
        graph.get('B').put('C', 4);
        graph.get('B').put('D', 5);
        graph.put('C', new HashMap<>());
        graph.get('C').put('A', 2);
        graph.get('C').put('B', 4);
        graph.get('C').put('D', 6);
        graph.put('D', new HashMap<>());
        graph.get('D').put('A', 3);
        graph.get('D').put('B', 5);
        graph.get('D').put('C', 6);
        Set<Edge> res = kruskal(graph);
        for (Edge e : res) {
            System.out.println(e);
        }
    }

    private static class Edge {
        char u;
        char v;
        int weight;

        public Edge(char u, char v, int weight) {
            this.u = u;
            this.v = v;
            this.weight = weight;
        }

        @Override
        public String toString() {
            return "(" + u + "-" + v + ", " + weight + ")";
        }
    }

    private static class UnionFind {
        Map<Character, Character> parents = new HashMap<>();

        public UnionFind(Set<Character> vertices) {
            for (char c : vertices) {
                parents.put(c, c);
            }
        }

        public char find(char u) {
            if (parents.get(u) != u) {
                parents.put(u, find(parents.get(u)));
            }
            return parents.get(u);
        }

        public void union(char u, char v) {
            char rootU = find(u);
            char rootV = find(v);
            if (rootU != rootV) {
                parents.put(rootU, rootV);
            }
        }
    }

    private static Set<Edge> kruskal(Map<Character, Map<Character, Integer>> graph) {
        PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparingInt(e -> e.weight));
        for (char c : graph.keySet()) {
            Map<Character, Integer> graph2 = graph.get(c);
            for (char c2 : graph2.keySet()) {
                if (c < c2) pq.offer(new Edge(c, c2, graph2.get(c2)));
            }
        }
        Set<Edge> mst = new HashSet<>();
        UnionFind uf = new UnionFind(graph.keySet());
        while (!pq.isEmpty()) {
            Edge e = pq.poll();
            if (uf.find(e.u) != uf.find(e.v)) {
                uf.union(e.u, e.v);
                mst.add(e);
                if (mst.size() == graph.keySet().size() - 1) break;
            }
        }
        if (mst.size() < graph.keySet().size() - 1) System.out.println("The graph is not connected!");
        return mst;
    }
}

• 提取所有边并去重（通过比较顶点大小避免重复）

• 按权重排序边后，使用并查集动态检测环，选择不形成环的最小边

Prim 算法

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Map<Character, Map<Character, Integer>> graph = new HashMap<>();
        graph.put('A', new HashMap<>());
        graph.get('A').put('B', 1);
        graph.get('A').put('C', 2);
        graph.get('A').put('D', 3);
        graph.put('B', new HashMap<>());
        graph.get('B').put('A', 1);
        graph.get('B').put('C', 4);
        graph.get('B').put('D', 5);
        graph.put('C', new HashMap<>());
        graph.get('C').put('A', 2);
        graph.get('C').put('B', 4);
        graph.get('C').put('D', 6);
        graph.put('D', new HashMap<>());
        graph.get('D').put('A', 3);
        graph.get('D').put('B', 5);
        graph.get('D').put('C', 6);
        Set<Edge> res = prim(graph);
        for (Edge e : res) {
            System.out.println(e);
        }
    }

    private static class Edge {
        char u;
        char v;
        int weight;

        public Edge(char u, char v, int weight) {
            this.u = u;
            this.v = v;
            this.weight = weight;
        }

        @Override
        public String toString() {
            return "(" + u + "-" + v + ", " + weight + ")";
        }
    }

    private static Set<Edge> prim(Map<Character, Map<Character, Integer>> graph) {
        Set<Character> visited = new HashSet<>();
        char start = graph.keySet().iterator().next();
        visited.add(start);
        PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparingInt(e -> e.weight));
        for (char v : graph.get(start).keySet()) {
            pq.add(new Edge(start, v, graph.get(start).get(v)));
        }
        Set<Edge> mst = new HashSet<>();
        while (!pq.isEmpty() && visited.size() < graph.keySet().size()) {
            Edge e = pq.poll();
            if (visited.contains(e.v)) break;
            mst.add(e);
            visited.add(e.v);
            for (char v : graph.get(e.v).keySet()) {
                if (!visited.contains(v)) {
                    pq.add(new Edge(e.v, v, graph.get(e.v).get(v)));
                }
            }
        }
        if (mst.size() < graph.keySet().size() - 1) System.out.println("The graph is not connected!");
        return mst;
    }
}

• 从任意顶点出发，维护优先队列存储连接已选/未选顶点的边

• 每次选择最小边并扩展已选顶点集合，直到覆盖所有顶点

Kahn 算法

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Map<Character, Set<Character>> graph = new HashMap<>();
        graph.put('A', Set.of('C', 'D'));
        graph.put('B', Set.of('D', 'E'));
        graph.put('C', Set.of('F'));
        graph.put('D', Set.of('G', 'H'));
        graph.put('E', Set.of('I'));
        graph.put('F', new HashSet<>());
        graph.put('G', new HashSet<>());
        graph.put('H', new HashSet<>());
        graph.put('I', new HashSet<>());
        List<Character> res = kahn(graph);
        for (char c : res) {
            System.out.print(c + " ");
        }
    }

    private static List<Character> kahn(Map<Character, Set<Character>> graph) {
        Map<Character, Integer> inDegree = new HashMap<>();
        for (char c : graph.keySet()) {
            inDegree.put(c, 0);
        }
        for (char c : graph.keySet()) {
            for (char cc : graph.get(c)) {
                inDegree.put(cc, inDegree.get(cc) + 1);
            }
        }
        List<Character> res = new ArrayList<>();
        Queue<Character> queue = new LinkedList<>();
        for (char c : graph.keySet()) {
            if (inDegree.get(c) == 0) {
                queue.add(c);
            }
        }
        while (!queue.isEmpty()) {
            char c = queue.poll();
            for (char cc : graph.get(c)) {
                inDegree.put(cc, inDegree.get(cc) - 1);
                if (inDegree.get(cc) == 0) {
                    queue.add(cc);
                }
            }
            res.add(c);
        }
        if (res.size() < graph.keySet().size()) System.out.println("The graph is cyclic!");
        return res;
    }
}

用一个哈希表记录顶点的入度，每次选取入度为 0 的顶点放入队列中。