Editing Kruskal's algorithm
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision | Your text | ||
Line 1: | Line 1: | ||
'''Kruskal's algorithm''' is a general-purpose algorithm for the [[minimum spanning tree]] problem, based on the [[disjoint sets data structure]]. The existence of very simple algorithms to maintain disjoint sets in almost [[Asymptotic analysis|constant time]] gives rise to simple implementations of Kruskal's algorithm whose running times are close to linear, usually outperforming [[Prim's algorithm]] in sparse graphs. | '''Kruskal's algorithm''' is a general-purpose algorithm for the [[minimum spanning tree]] problem, based on the [[disjoint sets data structure]]. The existence of very simple algorithms to maintain disjoint sets in almost [[Asymptotic analysis|constant time]] gives rise to simple implementations of Kruskal's algorithm whose running times are close to linear, usually outperforming [[Prim's algorithm]] in sparse graphs. | ||
− | + | =Theory of the algorithm= | |
− | Kruskal's may be characterized as a [[greedy algorithm]], which builds the MST one edge at a time. As befits a MST algorithm, the greedy strategy is to continually add the remaining edge of lowest weight. Unlike Prim's, however, Kruskal's adds edges without regard to the connectivity of the partially built MST. We shall assume that a spanning tree exists for the following sections. (If you find them too difficult, skip them.) | + | Kruskal's may be characterized as a [[greedy algorithm]], which builds the MST one edge at a time. As befits a MST algorithm, the greedy strategy is to continually add the remaining edge of lowest weight. Unlike Prim's, however, Kruskal's adds edges without regard to the connectivity of the partially built MST; that is, it does not necessarily add an edge emanating from a vertex that is in the partially built MST. Indeed, it may be said that Kruskal's starts with <math>V</math> forests of one vertex each, and adds edges one by one, each one causing two trees in the forest to coalesce into one, until all vertices have been placed in the same connected component and the MST is complete. In doing so, one must be careful not to add an edge between two vertices that are ''already'' in the same component, for doing so would create a cycle. We shall assume that a spanning tree exists for the following sections. (If you find them too difficult, skip them.) |
− | + | ==Lemma== | |
− | <p>Suppose that a | + | <p>Suppose that a subset <math>S</math> of the edges of a graph <math>G</math> is known to be a subset of the edges of some spanning tree of <math>G</math>. Consider the set of edges <math>T</math> containing exactly those edges <math>\in G\S</math> which, when added to <math>S</math>, do not induce a cycle. If a minimal-weight edge <math>\in T</math> is added to <math>S</math>, the resulting set is also guaranteed to be a subset of the edges of some spanning tree of <math>G</math>. |
− | + | ''Proof'': Consider the graph <math>G'</math> with vertex set <math>V(G)</math> and edge set <math>S</math>. Now, any edge in <math>G\S</math> connects either two vertices in different connected components in <math>G'</math> or two vertices in the same component. If it connects two vertices in the same component, adding it generates a cycle (since there is already a path from one component to the other that does not use that edge, and adding the edge generates a return path) and it is not in <math>T</math>. Otherwise, it does not generate a cycle because it is a bridge in the resulting single connected component, and it is in <math>T</math>. That is, <math>T</math> consists of exactly those edges linking different connected components in <math>G'</math>. It is clear that <!-- | |
− | == | + | ==Lemma 2== |
− | <p> | + | <p>Given some tree <math>T</math> which is a subgraph of graph <math>G</math> that is known to be a subtree of some MST of <math>G</math>, we shall call an edge a ''crossing'' edge if it joins a vertex <math>\in V(T)</math> and a vertex <math>\notin V(T)</math>. Then, any minimal crossing edge <math>e</math> may be added to <math>T</math> to give a new tree which is also a subtree of some MST of <math>G</math>.</p> |
− | + | <p>''Proof'': Given some MST of <math>G</math> containing <math>T</math> as a subtree, we may add our minimal crossing <math>e</math> to the MST. Evidently, the resulting cycle must contain another crossing edge. If this other crossing edge is of higher weight than <math>e</math>, we can delete it to yield a new spanning tree, ''per'' Lemma 1, whose weight is lower than the weight of the original spanning tree, contradicting our assumption that the spanning tree with which we started was minimal. Otherwise, the other crossing edge is of the same weight as <math>e</math> (it cannot be of lower weight, since <math>e</math> is minimal) and the addition of <math>e</math> and deletion of this edge yield, ''per'' Lemma 2, another spanning tree, this time of the same weight as the original, which is therefore another MST of <math>G</math>. That is, given any MST of <math>G</math> that does not contain <math>e</math>, we are able to generate another that does.</p> | |
− | + | ||
− | == | + | ==The algorithm== |
− | <p> | + | <p>The algorithm then operates as follows: we start with a trivial tree containing only one vertex (and no edges). It does not matter which vertex is chosen. Then, we choose a minimal-weight edge emanating from that vertex, adding it to our tree. We repeatedly choose a minimal-weight edge that joins any vertex in the tree to one not in the tree, adding the new edge and vertex to our tree. When there are no more vertices to add, the tree we have built is an MST.</p> |
− | + | ||
− | + | <p>''Proof'': By induction. | |
− | + | * Base case: We begin with a tree which, as it contains only one vertex and no edges, is certainly a subtree of some MST of the graph. (Of course, it is a subtree of ''all'' MSTs of the graph, but that fact is not important here.) | |
− | <p>''Proof'': | + | * Inductive step: By Lemma 2, if the current tree is the subtree of some MST of the graph, then the tree resulting from the addition of any minimal crossing edge to our tree yields a new tree which is also the subtree of some MST of the graph. |
− | + | In this way we proceed through a sequence of trees, each of which contains one more vertex than its predecessor, until we obtain a spanning tree. Since this spanning tree is the subtree of some MST of the graph, it must be an MST itself.</p> | |
− | * | + | |
− | + | ||
− | + | ||
− | |||
=Implementation= | =Implementation= | ||
As the previous sections are a bit heavy, here is some pseudocode for Prim's algorithm: | As the previous sections are a bit heavy, here is some pseudocode for Prim's algorithm: | ||
Line 40: | Line 34: | ||
</pre> | </pre> | ||
--> | --> | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
[[Category:Algorithms]] | [[Category:Algorithms]] | ||
− |