算法-图的最小生成树和最短路径

Java 表示图的经典模板，下文以此结构为例

图

public class Graph {
    /**
     * 序号和点 map
     */
    public HashMap<Integer, Node> nodes = new HashMap<>();

    /**
     * 边集
     */
    public HashSet<Edge> edges = new HashSet<>();

}

顶点

public class Node {

    public int value;
    /**
     * 入度
     */
    public int in = 0;
    /**
     * 出度
     */
    public int out = 0;

    public ArrayList<Node> nexts = new ArrayList<>();
    public ArrayList<Edge> edges = new ArrayList<>();

    public Node(int value) {
        this.value = value;
    }
}

边

public class Edge {
    public int weight;

    /**
     * 起点
     */
    public Node from;

    /**
     * 终点
     */
    public Node to;

    public Edge(int weight, Node from, Node to) {
        this.weight = weight;
        this.from = from;
        this.to = to;
    }
}

拓扑排序

假设有向图描述了一种节点间依赖关系，拓扑排序是按照这种关系进行节点排序的算法

在软件开发工程中，经常会使用各种依赖，这些依赖的加载或编译顺序，是通过拓扑排序得到的

示例为拓扑排序算法，先维护所有点入度，并获取所有入度为 0 的点放入队列进行遍历，，进行宽度优先搜索，每次消费掉一个入度为 0 的点，将其 next 节点的入度 - 1，并判断是否为 0，为 0 则加入队列

要求：

• 有向图
• 有入度为 0 的节点
• 没有环

public static List<Node> topologicalSort(Graph graph) {
    // 入度 map
    HashMap<Node, Integer> inMap = new HashMap<>();
    // 处理队列
    Queue<Node> zeroInQueue = new LinkedList<>();
    for (Node node : graph.nodes.values()) {
        inMap.put(node, node.in);
        // 找到入度为 0
        if (node.in == 0) {
            zeroInQueue.offer(node);
        }
    }
    List<Node> resList = new ArrayList<>();
    while (!zeroInQueue.isEmpty()) {
        Node node = zeroInQueue.poll();
        resList.add(node);
        for (Node next : node.nexts) {
            // 消除当前节点对入度的影响
            inMap.put(next, inMap.get(next) - 1);
            if (inMap.get(next) == 0) {
                zeroInQueue.offer(next);
            }
        }
    }
    return resList;
}

最小生成树

最小生成树，也叫最小连通树，是在图中满足各顶点相通的最小边集（总权值最小）

Kruskal 算法

也叫 K 算法，对图的整个边集进行从从小到大遍历，每次加上一个边，并考察该边是否会形成环，如果会则不加该边

要求：无向图

/**
 * K 算法 最小生成树
 * 要求无向图
 * 原理：每次选最短的边，判断该边会不会成环，会成环则不取该边
 * 判断会不会成环，使用 MySet 工具类
 */
public static Set<Edge> kruskalMST(Graph graph) {
    // 查询合并工具
    MySet mySet = new MySet(new ArrayList<>(graph.nodes.values()));
    // 小顶堆，取最小边
    PriorityQueue<Edge> minHeap = new PriorityQueue<>(Comparator.comparing(o -> o.weight));
    for (Edge edge : graph.edges) {
        minHeap.offer(edge);
    }
    HashSet<Edge> resSet = new HashSet<>();
    while (!minHeap.isEmpty()) {
        Edge edge = minHeap.poll();
        Node from = edge.from;
        Node to = edge.to;
        if (!mySet.isSameSet(from, to)) {
            resSet.add(edge);
            mySet.union(from, to);
        }
    }
    return resSet;
}

public static class MySet {

    HashMap<Node, List<Node>> map = new HashMap<>();

    public MySet(List<Node> list) {
        // 开始，每个节点在各自的 set 中
        for (Node node : list) {
            List<Node> set = new ArrayList<>();
            set.add(node);
            map.put(node, set);
        }
    }

    /**
     * 是否在一个集合
     */
    public boolean isSameSet(Node node1, Node node2) {
        return map.get(node1) == map.get(node2);
    }

    /**
     * 合并到一个集合
     */
    public void union(Node node1, Node node2) {
        List<Node> set1 = map.get(node1);
        List<Node> set2 = map.get(node2);

        for (Node node : set2) {
            set1.add(node);
            map.put(node, set1);
        }
    }

}

Prim 算法

也叫 P 算法，选择一个点 node，通过维护小顶堆，每次获取最小的边，并将当前边的 to 点的边加入堆

要求：无向图

/**
 * P 算法 最小生成树
 * 原理：选择一个点，维护一个小顶堆，加入该点的边，遍历小顶堆来获取最小的边，每次将当前最小边的结束点的边加入小顶堆
 * 要求无向图
 */
public static Set<Edge> primMST(Graph graph) {
    HashSet<Edge> resSet = new HashSet<>();
    // 防止重复处理
    HashSet<Node> cache = new HashSet<>();

    PriorityQueue<Edge> minHeap = new PriorityQueue<>(Comparator.comparing(o -> o.weight));

    // 此 for 循环只是随便挑取一个点
    // 仅仅防止图中存在孤岛，在整个图连通时没有实际作用
    for (Node node : graph.nodes.values()) {
        if (cache.contains(node)) {
            continue;
        }
        cache.add(node);
        for (Edge edge : node.edges) {
            minHeap.offer(edge);
        }
        while (!minHeap.isEmpty()) {
            Edge edge = minHeap.poll();
            Node toNode = edge.to;
            if (!cache.contains(toNode)) {
                cache.add(toNode);
                resSet.add(edge);
                for (Edge toEdge : toNode.edges) {
                    minHeap.offer(toEdge);
                }
            }
        }
    }

    return resSet;
}

最短路径

dijkstra 算法

也叫迪杰特斯拉算法，以点 head 开始，维护一个 head 到各点的距离哈希表，每次获取没有被处理过且距离最小的点 minNode，通过遍历 minNode 边集，得到 minNode 到其 to 点的距离，和已经维护的距离比较并更新

要求：不能有权值累加为负数的环

/**
 * dijkstra 算法
 * 要求不能有权值累加和为负数的环
 */
public static Map<Node, Integer> dijkstra(Node head) {
    // 从 head 到其他所有节点 key 的距离 val
    // 不在 map 中则到该节点还没有路，或者说距离为正无穷
    Map<Node, Integer> distanceMap = new HashMap<>();
    // head 自己到自己距离为 0
    distanceMap.put(head, 0);
    // 已经处理的点
    Set<Node> selectedNodes = new HashSet<>();
    // 选一个没有处理过、距离最小的点，此时应该就是 head
    Node minNode = getMinDistanceNode(distanceMap, selectedNodes);
    while (minNode != null) {
        Integer distance = distanceMap.get(minNode);
        for (Edge edge : minNode.edges) {
            Node toNode = edge.to;
            if (distanceMap.containsKey(toNode)) {
                // 比较之前发现的最小路径
                distanceMap.put(toNode, Math.min(distanceMap.get(toNode), distance + edge.weight));
            } else {
                // 没有该 key，说明到该节点还没有路
                distanceMap.put(toNode, distance + edge.weight);
            }
        }
        selectedNodes.add(minNode);
        minNode = getMinDistanceNode(distanceMap, selectedNodes);
    }
    return distanceMap;
}

/**
 * 找到没处理过的、距离最小的点
 */
private static Node getMinDistanceNode(Map<Node, Integer> distanceMap, Set<Node> selectedNodes) {
    Node minNode = null;
    int minDistance = Integer.MAX_VALUE;
    for (Entry<Node, Integer> entry : distanceMap.entrySet()) {
        if (!selectedNodes.contains(entry.getKey()) && entry.getValue() < minDistance) {
            minNode = entry.getKey();
            minDistance = entry.getValue();
        }
    }
    return minNode;
}