Kruskal's algorithm

The algorithm of Kruskal is a greedy algorithm of graph theory for computing minimum spanning trees of undirected graphs. The graph needs to additionally connected, edge- weighted and be finite.

The algorithm comes from Joseph Kruskal, who published it in 1956 in the journal "Proceedings of the American Mathematical Society ". He described it there as follows:

The shortest edge in each case denotes the edge with the smallest edge weight. Upon completion of the algorithm the selected edges form a minimum spanning tree of the graph.

If we apply the algorithm to unconnected graphs, so it computes a minimum spanning tree for each connected component of the graph. These trees form a minimum spanning forest.

Example

Formalized algorithm

The basic idea is to traverse the edges in order of increasing edge weights and adding each edge to the solution which does not form a circle with all previously selected edges. It successively so-called components for the minimum spanning tree are thus connected.

Input

Serves as input an edge- weighted graph related. denotes the set of vertices ( vertices ), the set of edges ( edges ). The weight function assigns each edge to an edge weight.

Output

The algorithm provides with a minimum spanning tree.

Algorithm

The algorithm works by Kruskal non- deterministic, ie it provides under certain circumstances when repeatedly executing different results. These results are all minimum spanning trees of.

G = ( V, E, w): a connected, undirected, edge- weighted graph Kruskal (G) 1 2 3 Sort the edges in L in ascending order according to their edge weight. 4 as long as 5 Choose an edge with the smallest edge weight 6 remove the edge from 7 if the graph contains no cycle 8 then 9 M = (V, E ') is a minimum spanning tree of G. The same algorithm can be applied by analogy to a maximum spanning tree. Be about a connected edge- weighted graph. Then you are with, and the algorithm of Kruskal -in. The output is finally obtained a minimum spanning tree of, and thus a maximum of.

Correctness proof

Be a connected edge- weighted graph and the output of the algorithm of Kruskal. To prove now the correctness of the algorithm, the following must be shown:

In the following, some proof ideas, demonstrate the validity of each statement follow:

If the edge set is generated in the second step of the algorithm, then there is a minimum spanning tree contains. The claim is true, that is, ( that is, there is no edge scheduled). Each minimum spanning tree satisfies the claim and there is a minimum spanning tree as a weighted, connected graph always has a minimum spanning tree. Now assume that the assertion is satisfied for and the edge set generated by the algorithm after step. It should be the minimum spanning tree contains. We now consider the case. For this is the last inserted by the algorithm edge.

Therefore follows that the Kruskal algorithm generated according to steps a quantity that can be expanded to a minimum spanning tree. However, since the result of the steps according to an algorithm is a tree ( as shown above ), it must be minimal.

Time complexity

In the following, the number of edges and the number of nodes. The running time of the algorithm consists of the necessary sorting the edges according to their weight and checking whether the graph is acyclic. The Order requires a term of. With proper implementation, the check for circular freedom is faster possible so that sorting determines the overall runtime. In particular, in graphs with many edges, the algorithm of Prim is so far more efficiently.

If the edges are already sorted, the algorithm of Kruskal works faster. We now consider how quickly the check at the county freedom is possible. In order to achieve the best possible maturity date, stores all nodes in a union-find structure. This contains information about which nodes are connected. At the beginning is no edge registered in the spanning tree, so each node itself is in a single partition. When an edge is to be added, it is checked whether and lie in different partitions. The purpose of the operation Find ( x): It provides a representative of the partition in which the node x is located. If Find ( ) and Find () return different results, then the edge can be added and the partitions of the two nodes are combined ( Union). Otherwise would occur by adding company the edge a circle, the edge is therefore discarded. Overall, the operation Find ( for each edge ), and the operation is called Union times. When using the heuristics Union -by -size and path compression an amortized running time analysis for the algorithm results in a complexity of. It is defined as and practically constant. Theoretically, however, this function grows infinitely, so it can not be omitted in the O- notation.

Others

The algorithm was used Kruskal originally as a tool for a simplified proof that a graph with pairwise distinct edge weights has a unique minimum spanning tree.