Documentation/translations/zh_CN/core-api/union_find.rst

Source file repositories/reference/linux-study-clean/Documentation/translations/zh_CN/core-api/union_find.rst

File Facts

System
Linux kernel
Corpus path
Documentation/translations/zh_CN/core-api/union_find.rst
Extension
.rst
Size
3130 bytes
Lines
93
Domain
Support Tooling And Documentation
Bucket
Documentation
Inferred role
Support Tooling And Documentation: documentation
Status
atlas-only

Why This File Exists

Repository support layer: documentation, build tooling, samples, user-space helper tools, generated initramfs support, licenses, and validation utilities.

Dependency Surface

Detected Declarations

Annotated Snippet

struct uf_node {
		struct uf_node *parent;
		unsigned int rank;
	};

其中parent为当前节点的父节点，rank为当前树的高度，在合并时将rank小的节点接到rank大
的节点下面以增加平衡性。

初始化并查集
-------------

可以采用静态或初始化接口完成初始化操作。初始化时，parent 指针指向自身，rank 设置
为 0。
示例::

	struct uf_node my_node = UF_INIT_NODE(my_node);

或

	uf_node_init(&my_node);

查找并查集的根节点
------------------

主要用于判断两个并查集是否属于一个集合，如果根相同，那么他们就是一个集合。在查找过程中
会对路径进行压缩，提高后续查找效率。
示例::

	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;

合并两个并查集
--------------

对于两个相交的并查集进行合并，会首先查找它们各自的根节点，然后根据根节点秩大小，将小的
节点连接到大的节点下面。
示例::

	uf_union(&node_1, &node_2);

Annotation

Implementation Notes