188 Kruskal's Algorithm

188 Kruskal's Algorithm

Kruskal's algorithm is a typical method for constructing minimum whole trees (MSTs) in graphs. The algorithm focuses on the weights of the edges, choosing the ones with the lowest cost first, and aims to efficiently connect the whole. A minimum global tree is a subgraph such that all vertices are connected and the sum of the weights of the edges of the whole is minimal.

First, all edges in the graph are sorted in ascending order by their weights. Then we check the edges one by one in decreasing order of weight, and if adding an edge does not create a closed path (cycle), we choose that edge. If a closed path is possible, the edge is skipped. This process is repeated until finally "vertex-number-1" edges are selected, at which point the algorithm is complete and the tree becomes a minimum global tree.

An important part of this process is to determine if a closed path can be created when an edge is added. For this purpose, a fast data management technique called Union-Find (prime set data structure) is used. It manages the groups to which each vertex belongs, and only adds an edge if no two vertices belong to the same group, thus avoiding loops.

The Kruskal method is applied, for example, in road planning to connect cities with the least construction cost or in the optimization of communication lines. The strategy of connecting the whole system in the shortest distance while steadily selecting the least-cost edges is a simple but very practical approach.