“This is my 39th day of participating in the First Challenge 2022. For more details: First Challenge 2022.”

Minimum spanning tree algorithm Kruskal

1, analysis,

The so-called minimum spanning tree is the minimum value of the sum of all edges without affecting the connectivity of all nodes

Look at all edges, from smallest to largest (greedy), if the current edge does not form a ring, take this edge, if the current edge does form a ring, leave this edge

And search sets go up: join in turn, merge in turn

And look up the set and skip the process, will not look up the set chapter

2, implementation,

// Union-Find Set
public static class UnionFind {
    // key Specifies the node above the value key node
    private HashMap<Node, Node> fatherMap;
    // key Specifies the number of nodes in a set. Value Specifies the number of nodes in the set
    private HashMap<Node, Integer> sizeMap;

    public UnionFind(a) {
        fatherMap = new HashMap<>();
        sizeMap = new HashMap<>();
    }

    public void makeSets(Collection<Node> nodes) {
        fatherMap.clear();
        sizeMap.clear();
        for (Node node : nodes) {
            fatherMap.put(node, node);
            sizeMap.put(node, 1); }}private Node findFather(Node n) {
        Stack<Node> path = new Stack<>();
        while(n ! = fatherMap.get(n)) { path.add(n); n = fatherMap.get(n); }while(! path.isEmpty()) { fatherMap.put(path.pop(), n); }return n;
    }

    public boolean isSameSet(Node a, Node b) {
        return findFather(a) == findFather(b);
    }

    public void union(Node a, Node b) {
        if (a == null || b == null) {
            return;
        }
        Node aDai = findFather(a);
        Node bDai = findFather(b);
        if(aDai ! = bDai) {int aSetSize = sizeMap.get(aDai);
            int bSetSize = sizeMap.get(bDai);
            if (aSetSize <= bSetSize) {
                fatherMap.put(aDai, bDai);
                sizeMap.put(bDai, aSetSize + bSetSize);
                sizeMap.remove(aDai);
            } else{ fatherMap.put(bDai, aDai); sizeMap.put(aDai, aSetSize + bSetSize); sizeMap.remove(bDai); }}}}public static class EdgeComparator implements Comparator<Edge> {

    @Override
    public int compare(Edge o1, Edge o2) {
        returno1.weight - o2.weight; }}public static Set<Edge> kruskalMST(Graph graph) {
    UnionFind unionFind = new UnionFind();
    unionFind.makeSets(graph.nodes.values());
    // From small edge to big edge, pop up one by one, small root heap!
    PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(new EdgeComparator());
    for (Edge edge : graph.edges) { / / M side
        priorityQueue.add(edge);  // O(logM)
    }
    Set<Edge> result = new HashSet<>();
    while(! priorityQueue.isEmpty()) {/ / M side
        Edge edge = priorityQueue.poll(); // O(logM)
        if(! unionFind.isSameSet(edge.from, edge.to)) {// O(1)result.add(edge); unionFind.union(edge.from, edge.to); }}return result;
}
Copy the code

Prim of minimum spanning tree algorithm

1, analysis,

Select a point and unlock it again

Point -> edge -> point -> edge…

2, implementation,

public static class EdgeComparator implements Comparator<Edge> {
    @Override
    public int compare(Edge o1, Edge o2) {
        returno1.weight - o2.weight; }}public static Set<Edge> primMST(Graph graph) {
    // The unlocked edge goes into the small root heap
    PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(new EdgeComparator());
    // Which points are unlocked
    HashSet<Node> nodeSet = new HashSet<>();
    Set<Edge> result = new HashSet<>(); // The selected edges are in result
    for (Node node : graph.nodes.values()) { // Pick a point at random
        // Node is the starting point
        if(! nodeSet.contains(node)) { nodeSet.add(node);for (Edge edge : node.edges) { // Unlock all connected edges with a single point
                priorityQueue.add(edge);
            }
            while(! priorityQueue.isEmpty()) { Edge edge = priorityQueue.poll();// Eject the smallest edge of the unlocked edge
                Node toNode = edge.to; // A possible new point
                if(! nodeSet.contains(toNode)) {// If it does not, it is a new point
                    nodeSet.add(toNode);
                    result.add(edge);
                    for(Edge nextEdge : toNode.edges) { priorityQueue.add(nextEdge); }}}}// break; To prevent the forest
    }
    return result;
}
Copy the code

Third, summary

Minimum spanning trees are all undirected graphs

Minimum spanning Tree Algorithm Kruskal:

1. Always start with the edge with the lowest weight and look at the edge with the highest weight
2. The current edge either enters the minimum spanning tree set or is discarded
3. If the current edge goes into the minimum spanning tree without forming a ring, the current edge is used
4. Discard the current edge if it would form a loop if entered into the minimum spanning tree
5. After looking at all the edges, we get the set of minimum spanning trees

Minimum spanning tree algorithm Prim:

1. You can start at any node to find a minimum spanning tree
2. After a point is added to the selected point, it unlocks all new edges starting from that point
3. Pick the smallest edge of all the unlocked edges and see if that edge forms a ring
4. If so, leave the current edge and proceed to the smallest edge of the remaining unlocked edge. Repeat 3
5. If not, take the current edge and add the edge’s point to the selected point, repeat 2
6. When all points are selected, the minimum spanning tree is obtained