Union-Find

文章目录

1. 1. Steps to developing a usable algorithm
2. 2. dynamic connectivity
   1. 2.1. Given a set of N objects.
   2. 2.2. Modeling the object

Steps to developing a usable algorithm

1. first step is to model the problem

   Try to understand, basically, what are the main elements of the problem that need to be solved

2. Find an algorithm to solve it.

3. Fast enough? Fits in memory?

   if not ,fiugre out why.

   find a way to address the problem.

4. lterate until satisfied.

---

dynamic connectivity

So, first we’ll talk about the dynamic connectivity动态连接性 problem, the model of the problem for union find.

Given a set of N objects.

• Union Command:

  connect two objects.

• Find/connected query:

  is there a path connecting the two objects?

union(n,x) 中的两个参数n,x2个数相连

connected(j,k)判断j,k两个目标是否能相连

Q. Is there there a path connecting p and q?

Modeling the object

• Pixels in digital photo.
• Computers in a network.
• Friends in a social network.
• Transistors in a computer chip.
• Elements in a mathematical set.
• Variable names in Fortran program
• Metallic sites in a composite system.