Introduction
I learn from my college classmates in class of 70141 of Shanghai Jiaotong University. Write down every word the teacher says in the lecture, that is long time ago, from 1984 to 1988. We have 7 girls in class of 70141, and some of girls worked so hard to learn mathematics and one of good habit was to discuss home work together before the light turned off in the evening. At that time I do not know how hard it is to write down clean notes after each class.
I like to spend at least 30 minutes to write down the notes about this union find algorithm written in Chinese. The blog is here.
Learn union find
First let me learn take down some notes in Chinese.
Dynamic connected - 动态连通性
Union-Find - 并查集
How to model the problems? - 对问题建模
There are two solutions. One is to find path in between, using DFS algorithm. The second one is no need to find path in between, using union find algorithm.
建模思路：
最简单而直观的假设是，对于连通的所有节点，我们可以认为它们属于一个组，因此不连通的节点必然就属于不同的组。随着Pair的输入，我们需要首先判断输入的两个节点是否连通。如何判断呢？按照上面的假设，我们可以通过判断它们属于的组，然后看看这两个组是否相同，如果相同，那么这两个节点连通，反之不连通。为简单起见，我们将所有的节点以整数表示，即对N个节点使用0到N-1的整数表示。而在处理输入的Pair之前，每个节点必然都是孤立的，即他们分属于不同的组，可以使用数组来表示这一层关系，数组的index是节点的整数表示，而相应的值就是该节点的组号了。该数组可以初始化为：
for( int i = 0; i < size; i++)
id[i] = i;
即对于节点i，它的组号也是i。
My own notes
Quick-find algorithm, C# class is here.
Quick-union algorithm, C# class is here.
Understand what is quick in quick-union algorithm:
No comments:
Post a Comment