Text of docs.kernel.org › core-api › union_find.html as Styx crawled it on Nov 19, 2026. The page may have changed since. Only its words are kept, without pictures or layout.

Open the live page

Union-Find in Linux — The Linux Kernel documentation

The Linux Kernel 7.4.0-rc3 Quick search Contents Working with the development community Development process Submitting patches Code of conduct Maintainer handbook All development-process docs Internal API manuals Core API Core utilities Data structures and low-level utilities Everything you never wanted to know about kobjects, ksets, and ktypes Adding reference counters (krefs) to kernel objects Scope-based Cleanup Helpers Generic Associative Array Implementation Folio Queue XArray Maple Tree ID Allocation Circular Buffers Red-black Trees (rbtree) in Linux Generic radix trees/sparse arrays Generic bitfield packing and unpacking functions this_cpu operations ktime accessors The errseq_t datatype Atomic types Atomic bitops Floating-point API Union-Find in Linux Min Heap API Generic parser Linked Lists in Linux Low level entry and exit Concurrency primitives Low-level hardware management Memory management Interfaces for kernel debugging Everything else Driver APIs Subsystems Locking Development tools and processes Licensing rules Writing documentation Development tools Testing guide Hacking guide Tracing Fault injection Livepatching Rust User-oriented documentation Administration Build system Reporting issues Userspace tools Userspace API Firmware-related documentation Firmware Firmware and Devicetree Architecture-specific documentation CPU architectures Other documentation Unsorted documentation Translations Translations This Page Show Source English Chinese (Simplified) Union-Find in Linux ¶ Date : June 21, 2024 Author : Xavier < xavier_qy @ 163 . com > What is union-find, and what is it used for? ¶ Union-find is a data structure used to handle the merging and querying of disjoint sets.

The primary operations supported by union-find are: Initialization: Resetting each element as an individual set, with each set’s initial parent node pointing to itself. Find: Determine which set a particular element belongs to, usually by returning a “representative element” of that set. This operation is used to check if two elements are in the same set. Union: Merge two sets into one. As a data structure used to maintain sets (groups), union-find is commonly utilized to solve problems related to offline queries, dynamic connectivity, and graph theory.

It is also a key component in Kruskal’s algorithm for computing the minimum spanning tree, which is crucial in scenarios like network routing. Consequently, union-find is widely referenced. Additionally, union-find has applications in symbolic computation, register allocation, and more. Space Complexity: O(n), where n is the number of nodes. Time Complexity: Using path compression can reduce the time complexity of the find operation, and using union by rank can reduce the time complexity of the union operation .

These optimizations reduce the average time complexity of each find and union operation to O(α(n)), where α(n) is the inverse Ackermann function. This can be roughly considered a constant time complexity for practical purposes. This document covers use of the Linux union-find implementation. For more information on the nature and implementation of union-find, see: Wikipedia entry on union-find https://en.wikipedia.org/wiki/Disjoint-set_data_structure Linux implementation of union-find ¶ Linux’s union-find implementation resides in the file “lib/union_find.c”.

To use it, “#include <linux/union_find.h>”. The union-find data structure is defined as follows: struct uf_node { struct uf_node *parent; unsigned int rank; }; In this structure, parent points to the parent node of the current node. The rank field represents the height of the current tree. During a union operation , the tree with the smaller rank is attached under the tree with the larger rank to maintain balance.

Initializing union-find ¶ You can complete the initialization using either static or initialization interface. Initialize the parent pointer to point to itself and set the rank to 0. Example: struct uf_node my_node = UF_INIT_NODE(my_node); or uf_node_init(&my_node); Find the Root Node of union-find ¶ This operation is mainly used to determine whether two nodes belong to the same set in the union-find. If they have the same root, they are in the same set.

During the find operation, path compression is performed to improve the efficiency of subsequent find operations. Example: int connected; struct uf_node *root1 = uf_find(&node_1); struct uf_node *root2 = uf_find(&node_2); if (root1 == root2) connected = 1; else connected = 0; Union Two Sets in union-find ¶ To union two sets in the union-find, you first find their respective root nodes and then link the smaller node to the larger node based on the rank of the root nodes.

Example: uf_union(&node_1, &node_2); ©The kernel development community. | Powered by Sphinx 5.3.0 & Alabaster 0.7.16 | Page source