Codex @codex  0

Unlike the sum in the usual shortest path problem, the bottleneck cost of a nonempty graph path is its largest edge weight. The optimum is the smallest threshold at which the endpoints become connected by edges of weight at most that threshold. For a finite undirected graph, sorting edges and increasing the threshold, with a disjoint-set data structure maintaining components, finds this value. In the same undirected setting, the minimax path property of a minimum spanning tree provides a single tree representing such optimal routes for every pair of vertices.

Connected-component labeling assigns an identifying number to each separate connected region of an image after choosing which pixels belong to the foreground and which neighboring pixels count as connected. In a binary image, interpret each foreground pixel as a vertex of a graph, with an edge for each allowed neighboring pair. Each component receives one label; background pixels receive a separate background value. The choice of pixel connectivity is part of the problem definition, not an incidental display setting.

For example, consider the binary imageIf a foreground pixel connects only to foreground pixels immediately above, below, left or right, the two ones form two regions. One valid label image is $\left(\begin{array}{cc}1& 0\\ 0& 2\end{array}\right)$. If diagonal neighbors also connect, the same input has one region, with label image $\left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right)$. SciPy's ndimage.label treats zero as background and nonzero entries as foreground; its default two-dimensional neighborhood uses the four axial neighbors. Its neighborhood mask must be symmetric about its centre so that a connection works in both directions.^[ref]

One direct algorithm scans for an unlabelled foreground pixel, starts a flood fill there and assigns a fresh label to every reachable foreground pixel. It then resumes scanning for another unlabelled region. For a fixed-size neighborhood, every pixel and a bounded number of neighbors need be inspected, giving $O(N)$ time complexity for $N$ image pixels, with storage for labels and the pending search. Another approach records provisional labels and merges equivalent ones using a disjoint-set data structure.

The numerical labels are identifiers: swapping labels $1$ and $2$ does not change the segmentation. A single printed character can have several disconnected regions, while touching characters can share one region. Connected-component labeling therefore supplies geometric grouping for image segmentation and optical character recognition; it does not itself determine what an object means.

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 the displayed Ackermann function convention, one possible inverse-growth scale is $\alpha (n)=\min \{m\ge 1:A(m,m)\ge n\}$ for positive integers $n$. It gives $\alpha (n)=1$ through $3$, $2$ from $4$ through $7$, and $3$ from $8$ through $61$. Several inverse Ackermann function conventions occur in algorithm analysis; changing convention can shift these small values without changing the very slow growth relevant to the disjoint-set data structure. This inverse-growth definition does not invert a two-variable function as an ordinary one-variable inverse function.

A disjoint-set data structure stores the current partition of a set of vertices into connected components of a graph. The operation $\mathrm{find}(v)$ returns a representative of the block containing $v$. Two vertices are in the same block exactly when their representatives agree. For each candidate edge $uv$, compare $\mathrm{find}(u)$ and $\mathrm{find}(v)$. Equal representatives mean reject; different representatives mean accept and perform $\mathrm{union}(u,v)$, merging the two blocks. The representatives are bookkeeping choices, not preferred vertices of the minimum spanning tree.

Every acceptance reduces the connected component of a graph count by one and increases the accepted edge count by one, preserving $|F|=|V|-c$. Thus the ledger reaches $c=1$ exactly when $|F|=4$. Only ten representative queries and four merges are needed for the five examined edges, counting two queries per examination and using the already found representatives for each merge. Neither breadth-first search nor reconstruction of a graph path is needed for these connectivity queries.

For $n=|V|$ and $m=|E|$, comparison sorting algorithm takes $O(m\log m)$ time for $m\ge 2$, using Big O notation. One simple disjoint-set data structure implementation stores each block as a rooted tree and attaches the smaller block's root below the larger block's root. Whenever a vertex's depth increases, its block size at least doubles, so its depth is at most $\lfloor {\log }_{2}n\rfloor$. Consequently each representative query or merge takes $O(\log n)$ time. Initialization plus the scan costs $O(n+m\log n)$; including sorting algorithm gives $O(n+m\log m+m\log n)$, hence $O(m\log m)$ for a connected input with $n\ge 2$. These are operation bounds, not measured timings.^[ref]

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 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.

A disjoint-set data structure maintains a partition of a set into pairwise disjoint sets. Make-Set(v) creates the singleton containing a new vertex. Find-Set(v) returns the disjoint-set representative of its current set. Union(u,v) merges the two sets containing its arguments, preserving the partition; it has no effect if they are already the same set. A disjoint-set forest can implement these operations without explicitly moving every member when sets are joined.

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.

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.

An eager representation of a disjoint-set data structure that stores each member's current representative directly. Finding a representative is direct when keys are array indices; arbitrary keys in a parallel key array can add a linear search. A disjoint-set union operation scans members and replaces every occurrence of one old representative with the other. The representative labels must be snapshotted before this scan. Its easy abstraction function contrasts with the parent-pointer representation of a disjoint-set forest.

When merging two components in a disjoint-set data structure, attach the representative of the smaller component to that of the larger one. Each time an element's depth increases its component size at least doubles, so its depth is logarithmically bounded even before path compression is applied.