Code example of Kruskal algorithm based on undirected weighted graph in Java language

The so-called weighted graph means that each edge in the graph will have a corresponding value or group of values. Usually, this value is just a number

For example, in the transportation network, the weight on the edge may represent the distance or the transportation cost (obviously both are numbers). However, the weight on the edge may also be other things, such as a string or even a more complex data packet, in which more data is collected

The core idea of Kruskal algorithm is to continuously find the smallest edge in the edge set in the weighted connected graph. If the edge meets the condition of obtaining the minimum spanning tree, it will be constructed until a minimum spanning tree is finally obtained.

Execution steps of Kruskal algorithm:

Step 1: in the weighted connected graph, the weights of edges are sorted;

Step 2: judge whether this edge needs to be selected (at this time, the edges in the graph have been arranged in order according to the weight from small to large). The judgment is based on whether the two vertices of the edge are connected. If connected, continue to the next one; if not, select to connect them.

Step 3: cycle the second step until all vertices in the graph are in the same connected component, that is, the minimum spanning tree is obtained.

For the implementation of weighted graph, see the following examples:

Graph:

Algorithm:

Test class:

summary

The above is all about the code example of Kruskal algorithm based on undirected weighted graph in Java language. I hope it will be helpful to you. If you have any questions, you can leave a message at any time. Xiaobian will try his best to answer them for you.