At the beginning of the 19th century, a geometer from Berlin, Jacob Steiner, set the task of how to connect the three villages so that their length was the shortest. Subsequently, he generalized this problem: it is required to find a point on the plane such that the distance from it to n other points is the smallest. In the 20th century, work continued on this topic. It was decided to take several points and connect them so that the distance between them was the shortest. This is all a special case of the problem being studied.
Greedy algorithms
Kruskal's algorithm refers to the "greedy" algorithms (they are also called gradient). The essence of those is the biggest gain at every step. Not always "greedy" algorithms give the best solution to the problem. There is a theory showing that when applied to certain tasks, they provide an optimal solution. This is the theory of matroids. The Kraskal algorithm refers to such problems.
Finding a minimum weight skeleton
The considered algorithm constructs the optimal frame of the graph. The problem about it is as follows. An undirected graph is given without multiple edges and loops, and a weight function w is assigned on the set of its edges, which assigns to each edge e a number - the weight of the edge - w (e). The weight of each subset of the set of edges is determined by the sum of the weights of its edges. It is required to find the frame of the smallest weight.
Description
The Kraskal algorithm works like this. First, all edges of the original graph are arranged in ascending order of weights. Initially, the frame does not contain any edges, but includes all the vertices of the graph. After the next step of the algorithm, one edge is added to the already constructed part of the framework, which is the spanning forest. It is not chosen arbitrarily. All edges of the graph that do not belong to the frame can be called red and green. The vertices of each red edge are in one connected component of the forest under construction, and the green vertices are in different. Therefore, if you add a red edge there, a cycle appears, and if green, in the forest obtained after this step, the connected components will be less by one. Thus, not a single red edge can be added to the resulting construction, but any green edge can be added to obtain a forest. And a green rib with minimal weight is added. The result is a frame of the smallest weight.
Implementation
Denote the current forest F. It divides the set of vertices of the graph into connected areas (their union forms F, and they do not intersect in pairs). At the red edges, both peaks lie in one part. Part (x) is a function that for each vertex x returns the name of the part to which x belongs. Unite (x, y) is a procedure that builds a new partition, consisting of the union of the parts x and y and all other parts. Let n be the number of edges of the graph. All these concepts are included in the Kraskal algorithm. Implementation:
Sort all edges of the graph from 1st to nth in ascending order of weight. (ai, bi are the vertices of the edge with number i).
for i = 1 to n do.
x: = Part (ai).
y: = Part (bi).
If x is not equal to y then Unite (x, y), include in edge F the number i.
Correctness
Let T be the frame of the original graph constructed using the Kruskal algorithm, and S be its arbitrary frame. It is necessary to prove that w (T) does not exceed w (S).
Let M be the set of edges S, P the set of edges T. If S is not equal to T, then there is an edge et of the skeleton T that does not belong to S. Connect et to S. We form a cycle, call it C. We remove from C any edge es belonging to S. Get a new frame, because there are as many edges and vertices in it. Its weight does not exceed w (S), since w (et) is not greater than w (es) by virtue of the Kraskal algorithm. This operation (replacing the edges of S by the edges of T) will be repeated until we obtain T. The weight of each subsequent frame obtained is not greater than the weight of the previous one, which implies that w (T) is not greater than w (S).
The correctness of the Kruskal algorithm also follows from the Rado-Edmonds theorem on matroids.
Examples of application of the Kruskal algorithm
A graph is given with vertices a, b, c, d, e and edges (a, b), (a, e), (b, c), (b, e), (c, d), (c, e) , (d, e). The weights of the ribs are shown in the table and in the figure. Initially, the forest under construction F contains all the vertices of the graph and does not contain any edges. The Kraskal algorithm will first add the edge (a, e), since it has the smallest weight, and the vertices a and e are in different components of the forest F (the edge (a, e) is green), then the edge (c, d), therefore that this edge has the smallest weight of the edges of the graph that do not belong to F, and it is green, then, for the same reasons, the edge (a, b) is added. But the edge (b, e) is skipped, although it has the smallest weight of the remaining edges, because it is red: the vertices b and e belong to the same connected component of the forest F, that is, if we add the edge (b, e) to F, then cycle. Then a green edge (b, c) is added, a red edge (c, e) is skipped, and then d, e. Thus, edges (a, e), (c, d), (a, b), (b, c) are added sequentially. The optimal frame of the original graph consists of nihers. This is how the algorithm works in this case. Kraskala. An example is shown.
The figure shows a graph consisting of two connected components. Bold lines show the edges of the optimal framework (green) constructed using the Kraskal algorithm.
The top graph shows the original graph, and the bottom one shows the minimum weight frame constructed for it using the algorithm in question.
The sequence of added ribs: (1,6); (0.3), (2.6) or (2.6), (0.3) - it does not matter; (3.4); (0,1), (1,6) or (1,6), (0,1) is also indifferent (5,6).
The Kraskal algorithm finds practical application, for example, to optimize the laying of communications, roads in new microdistricts of settlements in each country, as well as in other cases.