>

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

🕑
我们可以简单地用一个大小为N项的数组p来记录这个树的森林,其中p[i]记录了第i项的父项,如果p[i]=i,那么i就是这个树的根,也是包含第i项的集合的代表项。

再次看一下上面的可视化图,确定这个数组p里面的值。

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.

🕑
在同一个固定的例子上,你的答案应该是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)”示例作为起点。
另请注意,没有一个例子包含 "非常高 "的树。 在我们描述了所使用的两种启发式方法之后,你很快就会明白其中的原因。
🕑
Initialise(N):创建N个不相交集,所有这些都具有p [i] = i rank[i] = 0(这些等级值最初未示出)。
该操作的时间复杂度非常明显是O(N)。
由于屏幕尺寸的限制,我们设置1≤N≤16。
🕑

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

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

🕑
如果我们执行FindSet(12),我们将立即得到顶点12。如果我们执行FindSet(9),我们将在1步之后得到顶点6,并且没有其他变化。

现在试着执行FindSet(0)。如果这是你对这个默认的并查集例子的第一次调用,它将在2步后返回顶点3,然后由于路径压缩的作用而修改其内部结构(也就是说,顶点0直接指向顶点3)。注意,rank[1]=1的等级值现在是错误的,因为顶点1变成了一个新的叶顶点。然而,我们不会费心去更新它的值。

注意,下次再执行FindSet(0)时,由于路径已经被压缩,速度会快很多。现在,我们假设FindSet(i)的运行速度为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):如果i和j项最初来自两个不相交的集合,我们将较短的树/集合的代表项链接到较高的树/集合的代表项(否则,我们不做任何事情)。这也是在O(1)中完成的。

这就是按等级启发式合并的作用,它将导致产生的树高度相对较短。只有当两棵树在并合前是一样高的(通过启发式比较它们的等级值--注意我们不是在比较它们的实际高度),那么结果树的等级将增加一个单位。
🕑
还要注意的是,UnionSet函数中调用了FindSet函数,所以路径压缩也被间接使用。每次路径压缩压缩路径时,至少有一个等级值是不正确的。我们不需要去修正这些等级值,因为它们只是作为UnionSet函数的指导性启发。
🕑
在同样的默认例子中,尝试UnionSet(9, 12)。由于代表集{6, 9}的树目前比较高(根据rank[6] = 1的值),那么代表集{12}的较短的树将在顶点6下归位,而完全不增加合并后树的高度。
在同样的默认例子中,尝试UnionSet(0, 11)。注意,顶点3和顶点5的等级是相同的 rank[3] = rank[5] = 2。因此,我们可以把顶点3放在顶点5下面(我们的实现),或者把顶点5放在顶点3下面(两种选择都会使合并后树的结果高度增加1)。注意这里间接路径压缩的作用。
🕑

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:1
rank:3
rank:2
rank:5
rank:4

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:1
rank:4
rank:2
rank:5

讨论:为什么?

🕑

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.

🕑

到目前为止,我们说 FindSet(i), IsSameSet(i, j), 和 UnionSet(i, j) 的运行速度为O(1). 实际上,如果UFDS同时采用路径压缩和启发式按等级合并的方法来实现,它们的运行速度为 O(α(N)) 。


这个α(N) 被称为反Ackermann函数,增长速度极慢。对于这种UFDS数据结构的实际使用 (假设 N ≤ 1000000), 我们有 α(1000000) ≈ 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
关于 团队 使用条款 隐私政策

关于

VisuAlgo于2011年由Steven Halim博士创建,是一个允许学生以自己的速度自学基础知识,从而更好地学习数据结构与算法的工具。
VisuAlgo包含许多高级算法,这些算法在Steven Halim博士的书(“Competitive Programming”,与他的兄弟Felix Halim博士合作)和其他书中有讨论。今天,一些高级算法的可视化/动画只能在VisuAlgo中找到。
虽然本网站是专门为新加坡国立大学(NUS)学生学习各种数据结构和算法类(例如CS1010,CS2040,CS3230,CS3233,CS4234)而设,但我们作为在线学习的倡导者,我们非常希望世界各地的好奇的头脑能发现这些非常有用的算法可视化。
VisuAlgo不是从一开始就设计为在小触摸屏(例如智能手机)上工作良好,因为为了满足许多复杂算法可视化,需要大量的像素和点击并拖动手势进行交互。为得到良好的用户体验,最低屏幕分辨率应为1024x768,并且本网站只有首页相对适合移动设备。但是,我们正在测试一个准备在2022年4月发布的移动版本。
VisuAlgo是一个正在进行的项目,更复杂的可视化仍在开发中。
最令人兴奋的发展是自动问题生成器和验证器(在线测验系统),允许学生测试他们的基本数据结构和算法的知识。这些问题是通过一些随机生成的规则,学生的答案会在提交给我们的评分服务器后立即自动分级。这个在线测验系统,当它被更多的世界各地的CS教师采用,应该能从技术上消除许多大学的典型计算机科学考试手动基本数据结构和算法问题。通过在通过在线测验时设置小(但非零)的重量,CS教练可以(显着地)增加他/她的学生掌握这些基本问题,因为学生具有几乎无限数量的可以立即被验证的训练问题他们参加在线测验。培训模式目前包含12个可视化模块的问题。我们将很快添加剩余的12个可视化模块,以便VisuAlgo中的每个可视化模块都有在线测验组件。
VisuAlgo支持三种语言:英语,中文,印尼语。目前,我们还以各种语言写了有关VisuAlgo的公共注释:
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

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

致谢
本项目运营资金是由NUS教学与学习发展中心(CDTL)的教学增进款慷慨提供的。

使用条款

VisuAlgo is free of charge for Computer Science community on earth. If you like VisuAlgo, the only "payment" that we ask of you is for you to tell the existence of VisuAlgo to other Computer Science students/instructors that you know =) via Facebook/Twitter/Instagram/TikTok posts, course webpages, blog reviews, emails, etc.

If you are a data structure and algorithm student/instructor, you are allowed to use this website directly for your classes. If you take screen shots (videos) from this website, you can use the screen shots (videos) elsewhere as long as you cite the URL of this website (https://visualgo.net) and/or list of publications below as reference. However, you are NOT allowed to download VisuAlgo (client-side) files and host it on your own website as it is plagiarism. As of now, we do NOT allow other people to fork this project and create variants of VisuAlgo. Using the offline copy of (client-side) VisuAlgo for your personal usage is fine.

Note that VisuAlgo's online quiz component is by nature has heavy server-side component and there is no easy way to save the server-side scripts and databases locally. Currently, the general public can only use the 'training mode' to access these online quiz system. Currently the 'test mode' is a more controlled environment for using these randomly generated questions and automatic verification for real examinations in NUS.

List of Publications

This work has been presented briefly 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).

This work is done mostly by my past students. 

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 modules 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 module lecturer to keep track of your e-lecture slides reading and online quiz training progresses that is needed to run the module 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 module 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.