lEsphinx.addnodesdocument)}( rawsourcechildren]( translations LanguagesNode)}(hhh](h pending_xref)}(hhh]docutils.nodesTextEnglish}parenthsba attributes}(ids]classes]names]dupnames]backrefs] refdomainstdreftypedoc reftarget/core-api/union_findmodnameN classnameN refexplicitutagnamehhh ubh)}(hhh]hChinese (Traditional)}hh2sbah}(h]h ]h"]h$]h&] refdomainh)reftypeh+ reftarget'/translations/zh_TW/core-api/union_findmodnameN classnameN refexplicituh1hhh ubh)}(hhh]hItalian}hhFsbah}(h]h ]h"]h$]h&] refdomainh)reftypeh+ reftarget'/translations/it_IT/core-api/union_findmodnameN classnameN refexplicituh1hhh ubh)}(hhh]hJapanese}hhZsbah}(h]h ]h"]h$]h&] refdomainh)reftypeh+ reftarget'/translations/ja_JP/core-api/union_findmodnameN classnameN refexplicituh1hhh ubh)}(hhh]hKorean}hhnsbah}(h]h ]h"]h$]h&] refdomainh)reftypeh+ reftarget'/translations/ko_KR/core-api/union_findmodnameN classnameN refexplicituh1hhh ubh)}(hhh]hSpanish}hhsbah}(h]h ]h"]h$]h&] refdomainh)reftypeh+ reftarget'/translations/sp_SP/core-api/union_findmodnameN classnameN refexplicituh1hhh ubeh}(h]h ]h"]h$]h&]current_languageChinese (Simplified)uh1h hh _documenthsourceNlineNubhcomment)}(h SPDX-License-Identifier: GPL-2.0h]h SPDX-License-Identifier: GPL-2.0}hhsbah}(h]h ]h"]h$]h&] xml:spacepreserveuh1hhhhhhT/var/lib/git/docbuild/linux/Documentation/translations/zh_CN/core-api/union_find.rsthKubhnote)}(hX{此文件的目的是为让中文读者更容易阅读和理解，而不是作为一个分支。 因此， 如果您对此文件有任何意见或更新，请先尝试更新原始英文文件。 如果您发现本文档与原始文件有任何不同或者有翻译问题，请发建议或者补丁给 该文件的译者，或者请求中文文档维护者和审阅者的帮助。h]h paragraph)}(hX{此文件的目的是为让中文读者更容易阅读和理解，而不是作为一个分支。 因此， 如果您对此文件有任何意见或更新，请先尝试更新原始英文文件。 如果您发现本文档与原始文件有任何不同或者有翻译问题，请发建议或者补丁给 该文件的译者，或者请求中文文档维护者和审阅者的帮助。h]hX{此文件的目的是为让中文读者更容易阅读和理解，而不是作为一个分支。 因此， 如果您对此文件有任何意见或更新，请先尝试更新原始英文文件。 如果您发现本文档与原始文件有任何不同或者有翻译问题，请发建议或者补丁给 该文件的译者，或者请求中文文档维护者和审阅者的帮助。}(hhhhhNhNubah}(h]h ]h"]h$]h&]uh1hh5Documentation/translations/zh_CN/disclaimer-zh_CN.rsthKhhubah}(h]h ]h"]h$]h&]uh1hhhhhhhhNubh field_list)}(hhh]hfield)}(hhh](h field_name)}(hOriginalh]hOriginal}(hhhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhhhKubh field_body)}(h&Documentation/core-api/union_find.rst h]h)}(h%Documentation/core-api/union_find.rsth]h%Documentation/core-api/union_find.rst}(hhhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhhubah}(h]h ]h"]h$]h&]uh1hhhubeh}(h]h ]h"]h$]h&]uh1hhhhKhhhhubah}(h]h ]h"]h$]h&]uh1hhhhhhhhKubhsection)}(hhh](htitle)}(h$Linux中的并查集（Union-Find）h]h$Linux中的并查集（Union-Find）}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjhhhhhKubh)}(hhh](h)}(hhh](h)}(h日期h]h日期}(hj,hhhNhNubah}(h]h ]h"]h$]h&]uh1hhj)hhhKubh)}(h2024年6月21日h]h)}(hj<h]h2024年6月21日}(hj>hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK hj:ubah}(h]h ]h"]h$]h&]uh1hhj)ubeh}(h]h ]h"]h$]h&]uh1hhhhK hj&hhubh)}(hhh](h)}(h作者h]h作者}(hjZhhhNhNubah}(h]h ]h"]h$]h&]uh1hhjWhhhKubh)}(hXavier h]h)}(hXavier h](hXavier <}(hjlhhhNhNubh reference)}(hxavier_qy@163.comh]hxavier_qy@163.com}(hjvhhhNhNubah}(h]h ]h"]h$]h&]refurimailto:xavier_qy@163.comuh1jthjlubh>}(hjlhhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhK hjhubah}(h]h ]h"]h$]h&]uh1hhjWubeh}(h]h ]h"]h$]h&]uh1hhhhK hj&hhubeh}(h]h ]h"]h$]h&]uh1hhjhhhhhK ubj)}(hhh](j)}(h$何为并查集，它有什么用？h]h$何为并查集，它有什么用？}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjhhhhhKubhdefinition_list)}(hhh]hdefinition_list_item)}(hX并查集是一种数据结构，用于处理一些不交集的合并及查询问题。并查集支持的主要操作： 初始化：将每个元素初始化为单独的集合，每个集合的初始父节点指向自身。 查询：查询某个元素属于哪个集合，通常是返回集合中的一个“代表元素”。这个操作是为 了判断两个元素是否在同一个集合之中。 合并：将两个集合合并为一个。 h](hterm)}(hx并查集是一种数据结构，用于处理一些不交集的合并及查询问题。并查集支持的主要操作：h]hx并查集是一种数据结构，用于处理一些不交集的合并及查询问题。并查集支持的主要操作：}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhhhKhjubh definition)}(hhh](h)}(hf初始化：将每个元素初始化为单独的集合，每个集合的初始父节点指向自身。h]hf初始化：将每个元素初始化为单独的集合，每个集合的初始父节点指向自身。}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhjubj)}(hhh]j)}(h查询：查询某个元素属于哪个集合，通常是返回集合中的一个“代表元素”。这个操作是为 了判断两个元素是否在同一个集合之中。 h](j)}(hx查询：查询某个元素属于哪个集合，通常是返回集合中的一个“代表元素”。这个操作是为h]hx查询：查询某个元素属于哪个集合，通常是返回集合中的一个“代表元素”。这个操作是为}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhhhKhjubj)}(hhh]h)}(h6了判断两个元素是否在同一个集合之中。h]h6了判断两个元素是否在同一个集合之中。}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhjubah}(h]h ]h"]h$]h&]uh1jhjubeh}(h]h ]h"]h$]h&]uh1jhhhKhjubah}(h]h ]h"]h$]h&]uh1jhjubh)}(h*合并：将两个集合合并为一个。h]h*合并：将两个集合合并为一个。}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhjubeh}(h]h ]h"]h$]h&]uh1jhjubeh}(h]h ]h"]h$]h&]uh1jhhhKhjubah}(h]h ]h"]h$]h&]uh1jhjhhhhhNubh)}(hX并查集作为一种用于维护集合（组）的数据结构，它通常用于解决一些离线查询、动态连通性和 图论等相关问题，同时也是用于计算最小生成树的克鲁斯克尔算法中的关键，由于最小生成树在 网络路由等场景下十分重要，并查集也得到了广泛的引用。此外，并查集在符号计算，寄存器分 配等方面也有应用。h]hX并查集作为一种用于维护集合（组）的数据结构，它通常用于解决一些离线查询、动态连通性和 图论等相关问题，同时也是用于计算最小生成树的克鲁斯克尔算法中的关键，由于最小生成树在 网络路由等场景下十分重要，并查集也得到了广泛的引用。此外，并查集在符号计算，寄存器分 配等方面也有应用。}(hj9hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhjhhubh)}(h(空间复杂度: O(n)，n为节点数。h]h(空间复杂度: O(n)，n为节点数。}(hjGhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhjhhubh)}(hXM时间复杂度：使用路径压缩可以减少查找操作的时间复杂度，使用按秩合并可以减少合并操作的 时间复杂度，使得并查集每个查询和合并操作的平均时间复杂度仅为O(α(n))，其中α(n)是反阿 克曼函数，可以粗略地认为并查集的操作有常数的时间复杂度。h]hXM时间复杂度：使用路径压缩可以减少查找操作的时间复杂度，使用按秩合并可以减少合并操作的 时间复杂度，使得并查集每个查询和合并操作的平均时间复杂度仅为O(α(n))，其中α(n)是反阿 克曼函数，可以粗略地认为并查集的操作有常数的时间复杂度。}(hjUhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK hjhhubh)}(hw本文档涵盖了对Linux并查集实现的使用方法。更多关于并查集的性质和实现的信息，参见：h]hw本文档涵盖了对Linux并查集实现的使用方法。更多关于并查集的性质和实现的信息，参见：}(hjchhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK$hjhhubh block_quote)}(hX维基百科并查集词条 https://en.wikipedia.org/wiki/Disjoint-set_data_structure h]j)}(hhh]j)}(hV维基百科并查集词条 https://en.wikipedia.org/wiki/Disjoint-set_data_structure h](j)}(h维基百科并查集词条h]h维基百科并查集词条}(hj~hhhNhNubah}(h]h ]h"]h$]h&]uh1jhhhK'hjzubj)}(hhh]h)}(h9https://en.wikipedia.org/wiki/Disjoint-set_data_structureh]ju)}(hjh]h9https://en.wikipedia.org/wiki/Disjoint-set_data_structure}(hjhhhNhNubah}(h]h ]h"]h$]h&]refurijuh1jthjubah}(h]h ]h"]h$]h&]uh1hhhhK'hjubah}(h]h ]h"]h$]h&]uh1jhjzubeh}(h]h ]h"]h$]h&]uh1jhhhK'hjwubah}(h]h ]h"]h$]h&]uh1jhjsubah}(h]h ]h"]h$]h&]uh1jqhhhK&hjhhubeh}(h]id1ah ]h"]$何为并查集，它有什么用？ah$]h&]uh1jhjhhhhhKubj)}(hhh](j)}(h并查集的Linux实现h]h并查集的Linux实现}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjhhhhhK*ubh)}(hxLinux的并查集实现在文件“lib/union_find.c”中。要使用它，需要 “#include ”。h]hxLinux的并查集实现在文件“lib/union_find.c”中。要使用它，需要 “#include ”。}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK,hjhhubh)}(h&并查集的数据结构定义如下::h]h%并查集的数据结构定义如下:}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK/hjhhubh literal_block)}(hNstruct uf_node { struct uf_node *parent; unsigned int rank; };h]hNstruct uf_node { struct uf_node *parent; unsigned int rank; };}hjsbah}(h]h ]h"]h$]h&]hhuh1jhhhK1hjhhubh)}(h其中parent为当前节点的父节点，rank为当前树的高度，在合并时将rank小的节点接到rank大 的节点下面以增加平衡性。h]h其中parent为当前节点的父节点，rank为当前树的高度，在合并时将rank小的节点接到rank大 的节点下面以增加平衡性。}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK6hjhhubeh}(h]linuxah ]h"]并查集的linux实现ah$]h&]uh1jhjhhhhhK*ubj)}(hhh](j)}(h初始化并查集h]h初始化并查集}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjhhhhhK:ubh)}(h可以采用静态或初始化接口完成初始化操作。初始化时，parent 指针指向自身，rank 设置 为 0。 示例::h]h可以采用静态或初始化接口完成初始化操作。初始化时，parent 指针指向自身，rank 设置 为 0。 示例:}(hj+hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK