Hello, I am Xiao Huang, a Java development engineer of Unicorn Enterprise. Thank you for meeting us in the vast sea of people. As the saying goes: When your talent and ability are not enough to support your dream, please calm down and study. I hope you can study with me and work hard together to realize your own dream.

One, the introduction

Dove a week I came back……..

Xiao Huang went to her birthday

Let me show you the birthday cake

Have you ever encountered this kind of thing in your life

Your county needs to build roads between several communities. Due to the shortage of government funds, it is impossible to build roads between all communities. Instead, a road that can connect all communities can be built with the least amount of funds

As shown below:Of course, the above is just an abstract example, but in our real life, the distance between each community is also different. How can we use the minimum capital to connect all communities?

This brings us to our big brothers today: Kruskal and Prim algorithms

These two algorithms generate minimum spanning trees from edge and point respectively to ensure the minimization of funds

In this article, we will approach The Kruskal algorithm and explore how the algorithm determines the minimum spanning tree by edge

Of course, some of you might be wondering, why don’t you tell me the Prim algorithm once and for all, and I’ll tell you the answer at the end

What is The Kruskal algorithm

Kruskal algorithm is a method to find the minimum spanning tree of connected networks. Different from Prim algorithm, its time complexity is O(ELOGE) (e is the number of edges in the network), so it is suitable for finding the minimum spanning tree with sparse edges.

Because our Kruskal algorithm takes edge as the unit, we need to find the minimum spanning tree of some edge sparseness, which has a relatively small time complexity

Let’s take the following neighborhood as an exampleKruskalThe algorithm will give us a shortest path to connect all the cells

Three, the essence of Kruskal algorithm

For Kruskal algorithm, the whole use of greedy + and look up the set idea

Have not familiar with and check the collection of children’s shoes can take a look at this article:Learn and look up sets in three minutes

In simple terms, we need to put all edges into a heap, sorted by edge size, as follows: 1, 2, 3, 6, 7, 10, 12

  • Let’s take the first side1Take out,C district 和 D villageMerge, present collection:{C, D}

  • Let’s take the second side2Take out,A neighborhood 和 E villageMerge, present collection:{C, D}.{A, E}

  • Let’s take the third side3Take out,A neighborhood 和 B cellMerge, present collection:{C, D}.{A, B, E}

  • Take the fourth side6Take out,A neighborhood 和 D villageMerge, present collection:{A, B, E, C, D}

  • Take the fifth edge7Take out,B cell 和 E villageMerge, as a result of{A, B, E, C, D}In a set, the edge is skipped without merging
  • Take the sixth side10Take out,B cell 和 C districtMerge, as a result of{A, B, E, C, D}In a set, the edge is skipped without merging
  • And so on…….

And we end up with a path, which is our minimum spanning tree

According to the figure, our minimum capital need is 12

Realization of Kruskal algorithm

For The Kruskal algorithm, we need to implement two parts

  • Check and set
  • greedy

1. And check the set

Here simply put down and check the set of two key steps, the rest of the source code can be concerned about love knock code yellow public number, reply: algorithm source code can be obtained algorithm source

Merger:

	/ / merge
    public void union(Node node1, Node node2) {
        // Find the parent of both nodes
        Node node1Parent = getParentNode(node1);
        Node node2Parent = getParentNode(node2);
        // See if you are a father
        if(node1Parent ! = node2Parent) {// Number of parent nodes for node1 and node2
            int size1 = size.get(node1Parent);
            int size2 = size.get(node2Parent);
            // If the number of nodes is greater, the number of nodes will be merged
            if (size1 >= size2) {
                parent.put(node1Parent, node2Parent);
                size.put(node1Parent, size1 + size2);
                size.remove(node2Parent);
            } else{ parent.put(node2Parent, node1Parent); size.put(node2Parent, size1 + size2); size.remove(node2Parent); }}}Copy the code

Query:

	public boolean isSame(Node node1, Node node2) {
        return getParentNode(node1) == getParentNode(node2);
    }

    public Node getParentNode(Node node) {
        // For path compression
        Stack<Node> stack = new Stack<>();
        while(parent.get(node) ! = node) { stack.add(node); node = parent.get(node); }while(! stack.isEmpty()) { parent.put(stack.pop(), node); }return node;
    }
Copy the code

2. Kruskal algorithm

And check the initialization of the set:

	// Assign an initial value
    public void makeSets(Collection<Node> list) {
        for (Node node : list) {
        	// The parent of each node is itself, and the number of sets is 1
            parent.put(node, node);
            size.put(node, 1); }}Copy the code

Comparator (sort by edge weight) :

 	public static class EdgeComparator implements Comparator<Edge> {

        @Override
        public int compare(Edge o1, Edge o2) {
            returno1.weight - o2.weight; }}Copy the code

Kruskal algorithm:

	public static Set<Edge> kruskalMST(Graph graph) {
        Union union = new Union();
        // Initialize and look up the set
        union.makeSets(graph.nodes.values());
		// Build heap, sort by edge weight
        PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(new EdgeComparator());
        / / in the side
        for (Edge edge : graph.edges) {
            priorityQueue.add(edge);
        }
        Set<Edge> edges = new HashSet<>();
        // Start with the smallest
        while(! priorityQueue.isEmpty()) { Edge edge = priorityQueue.poll();// check to see if it is a set
            if(! union.isSame(edge.from, edge.to)) {// You can take this edge and merge the two pointsedges.add(edge); union.union(edge.from, edge.to); }}return edges;
    }
Copy the code

The description of the above figure uses the graphical description: the graphical description of the figure

Five, the summary

Through the above description, we can solve the problem we mentioned at the beginning: your county needs to build roads between several communities. Due to the shortage of government funds, it is impossible to build roads between all communities, but to build a road that can connect all communities with the least amount of funds

At the same time, the code for Kruskal also needs to be written several times. When the blogger wrote this blog, he forgot how to write it (escape

  • 1584. Minimum cost for connecting all points

Interested in the source code of small partners, you can pay attention to love knocking code yellow public number, reply: algorithm source code can be obtained algorithm source

To answer the initial question: Some of you might be wondering, why don’t you just cover Prim once and for all

Answer: next period speak Prim, can water a period (escape

That’s it for this installment, and next time we’ll talk about Prim

I am a unicorn enterprise Java development engineer, hope you can point attention ah, have a question you can leave a message or private message to add my wechat: HLS1793929520, we see you next time!