Kruskal's algorithm - efficient algorithm for constructing the minimum spanning tree of a weighted connected undirectedgraph. The algorithm is also used to find some approximations for the Steiner problem.

The algorithm solves the problem of finding the minimum spanning tree (MST).

The problem of finding the minimum spanning tree is often encountered in a similar setting: for example, there arencities that need to be connected by roads so that one can get from any city to any other (directly or through othercities). It is allowed to build roads between given pairs of cities and the cost of building each such road is known. Itis required to decide which roads should be built in order to minimize the total cost of construction.

At the beginning, the current set of edges is set to empty. Then, while it is possible, the following operation iscarried out: from all edges, the addition of which to the already existing set does not cause the appearance of a cyclein it, the edge of the minimum weight is selected and added to the already existing set. When there are no more suchedges, the algorithm is complete. The subgraph of a given graph, containing all its vertices and the found set of edges,is its minimum weight spanning tree.

First, let's sort the incoming list of edges by weight. Thus, taking the elements sequentially from the list, each timewe will receive the edge with the minimum weight among the remaining ones.

Next, in the loop, we look for the index of the set that contains the beginning of the edge and the set that containsthe end of the edge. If the set is not found, we getNone.

• Ifboth sets are found and theirindices are equal, we skip an edge, it will make a cycle.
• Ifone of the edge points was found in some set, add the opposite point to this set and add the edge to theresult.
• Ifboth sets are not found, add an edge to the result and add to the list of sets a set with two points of thisedge
• Ifboth sets are found, but theindices are not equal, add an edge to the result and join the sets by indicesusing theunion operation.

defkruskal(edges:list)->list:# Sorting input edges by weightedges=sorted(edges,key=lambdaitem:item[2])# Adding first edge (with smallest weight) to result list and deleting it from input edges.result= [edges.pop(0)]# Adding to array first set of expanded points.array= [{result[0][0],result[0][1]}]# For each edge in sorted list (without deleted first)foredgeinedges:# Looking for start point occurrences in expanded points sets and trying to get set index.start_connection=next(iter([iforiinrange(len(array))ifedge[0]inarray[i]]),None)# Looking for end point occurrences in expanded points sets and trying to get set index.end_connection=next(iter([iforiinrange(len(array))ifedge[1]inarray[i]]),None)# If edge makes cycle - skip it.ifstart_connectionisnotNoneandstart_connection==end_connection:continue# Adding edge to result list.result.append(edge)# If edge first point found in expanded points set - add second edge point.ifstart_connectionisnotNone:array[start_connection].add(edge[1])# If edge second point found in expanded points set - add first edge point.ifend_connectionisnotNone:array[end_connection].add(edge[0])# If edge is not connected with any chains - add new set of expanded points. (new chain)ifstart_connectionisNoneandend_connectionisNone:array.append({edge[0],edge[1]})# If edge connects two chains - merge these chains. (union from two expanded points sets)ifstart_connectionisnotNoneandend_connectionisnotNone:array.append(array[start_connection].union(array[end_connection]))array= [array[i]foriinrange(len(array))ifi!=start_connectionandi!=end_connection]returnresult

[('a', 'd', 5), ('c', 'e', 5), ('d', 'f', 6), ('a', 'b', 7), ('b', 'e', 7), ('e', 'g', 9)]

Author:Danil Andreev.
Thanks for inspiration:Wikipedia.