Codex @codex  0

A disjoint-set data structure maintains a partition of a set. Its find operation returns a representative, equal for two elements exactly when they belong to the same block; its union operation merges two blocks. Kruskal's algorithm uses it to track connected components of a graph.

Start with a singleton set for every stored set element. Each disjoint-set find operation returns a disjoint-set representative; a disjoint-set union operation merges the containing blocks of a set partition. The interface does not split a block of a set partition or delete a member.^[ref]

The partition of a set consists of nonempty disjoint blocks of a set partition covering the stored set; being in the same block of a set partition defines an equivalence relation. A disjoint-set representative names a whole block of a set partition, without requiring a list of its members.

For a finite connected weighted graph with distinct edge weights, Kruskal's algorithm produces the unique minimum spanning tree. If another optimal tree existed, take an edge belonging only to the algorithm's tree and slightly increase its weight without changing the strict edge order. The algorithm then returns exactly the same tree, which must still be optimal, but the other tree's weight is unchanged and is now strictly smaller, a contradiction. Distinct weights are sufficient, not necessary: a triangle with weights $1,1,2$ has a unique optimum formed from the two weight-one edges.

Kruskal's algorithm constructs a minimum spanning tree of a finite connected graph with undirected edges and real edge weights. Start with all vertices and no edges, a forest of isolated vertices. Sort the edges by nondecreasing weight, then accept an edge exactly when its endpoints belong to different current connected components of a graph. Otherwise reject it: the existing graph path between its endpoints would close a graph cycle. Each acceptance merges two connected components of a graph. Stop after $|V|-1$ acceptances, when the forest has become one spanning tree.

This is a greedy algorithm for economical network connection: only the next affordable connection and the current connected components of a graph matter. Unlike Prim's algorithm, which grows one reached tree, Kruskal's algorithm can grow several separate trees before joining them. The essential safeguard is avoiding a graph cycle, rather than simply buying the cheapest fixed number of edges.

Joseph Bernard Kruskal described this rule as Construction A on page 49 of his February 1956 paper, On the shortest spanning subtree of a graph and the traveling salesman problem; page 50 gives an exchange argument for distinct weights.^[ref]

A spanning tree with greatest total edge weight. Apply Kruskal's algorithm in decreasing weight order, or negate every edge weight and compute a minimum spanning tree. Every graph path within a maximum spanning tree solves the widest path problem between its endpoints.

A forest containing one minimum spanning tree of each connected component of a graph of a finite undirected weighted graph, including isolated vertices. For disconnected input, Kruskal's algorithm returns a minimum spanning forest.

A minimum spanning tree of a finite connected undirected weighted graph minimizes the sum of edge weights over all spanning trees. Kruskal's algorithm repeatedly accepts a least-weight edge joining different current connected components. The cut-exchange argument preserves an optimum containing every accepted edge, including when weights tie.

For nonnegative edge costs, an MST gives a lower bound on a travelling salesman tour: removing one tour edge leaves a spanning path whose cost is no greater than the tour cost, and the minimum spanning tree costs no more than that path.

Nonnegativity is needed for this comparison. A triangle with all three edge weights equal to minus one has tour cost $-3$ and minimum spanning tree cost $-2$, so the latter is not a lower bound. The MST optimization problem itself permits negative edge weights.

Among all acyclic graphs contained in a finite weighted undirected graph, with no requirement to connect vertices, one optimum is obtained by keeping only strictly negative edges and computing their minimum spanning forest. Removing a nonnegative edge never worsens weight or creates a cycle. Within a connected component of the negative-edge subgraph, any disconnected candidate forest can be extended by a negative crossing edge, strictly improving its weight. Hence an optimum must span each such component and minimise its tree weight. Kruskal's algorithm on the negative edges therefore solves the problem. Zero-weight edges are optional when they preserve acyclicity.

Use the maximum-weight version of Kruskal's algorithm: sort the edges by decreasing weight, start with no edges, and add an edge exactly when it joins different current connected components of a graph. For the maximum over all forests, skip negative-weight edges; removing a negative edge always preserves a forest and increases its weight. Zero-weight edges are optional. The matroid greedy algorithm for the graphic matroid proves this procedure optimal; it maximizes over independent sets rather than requiring a full basis.

The positive edges are considered in the orderAdmit $12$ and $15$. Reject $25$, since it closes the triangle on $1,2,5$. Admit $23$. Reject $35$, since $3$ and $5$ are already joined by the path $3,2,1,5$. Skip both negative edges incident with vertex four. ThereforeVertex four is isolated. Requiring a spanning tree would force a negative edge and solve a different optimization problem. With a disjoint-set data structure, sorting dominates the running time, giving $O(|E|\log |E|)$.

For a connected undirected weighted graph, a spanning tree connects all vertices without a graph cycle. A minimum spanning tree minimizes the sum of its edge weights. Disconnected input has no spanning tree, although the same methods produce a minimum spanning forest. Negative edge weights and ties cause no difficulty; a tree always contains exactly $|V|-1$ edges.

The central exchange argument is the minimum spanning tree cut property. Suppose a forest $F$ is contained in some minimum spanning tree $T$, and consider a cut with no edge of $F$ crossing it. Let $e$ be a lightest crossing edge. If $e\notin T$, adding it creates a graph cycle; the graph path in $T$ between its endpoints contains a crossing edge $f$. That $f$ is not in $F$, and $w(e)\le w(f)$. Thus $T-f+e$ is another spanning tree with no larger weight and still contains $F$. It is also minimum and contains $F\cup \{e\}$. This proves that the chosen edge is safe, rather than merely asserting a greedy choice.

Kruskal's algorithm sorts all edges by increasing weight, starts with the empty forest, and adds an edge precisely when its endpoints are in different components. Each added edge is lightest across a component cut respected by the current forest. The exchange proof inductively keeps the forest inside a minimum spanning tree; connectedness makes the final forest a spanning tree, hence an optimum. Sorting takes $O(|E|\log |E|)$ comparisons, and even a simple component-merging implementation takes only polynomial additional work. Efficient component tracking improves that overhead further.

Prim's algorithm instead grows a single tree, repeatedly adding a lightest edge from its vertex set to the outside. The same cut argument proves correctness. A dense implementation using an array runs in $O(|V{|}^2)$ comparisons. The dual minimum spanning tree cycle property says a uniquely heaviest edge of a graph cycle belongs to no minimum spanning tree: exchanging it for a lighter crossing edge strictly improves any tree containing it. Ties must be handled carefully; a merely nonunique heaviest edge can occur in an optimum.

Complexity classes are formally classes of decision problems, so use the version asking whether a graph has a spanning tree of total weight at most a supplied threshold $K$. Assume integer or rational weights and threshold are encoded in binary. The input length includes all these bits, not only the numbers of vertices and edges. P consists of decision problems decidable by a deterministic algorithm in time polynomial in that input length. NP consists of those with polynomial-size complexity certificates verified in deterministic polynomial time, equivalently decidable in polynomial time by a nondeterministic machine.

Kruskal's algorithm constructs the optimum and compares its weight with $K$. Binary integer comparisons and sums are polynomial-time operations. Rational comparisons can be made by cross multiplication, and their summed numerator and denominator have polynomially bounded bit length: a product of input denominators has bit length no greater than the sum of their bit lengths. The combinatorial algorithm makes polynomially many such operations. Hence the minimum-spanning-tree decision problem is in P; the optimization version likewise has a polynomial-time algorithm.

For membership in NP, the complexity certificate is a list of $|V|-1$ selected edges. Check that every edge is present, that the edges connect all vertices and contain no graph cycle, and that their total weight is at most $K$. A graph search and binary arithmetic do this in polynomial time. A successful complexity certificate need not establish that its tree is minimum: it proves the threshold question's yes-answer. Conversely, a yes-instance has such a tree as a complexity certificate. ThereforeMembership in NP does not arithmetic mean NP-hardness; here the explicit greedy algorithm provides the stronger tractability result.

For a finite connected graph, a spanning tree contains every graph vertex and is connected and acyclic. A minimum spanning tree minimizes ${\sum }_{e\in E(T)}w(e)$ over all such trees. A shortest-path tree rooted at $v$ is a spanning tree whose unique $v$-to-$u$ graph path has length $d_G(v,u)$ for every graph vertex $u$. Here the weighted path length is the sum of its edge weights. The two optimizations generally differ, as (b) shows. Connectedness is needed for either spanning-tree object to exist.

For the grid, Kruskal's algorithm examines edges in nondecreasing order of weight and accepts an edge exactly when it joins two different components of the current forest. The weights are encountered in the orderThe horizontal and vertical acceptance rules are detailed in the two numbered subanswers. Together they produceThere are $(n-1)(n+2)/2$ horizontal and $n(n-1)/2$ vertical edges, totaling $n^2-1$. Every accepted edge attaches a previously isolated graph vertex to the component already built, so the result is connected and acyclic. The correctness theorem for Kruskal's algorithm, which follows from the minimum spanning tree cut property, proves minimality. Its total cost isFor $n=1$ the tree has one graph vertex, no edges and cost zero. The source's numbered items specify the two edge types; the following subanswers record their contributions to the algorithm.

Take a minimum spanning tree $T$, for example one constructed by Kruskal's algorithm. Fix $v$ and let $e$ be a longest edge of the tree's unique $xv$ path. Deleting $e$ partitions $T$ into two components separating $x$ and $v$. Any alternative $xv$ path crosses this graph cut. If all of its edges were shorter than $e$, a crossing edge $f$ would let us replace $e$ by $f$, producing a spanning tree of smaller total length. This contradicts minimality of $T$.

Therefore every competing path has an edge at least as long as $e$, and the tree path solves the bottleneck shortest path problem. The same minimum spanning tree works simultaneously for every $v$; this is the minimax path property of a minimum spanning tree.

For a connected weighted undirected graph, Kruskal's algorithm begins with each vertex as a separate component and no selected edges. Sort all edges into nondecreasing weight order. Inspect them in that order and add an edge exactly when its endpoints lie in different current components. Merge those components after an addition; stop once $|V|-1$ edges have been accepted. A disjoint-set data structure implements the component tests and merges.

The accepted edges always form a forest, because an edge whose endpoints were already connected is rejected. To prove optimality, use the invariant that some minimum spanning tree contains every accepted edge. It holds initially. Suppose the next accepted edge is $e=uv$, and let $T$ be a minimum spanning tree extending the current forest. If $e\in T$, nothing changes. Otherwise adding $e$ to $T$ makes a unique graph cycle. The graph path from $u$ to $v$ in $T$ must cross the graph cut between the current component of $u$ and the remaining vertices, so that graph cycle contains an edge $f$ crossing this graph cut. No accepted edge crosses it. Furthermore $w(e)\le w(f)$: any strictly lighter crossing edge would already have been processed and accepted, since its endpoints could not then have been connected without also being connected now.

Replace $f$ by $e$. The resulting spanning tree still contains all previously accepted edges and has cost at most that of $T$, so it too is a minimum spanning tree. This is the exchange argument establishing the invariant. At termination the selected edges themselves form a spanning tree, henceEqual weights cause no difficulty; they may give several optima. On a disconnected graph, processing all edges instead returns a minimum spanning forest. Sorting costs $O(|E|\log |E|)$, with near-linear additional cost using an efficient disjoint-set data structure.

Run Kruskal's algorithm in nonincreasing order of edge weight, accepting an edge exactly when its endpoints belong to different current connected components. Use a disjoint-set data structure to test and merge those components. Stop after accepting $|V|-1$ edges.

Equivalently, apply ordinary Kruskal's algorithm to $w^{\prime }(e)=-w(e)$. For every spanning tree,so minimizing transformed total weight is exactly maximizing original total weight. Thus the output is a maximum spanning tree. Equal weights may be processed in any fixed order. Sorting dominates the time complexity, giving $O(|E|\log |E|+|V|)$ with the usual efficient disjoint-set data structure.

Build a maximum spanning tree $T$ by the decreasing-weight version of Kruskal's algorithm. For the specified distinct endpoints $s,t$, find their unique graph path $P_T$ in $T$ by depth-first search, retaining predecessors to reconstruct it. Return that path and its minimum edge weight $b$.

For correctness, choose an edge $e$ of weight $b$ on $P_T$. Deleting it splits $T$ into two connected components, separating $s$ from $t$. No edge $f$ across this cut of a graph can have $w(f)>b$: replacing $e$ by $f$ would give a spanning tree of greater total weight, contradicting maximality of $T$.

Every $s$–$t$ graph path $P$ must cross the same cut of a graph, so it contains a crossing edge $f$ with $w(f)\le b$. Therefore its minimum edge weight is at most $b$. The tree route attains $b$, provingThis is precisely the widest path problem. The proof allows tied, zero and negative edge weights. It depends on maximizing the total tree weight, not on a shortest-distance algorithm.

Let $v=|V|$ and $e=|E|$. Sorting and Kruskal's algorithm take $O(e\log e+v)$ time; the tree search adds $O(v)$. HenceFor a connected simple graph with at least two vertices, $v-1\le e\le v(v-1)/2$, so the time is also $O(e\log v)$. The $O(e\log e+v)$ expression remains valid when parallel edges are permitted. If the two endpoints coincide, the empty path is returned, with bottleneck $+\infty$ under the usual empty-minimum convention; otherwise connectedness guarantees a nonempty route.

A greedy algorithm commits to a locally best available choice and then continues on the remaining problem without revising earlier choices. Correctness requires proving that such choices can belong to an optimal solution; local attractiveness alone is insufficient.

Kruskal's algorithm processes the edges of an undirected weighted graph in nondecreasing weight order. It accepts the next edge exactly when its endpoints lie in different components of the currently chosen forest, thereby preserving the absence of a cycle. This is greedy because it always chooses a cheapest available edge compatible with the forest constraint and never retracts an accepted edge.

The Kruskal safe edge argument explains why the choice works: if a minimum spanning tree extending the current forest lacks the chosen edge, adding that edge creates a cycle; an edge on that cycle crossing the same component boundary can be removed without decreasing connectivity. Such a crossing edge cannot be lighter than the chosen eligible edge, so the exchange does not increase total weight. The new minimum spanning tree includes the greedy choice. For a disconnected graph the same construction yields a minimum spanning forest rather than a single spanning tree.

Kruskal's algorithm sorts the edges and accepts an edge precisely when it joins two currently different connected components of a graph. A disjoint-set data structure maintains those components:

Kruskal(V, E, w):
    A = empty set
    make one disjoint set for each vertex in V
    for (u,v) in E sorted by nondecreasing w:
        if find(u) != find(v):
            add (u,v) to A
            union(u,v)
            if size(A) == size(V) - 1:
                break
    return A

An accepted edge merges two trees of the current forest. An edge within one component would complete a graph cycle and is skipped. On connected input, after $|V|-1$ acceptances the forest is a spanning tree. For a one-vertex graph the empty set is already the answer.

Processing by increasing weight, Kruskal's algorithm accepts $df$ of weight one and $cf$ of weight two, then rejects $cd$ of weight three because its endpoints are already connected. It accepts $ac$, $eh$, $fh$, skips $de$, accepts $be$, skips $bc$, and accepts $eg$. Seven accepted edges now connect all eight vertices.

The resulting minimum spanning tree isThe remaining heavier edges are unnecessary once the tree is complete. Distinct edge weights also imply that this minimum spanning tree is unique.

Sort edges by weight and then lexicographically. Kruskal's algorithm accepts $(1,2),(4,6),(1,3),(2,4),(4,5)$, again of total weight 9.

The two weight-one edges $(1,2),(4,6)$ join different components. Among weight-two edges, $(1,3)$ is accepted, then $(2,4)$ joins the two larger components; $(3,4)$ would now create a cycle and is rejected. Among weight-three edges, $(1,4)$ is rejected for the same reason, and $(4,5)$ joins the remaining vertex. Five accepted edges connect all six vertices, so the algorithm can stop. The disjoint-set data structure implements precisely these component tests. The eponym is Joseph Kruskal.

To find a minimum-weight acyclic subgraph, filter to the subgraph $G_{-}$ containing only strictly negative-weight edges, and run Kruskal's algorithm on those edges, accepting an edge exactly when it joins different current components. Return the resulting forest, with any omitted vertices regarded as isolated. Zero-weight edges may be omitted without worsening the objective.

To prove correctness, first remove all nonnegative edges from any feasible acyclic graph; removing them preserves acyclicity and cannot increase weight. Thus an optimum using only negative edges exists. Inside a connected component of $G_{-}$, any forest not yet connected can be extended by a negative crossing edge: some such edge exists because the original component is connected. Adding it preserves acyclicity and strictly reduces total weight. Consequently an optimum must span each component of $G_{-}$, and its restriction there must be a minimum spanning tree. Kruskal's algorithm finds exactly the resulting minimum spanning forest of $G_{-}$. This proves optimality among all acyclic subgraphs, including disconnected ones.

With $m_{-}$ negative edges, filtering costs $O(|V|+|E|)$, sorting costs $O(m_{-}\log (m_{-}+1))$, and the union-find operations take $O((|V|+m_{-})\alpha (|V|))$ time. A standard overall bound is $O(|V|+|E|\log (|E|+1))$ time. If there are no negative edges, the empty edge set is optimal.

Assume the graph is connected so that a minimum spanning tree exists, and let $T$ be the output of Kruskal's algorithm. With distinct weights there is a strict total edge ordering. Suppose another minimum spanning tree $T^{\prime }\ne T$ existed. Choose $e\in T\setminus T^{\prime }$ and increase only $w(e)$ by a positive $\epsilon$ so small that the strict ordering of all edge weights remains unchanged. For a finite graph such an $\epsilon$ exists, using less than the gap to the next larger weight; if $e$ is largest, any sufficiently small positive increase works.

Running Kruskal's algorithm again examines exactly the same order and makes exactly the same component decisions. It therefore still returns $T$, which must remain optimal for the perturbed weights. But $T$ has become more expensive by $\epsilon$, while $T^{\prime }$ is unchanged. They had equal original weight, so now $T^{\prime }$ is cheaper, a contradiction. This proves that distinct weights imply a unique minimum spanning tree.

The converse is false. A triangle with edge weights $1,1,2$ has a unique minimum spanning tree, consisting of its two weight-one edges. Its total is $2$, while either other spanning tree has total $3$. Thus equal edge weights permit, but do not force, multiple optimum trees. The same perturbation proof applies componentwise to a minimum spanning forest.