连接性问题
问题概述
让我们先看看图片
在连接或断开的这个点网络中，可以找到从P点到Q点的路径。可以抽象为连接问题，包括在计算机网络中判断两台主机是否连接在一起，以及在社交网络中两个用户是否有间接社交关系。
问题抽象
网络上的点(主机、人)可以抽象成对象，p-q表示P连接到Q，连接关系可以传递。p-q q-r=p-r；为了简要说明问题，如果将两个对象标记为整数对，则指定的整数对序列将描述点网络。
下图中的节点数N=5网络(使用0 ~ N-1表示对象)可以用整数对序列0-1 1-3 2-4来说明连接关系。其中0和3也连接在一起，有两个连接组件，{0，1，3}和{
问题：将描述连接关系的整数对序列指定为两个整数P和Q，以确认是否可以连接。
问题的例子
输入未连接
3-4 3-4
4-9 4-9
8-0 8-0
2-3 2-3
5-6 5-6
2-9 2-3-4-9
5-9 5-9
7-3 7-3
4-8 4-8
5-6 5-6
0-2 0-8-4-3-2
6-1 6-1
相应的连接图如下：黑线表示两个节点次连接，绿线表示两个节点已经有连接关系。
算法1:快速搜索算法
使用阵列id[i]储存节点值。I是节点序号。也就是说，初始状态序列号和数组值相同。
输入前两个连接后，id[i]将更改为：
Id[i]的值表示连接完成后I是连接的结束节点。如果连接了p和q，则id[p]和id[q]的值必须相同。
4-9完成后，id[3]和id[4]的值都是结束节点9。这时直接判断3和9是否连接，id[3]和id[9]的值是否相同，如果相同，是否连接，如果不相同，是否存在连接关系。显然，id[3]==id[9]==9意味着存在连接关系。
算法实现
/* * file 3360 1.1-quick _ find . go */
Package main
Import.
Const N=10
Var id [N]int
Func main() {
reader :=buf io . new reader(OS . stdin)
//初始化元素值与节点序列号相同的id数组
FOR I :=0；I N；I {
Id[i]=I
}
//读取命令行输入
For {
Data，_，_ :=reader。ReadLine()
Str:=string(数据)
If str==' \ n ' {
Continue
}
If str==' # ' {
布雷克
}
Values :=字串。Split(str，')。
p，_ :=strconv.atoi(值[0])
q，_ :=strconv.atoi(值[1])
If Connected(p，q) {
FMT . Printf(“Already连接节点3360% d-%d \ n”，P，Q)
Continue
}
union(p，q)
}
}
//决定整数p和q的节点是否连接在一起
Func Connected(p，q int) bool {
Return id[p]==id[q]
}
//连接的p-q节点
Func Union(p，q int) {
Pid :=id[p]
Qid :=id[q]
重复//id阵列，将值为id[p]的所有节点替换为id[q]
FOR I :=0；I N；I {
If id[i]==PID {
Id[i]=qid
}
}
Fmt.printf(“未连接节点3360% d-%d \ n”，P，Q)
}
运营效果：可以判断2-9已经连接。
复杂性
快速查找算法在判断P和Q是否连接时，只需要判断id[p]和id[q]是否相同即可。但是，当P和Q不连接时合并，因此每次合并时都需要遍历整个数组。特性：快速查找，缓慢合并
算法2:快速合并算法
概述
每次合并时，快速查找算法都会完全遍历数组，使其效率低下。如果不每次遍历id[]，而是优化数组中的部分值，则复杂性会降低。
这时要考虑树形结构。在连接关系的传递性上，p-r q-r=p-q可以看作root，P和Q可以看作子点。因为P和Q有相同的根R，所以P和Q是相连的。这里的树是连接关系的抽象。
数据结构
要将数组用作树实现，请执行以下操作：
节点阵列id[N]，id[i]储存I的父节点
I的根节点是ID[ID].id[i].]。父节点的父节点.根节点(父节点是自身)
使用树的好处
将整数到序列表示从数组更改为树，每个节点存储父节点的位置。这个树有两个优点。
请检查p和q是否连接：是否存在同一个根节点
从p合并到q:将p的根节点更改为q的根节点(快速合并，无需整个遍历)
示例：
对于上述整数对序列，查找、合并过程如下：橙色是合并操作，灰色是连接状态，绿色是存储树的阵列。
红色2-3不是直接使用2作为3的子节点，而是找到3的根节点9，合并2-3和3-4-9，生成2-9
算法实现：
/* *文件3360 1.2-quick _ union.go */
//p和q具有相同的根节点，并且已连接。
Func Connected(p，q int) bool {
Return getRoot(p)==getRoot(q)
}
//连接的p-q节点
Func Union(p，q int) {
PRoot :=getRoot(p)
QRoot :=getRoot(q)
Id[pRoot]=qRoot //q树的根现在有父节点(p树的根)以完成合并
Fmt.printf(“未连接节点3360% d-%d \ n”，P，Q)
}
获取//节点I的根节点
Func getRoot(i int) int {
//在没有根节点的情况下继续向上查找
For I！=id[i] {
I=id[i]
}
Return I
}
算法3:具有权值的快速合并算法
概述
快速合并算法有一个缺陷。数据量大时，随机合并子树会提高树，在找到根节点时，需要遍历数组的大部分值。还是很慢。在下图中，如果判断P，Q是否连接，则需要找到13个节点。
如果树合并后仍然变短，子树之间保持平衡，则找到根节点后，少遍历很多节点，检查下图中是否连接了P、Q，只需要找到7个节点。
构建平衡树
要想构建平衡的树，合并时要将小树合并到大树上，不要让合并的树慢慢上升或上升，从而大大减少大部分合并需要通过的节点。(大卫亚设，Northern Exposure(美国电视剧)，女性)区分小树，大树使用树的权重。子树包含节点数。
数据结构
树节点的存储仍然使用id[i]，但需要额外的数组大小[i]来记录节点I的子节点数。
算法实现
/* *
文件： 1.3-weighted _ version.go
基于快速合并算法，合并操作将小树合并为大树即可
*/
Var id [N]int
Var size [N]int
Func main() {
//初始化元素值与节点序列号相同的id数组
FOR I :=0；I N；I {
Id[i]=I
大小[I]=I
}
.
}
.
//连接的p-q节点
Func Union(p，q int) {
PRoot :=getRoot(p)
QRoot :=getRoot(q)
//p树是大树
If size[pRoot] size[qRoot] {
Id[pRoot]=qRoot根
Size[qRoot]=size[pRoot]
} else {
Id[qRoot]=id[pRoot]
Size[pRoot]=size[qRoot]
}
Id[pRoot]=qRoot //q树的根现在有父节点(p树的根)以完成合并
Fmt.printf(“未连接节点3360% d-%d \ n”，P，Q)
}
算法4:路径压缩的加权快速合并算法
概述
加权快速合并算法即使大部分整数对都是直接连接的，结果树也仍然像序列一样高。
10-8 8-6 11-9 12-9 9-6 6-3 7-3 3-1 4-1 5-1 1-0 2-0
结果树如下：
此时，要判断9-2的连接关系，必须分别找到9和2的根节点。找到9的根节点时，它会经过6，3，1树。6、3和1树的子节点与9一样，根节点都是0，因此将6、3和1树直接更改为0的子树。下面是：
优化
每次计算节点的根节点时，沿路径检查的节点也指向根节点。如果尽可能地展平树，则在检查连接状态时巡回的节点数将大幅减少。
算法实现
/* *
file 3360 1.4-path _ compression _ by _ halving . go
更改的代码很少，但很精致
*/
获取//节点I的根节点
Func getRoot(i int) int {
//在没有根节点的情况下继续向上查找
For I！=id[i] {
Id [I]=id [id [I]//节点，继续向上移动，直到节点的父节点连接到根节点为止
I=id[i]
}
Return I
}
复杂性
n是节点集合的大小，t是树的高度。
算法初始化的复杂性集成复杂性检索复杂性
快速查找N N(完整遍历)1(数组值比较)
快速合并遍历树(N T)遍历树(T)
具有加权的快速合并N LG N LG N
路径压缩的权重将n快速合并到接近1(树的高度接近2)。
摘要
如上所述，有四种算法可以解决连接问题，从效率低下的基本功能的快速搜索到复杂性接近1的路径压缩带的快速合并。算法可以学习解决程序问题的一般步骤。也就是说，您可以完成基本功能，然后针对效率低下的任务进行优化，从而降低复杂性。