>

>
1x
go to beginning previous frame pause play next frame go to end
并查集(UFDS)数据结构被用来模拟多个不相交集,它能够有效率地(即在几乎常数的时间内)确定一个元素属于哪个集,测试两个元素是否属于同一个集,并在需要时将两个不相交集合并为一个。它可以用来寻找无向图中的连接分量,因此可以作为最小生成树(MST)问题的Kruskal算法的一部分。

Remarks: By default, we show e-Lecture Mode for first time (or non logged-in) visitor.
If you are an NUS student and a repeat visitor, please login.

🕑
在此查看并查集可视化的例子!
每棵树代表一个不相交的集合(因此多个不相交集合能形成一个森林),树的根是这个不相交集合的代表项目。

现在停下来看看当前可视化中的树。 总共有多少项(N)? 有多少个不相交的集合? 每个不相交集的成员是什么? 每个不相交集的代表项是什么?

Pro-tip 1: Since you are not logged-in, you may be a first time visitor (or not an NUS student) who are not aware of the following keyboard shortcuts to navigate this e-Lecture mode: [PageDown]/[PageUp] to go to the next/previous slide, respectively, (and if the drop-down box is highlighted, you can also use [→ or ↓/← or ↑] to do the same),and [Esc] to toggle between this e-Lecture mode and exploration mode.

🕑
由于我们固定了这个电子讲座的默认例子,你的答案应该是。N=13,有4个不相交的集合。{0,1,2,3,4,10}, {5,7,8,11}, {6,9}, {12},下划线的成员是他们自己不相交集合的代表项。

Pro-tip 2: We designed this visualization and this e-Lecture mode to look good on 1366x768 resolution or larger (typical modern laptop resolution in 2021). We recommend using Google Chrome to access VisuAlgo. Go to full screen mode (F11) to enjoy this setup. However, you can use zoom-in (Ctrl +) or zoom-out (Ctrl -) to calibrate this.

🕑

We can simply record this forest of trees with an array p of size N items where p[i] records the parent of item i and if p[i] = i, then i is the root of this tree and also the representative item of the set that contains item i.


Once again, look at the visualization above and determine the values inside this array p.


Discuss: If i is the root of the tree that contains it, can we set p[i] = -1 instead of p[i] = i? What are the implications?


Pro-tip 3: Other than using the typical media UI at the bottom of the page, you can also control the animation playback using keyboard shortcuts (in Exploration Mode): Spacebar to play/pause/replay the animation, / to step the animation backwards/forwards, respectively, and -/+ to decrease/increase the animation speed, respectively.

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.


If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.


FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

🕑
在同一个固定的例子上,你的答案应该是p=[1,3,3,3,5,6,5,5,6,4,8,12],大小N=13,范围从p[0]到p[12]

你可以检查一下,p[3]=3,p[5]=5,p[6]=6,p[12]=12,这与{3,5,6,12}是(它们自己的不相交集)代表项的事实一致。
🕑
我们还在同样大小为N的数组rank中记录额外的等级信息。rank[i]的值是根植于顶点i的子树高度的上限,它将被用作UnionSet(i, j)操作的启发式指导。你会注意到,在 "路径压缩 "(将在后面描述)压缩某些路径后,rank值不再反映该子树的真实高度。

由于有很多项的等级为0,我们对可视化进行了如下设置,以减少杂乱:只有当顶点i的等级大于0时,VisuAlgo才会在顶点i下面以红色文字显示rank[i]的值(简写为一个字符r)。
🕑
在同一个固定的例子上,验证{1,4,6,8}的等级为1,{3,5}的等级为2,其余的等级为0(未显示)。

在这个时间点上,所有的等级值都是正确的,也就是说,它们确实描述了根在该顶点的子树的高度。我们很快就会看到,在接下来的几张幻灯片中,它们并不总是正确的。
🕑
此可视化页面中有五个可用的合并集操作:
示例,Initialize(N)(初始化),FindSet(i)(查找),IsSameSet(i,j)(在同一集),和UnionSet(i,j)(合并)
第一个操作(示例)并不重要:具有各种特殊特征的合并集结构实例列表,供您参考。 此e-Lecture模式始终使用“四个不相交集(Four disjoint sets)”示例作为起点。
另请注意,没有一个例子包含 "非常高 "的树。 在我们描述了所使用的两种启发式方法之后,你很快就会明白其中的原因。
🕑

Initialize(N, M): Create N items and form M disjoint sets with these N items. We randomly pick two disjoint sets and merge them until we have M random disjoint sets. Currently this setup is not random enough, i.e., it cannot create tall trees for example.


The default form is Initialize(N, N), i.e., M = N, all with p[i] = i and rank[i] = 0 (all these rank values are initially not shown). The time complexity of this operation is clearly O(N).


Due to the limitation of screen size, we set 1 ≤ N ≤ 16.

🕑

FindSet(i):从顶点i,递归地在树上往上移动。 也就是说,从顶点i,我们转到顶点p [i]),直到我们找到该树的根,这是该不相交集的的代表项(代表项具有p [i] = i的性质)。

在这个FindSet(i)操作中,我们在每次调用FindSet(i)之后使用路径压缩,因为现在沿着从顶点i到根的路径的每个顶点都知道根是它们的代表项,并且可以用O(1)时间直接指向它 。

🕑

If we execute FindSet(12), we will immediately get vertex 12.
If we execute FindSet(9) we will get vertex 6 after 1 step and no other change.


Now try executing FindSet(0). If this is your first call on this default UFDS example, it will return vertex 3 after 2 steps and then modify the underlying UFDS structure due to path-compression in action (that is, vertex 0 points to vertex 3 directly). Notice that rank value of rank[1] = 1 is now wrong as vertex 1 becomes a new leaf. However, we will not bother to update its value.


Notice that the next time you execute FindSet(0) again, it will be (much) faster as the path has been compressed. For now, we assume that FindSet(i) runs in O(1).

🕑
IsSameSet(i,j):只需检查是否 FindSet(i) == FindSet(j)。 该函数经常出现在Kruskal的MST算法中。 由于它只调用FindSet操作两次,我们假设它的时间复杂度为O(1)。

请注意,FindSet函数在IsSameSet函数内部被调用,因此也间接使用了路径压缩
🕑
如果我们调用IsSameSet(3, 5),我们应该得到false,因为顶点3和顶点5是它们各自不相交集合的代表项,它们是不同的。

现在在相同的默认例子上尝试IsSameSet(0, 11),看看顶点0和顶点11的间接路径压缩。我们应该得到false,因为两个代表项:顶点3和顶点5,是不同的。注意,现在顶点{1,5,8}的等级值是错误的。但我们不会修复它们。
🕑

UnionSet(i, j): If item i and j come from two disjoint sets initially, we link the representative item of the shorter tree/disjoint set to the representative item of the taller tree/disjoint set (otherwise, we do nothing). This is also done in O(1).


This is union-by-rank heuristic in action and will cause the resulting tree to be relatively short. Only if the two trees are equally tall before union (by comparing their rank values heuristically — note that we are not comparing their actual — the current — heights), then the rank of the resulting tree will increase by one unit.

🕑
还要注意的是,UnionSet函数中调用了FindSet函数,所以路径压缩也被间接使用。每次路径压缩压缩路径时,至少有一个等级值是不正确的。我们不需要去修正这些等级值,因为它们只是作为UnionSet函数的指导性启发。
🕑

On the same default example, try UnionSet(9, 12). As the tree that represents disjoint set {6, 9} is currently taller (according to the value of rank[6] = 1), then the shorter tree that represents disjoint set {12} will be slotted under vertex 6, without increasing the height of the combined tree at all.


On the same default example, try UnionSet(0, 11). Notice that the ranks of vertex 3 and vertex 5 are the same rank[3] = rank[5] = 2. Thus, we can either put vertex 3 under vertex 5 (our implementation) or vertex 5 under vertex 3 (both will increase the resulting height of the combined tree by 1). Notice the indirect path-compression heuristic in action.

🕑

Quiz: Starting with N=8 disjoint sets, how tall (heuristically) can the resulting final tree if we call 7 UnionSet(i, j) operations strategically?

rank:3
rank:1
rank:2
rank:4
rank:5

Quiz: Starting with N=8 disjoint sets, how short (heuristically) can the resulting final tree if we call 7 UnionSet(i, j) operations strategically?

rank:3
rank:5
rank:2
rank:1
rank:4

讨论:为什么?

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.


If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.


FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

🕑

So far, we say that FindSet(i), IsSameSet(i, j), and UnionSet(i, j) runs in O(1). Actually they run in O(α(N)) if the UFDS is implemented with both path-compression and union-by-rank heuristics. The analysis is quite involved and is skipped in this visualization.


This α(N) is called the inverse Ackermann function that grows extremely slowly. For practical usage of this UFDS data structure (assuming N ≤ 1M), we have α(1M) ≈ 1.

🕑
您已经完成了这个并查集数据结构的基本内容,我们鼓励您进入探索模式,用您自己的例子探索这个简单而有趣的数据结构。

然而,我们还有一些更有趣的并查集挑战给你。
🕑
请看以下C++/Python/Java/OCaml实现的面向对象编程(OOP)方式并查集实现:unionfind_ds.cpp | py | java | ml
你可以根据自己的需要自由地定制这个实现,因为一些较难的问题需要对这个基本实现进行定制。
我确实希望有一天C++/Python/Java/OCaml/其他编程语言能将这种有趣的数据结构纳入他们的基础库。
🕑
关于这个数据结构的一些更有趣的问题,请在并查集训练模块 上练习。
🕑
即使在通过了这个UFDS模块的在线测验后,你认为你已经真正掌握了这种数据结构吗?

让我们来挑战一下你,让你解决两个需要使用并查集的编程问题:UVa 01329 - Corporative NetworkKattis - Control

请注意,这两个问题都是实际的国际大学生程序设计竞赛(ICPC)问题,也就是说,它们是 "不简单的"。
🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.


If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.


FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

🕑
请注意,并查集数据结构没有 "撤销 "操作。一旦两个不相交的集被合并起来,就不容易再把它们分割成原来的两个集,特别是当路径压缩使合并后的树变平时。

讨论:那么,如果我们需要这种 "拆分 "或 "分割 "或 "切割 "的操作,该怎么做呢?
🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.


If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.


FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.


You have reached the last slide. Return to 'Exploration Mode' to start exploring!

Note that if you notice any bug in this visualization or if you want to request for a new visualization feature, do not hesitate to drop an email to the project leader: Dr Steven Halim via his email address: stevenhalim at gmail dot com.

🕑

例子

Initialise(初始化)

FindSet(查找)

IsSameSet(在同一集)

UnionSet

>

四个不交集

三个不交集

Two disjoint sets

1棵等级4的树

N =

 into

M =

  disjoint sets of rank ≤ 1 

执行

i =

执行

i =
j =

执行

i =
j =

执行

We use cookies to improve our website.
By clicking ACCEPT, you agree to our use of Google Analytics for analysing user behaviour and improving user experience as described in our Privacy Policy.
By clicking reject, only cookies necessary for site functions will be used.

ACCEPT REJECT
关于 团队 使用条款 隐私政策

关于

Initially conceived in 2011 by Dr. Steven Halim, VisuAlgo aimed to facilitate a deeper understanding of data structures and algorithms for his students by providing a self-paced, interactive learning platform.

Featuring numerous advanced algorithms discussed in Dr. Steven Halim's book, 'Competitive Programming' — co-authored with Dr. Felix Halim and Dr. Suhendry Effendy — VisuAlgo remains the exclusive platform for visualizing and animating several of these complex algorithms even after a decade.

While primarily designed for National University of Singapore (NUS) students enrolled in various data structure and algorithm courses (e.g., CS1010/equivalent, CS2040/equivalent (including IT5003), CS3230, CS3233, and CS4234), VisuAlgo also serves as a valuable resource for inquisitive minds worldwide, promoting online learning.

Initially, VisuAlgo was not designed for small touch screens like smartphones, as intricate algorithm visualizations required substantial pixel space and click-and-drag interactions. For an optimal user experience, a minimum screen resolution of 1366x768 is recommended. However, since April 2022, a mobile (lite) version of VisuAlgo has been made available, making it possible to use a subset of VisuAlgo features on smartphone screens.

VisuAlgo remains a work in progress, with the ongoing development of more complex visualizations. At present, the platform features 24 visualization modules.

Equipped with a built-in question generator and answer verifier, VisuAlgo's "online quiz system" enables students to test their knowledge of basic data structures and algorithms. Questions are randomly generated based on specific rules, and students' answers are automatically graded upon submission to our grading server. As more CS instructors adopt this online quiz system worldwide, it could effectively eliminate manual basic data structure and algorithm questions from standard Computer Science exams in many universities. By assigning a small (but non-zero) weight to passing the online quiz, CS instructors can significantly enhance their students' mastery of these basic concepts, as they have access to an almost unlimited number of practice questions that can be instantly verified before taking the online quiz. Each VisuAlgo visualization module now includes its own online quiz component.

VisuAlgo has been translated into three primary languages: English, Chinese, and Indonesian. Additionally, we have authored public notes about VisuAlgo in various languages, including Indonesian, Korean, Vietnamese, and Thai:

id, kr, vn, th.

团队

项目领导和顾问(2011年7月至今)
Dr Steven Halim, Senior Lecturer, School of Computing (SoC), National University of Singapore (NUS)
Dr Felix Halim, Senior Software Engineer, Google (Mountain View)

本科生研究人员 1 (Jul 2011-Apr 2012)
Koh Zi Chun, Victor Loh Bo Huai

最后一年项目/ UROP学生 1 (Jul 2012-Dec 2013)
Phan Thi Quynh Trang, Peter Phandi, Albert Millardo Tjindradinata, Nguyen Hoang Duy

最后一年项目/ UROP学生 2 (Jun 2013-Apr 2014)
Rose Marie Tan Zhao Yun, Ivan Reinaldo

本科生研究人员 2 (May 2014-Jul 2014)
Jonathan Irvin Gunawan, Nathan Azaria, Ian Leow Tze Wei, Nguyen Viet Dung, Nguyen Khac Tung, Steven Kester Yuwono, Cao Shengze, Mohan Jishnu

最后一年项目/ UROP学生 3 (Jun 2014-Apr 2015)
Erin Teo Yi Ling, Wang Zi

最后一年项目/ UROP学生 4 (Jun 2016-Dec 2017)
Truong Ngoc Khanh, John Kevin Tjahjadi, Gabriella Michelle, Muhammad Rais Fathin Mudzakir

最后一年项目/ UROP学生 5 (Aug 2021-Dec 2022)
Liu Guangyuan, Manas Vegi, Sha Long, Vuong Hoang Long

最后一年项目/ UROP学生 6 (Aug 2022-Apr 2023)
Lim Dewen Aloysius, Ting Xiao

最后一年项目/ UROP学生 7 (Aug 2023-Apr 2024)
TBA1, TBA2, TBA3

List of translators who have contributed ≥100 translations can be found at statistics page.

致谢
The birth of this project was made possible by the generous Teaching Enhancement Grant from NUS Centre for Development of Teaching and Learning (CDTL).

使用条款

VisuAlgo is generously offered at no cost to the global Computer Science community. If you appreciate VisuAlgo, we kindly request that you spread the word about its existence to fellow Computer Science students and instructors. You can share VisuAlgo through social media platforms (e.g., Facebook, YouTube, Instagram, TikTok, Twitter, etc), course webpages, blog reviews, emails, and more.

Data Structures and Algorithms (DSA) students and instructors are welcome to use this website directly for their classes. If you capture screenshots or videos from this site, feel free to use them elsewhere, provided that you cite the URL of this website (https://visualgo.net) and/or the list of publications below as references. However, please refrain from downloading VisuAlgo's client-side files and hosting them on your website, as this constitutes plagiarism. At this time, we do not permit others to fork this project or create VisuAlgo variants. Personal use of an offline copy of the client-side VisuAlgo is acceptable.

Please note that VisuAlgo's online quiz component has a substantial server-side element, and it is not easy to save server-side scripts and databases locally. Currently, the general public can access the online quiz system only through the 'training mode.' The 'test mode' offers a more controlled environment for using randomly generated questions and automatic verification in real examinations at NUS.

List of Publications

This work has been presented at the CLI Workshop at the ICPC World Finals 2012 (Poland, Warsaw) and at the IOI Conference at IOI 2012 (Sirmione-Montichiari, Italy). You can click this link to read our 2012 paper about this system (it was not yet called VisuAlgo back in 2012) and this link for the short update in 2015 (to link VisuAlgo name with the previous project).

Bug Reports or Request for New Features

VisuAlgo is not a finished project. Dr Steven Halim is still actively improving VisuAlgo. If you are using VisuAlgo and spot a bug in any of our visualization page/online quiz tool or if you want to request for new features, please contact Dr Steven Halim. His contact is the concatenation of his name and add gmail dot com.

隐私政策

Version 1.1 (Updated Fri, 14 Jan 2022).

Disclosure to all visitors: We currently use Google Analytics to get an overview understanding of our site visitors. We now give option for user to Accept or Reject this tracker.

Since Wed, 22 Dec 2021, only National University of Singapore (NUS) staffs/students and approved CS lecturers outside of NUS who have written a request to Steven can login to VisuAlgo, anyone else in the world will have to use VisuAlgo as an anonymous user that is not really trackable other than what are tracked by Google Analytics.

For NUS students enrolled in courses that uses VisuAlgo: By using a VisuAlgo account (a tuple of NUS official email address, NUS official student name as in the class roster, and a password that is encrypted on the server side — no other personal data is stored), you are giving a consent for your course lecturer to keep track of your e-lecture slides reading and online quiz training progresses that is needed to run the course smoothly. Your VisuAlgo account will also be needed for taking NUS official VisuAlgo Online Quizzes and thus passing your account credentials to another person to do the Online Quiz on your behalf constitutes an academic offense. Your user account will be purged after the conclusion of the course unless you choose to keep your account (OPT-IN). Access to the full VisuAlgo database (with encrypted passwords) is limited to Steven himself.

For other NUS students, you can self-register a VisuAlgo account by yourself (OPT-IN).

For other CS lecturers worldwide who have written to Steven, a VisuAlgo account (your (non-NUS) email address, you can use any display name, and encrypted password) is needed to distinguish your online credential versus the rest of the world. Your account will be tracked similarly as a normal NUS student account above but it will have CS lecturer specific features, namely the ability to see the hidden slides that contain (interesting) answers to the questions presented in the preceding slides before the hidden slides. You can also access Hard setting of the VisuAlgo Online Quizzes. You can freely use the material to enhance your data structures and algorithm classes. Note that there can be other CS lecturer specific features in the future.

For anyone with VisuAlgo account, you can remove your own account by yourself should you wish to no longer be associated with VisuAlgo tool.