考研数据结构之并查集

发表于

小知识，大挑战！本文正在参与“程序员必备小知识”创作活动

image.png
漏网之鱼：逻辑结构——“集合”

逻辑结构——数据元素之间的逻辑关系是什么？

集合的两个基本操作——“并”和“查”

Find ——“查”操作：确定一个指定元 素所属集合
Union ——“并”操作：将两个不想交 的集合合并为一个
注：并查集（Disjoint Set）是逻辑结 构——集合的一种具体实现，只进行 “并”和“查”两种基本操作

image.png

image.png

image.png

image.png
如何“查”到一个元素到底属于哪一个集合？ —— 从指定元素出发，一路向北，找到根节点
如何判断两个元素是否属于同一个集合？
—— 分别查到两个元素的根，判断根节点是否相同即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
c++复制代码#include<iostream>
using namespace std;
#define SIZE 13

int UFSets[SIZE];   //集合元素组 

//初始化并查集
void Initial(int S[]){
	for(int i=0;i<SIZE;i++)
		S[i]=-1;
} 

//Find "查"操作，找X所属集合（返回X所属根结点）
int Find(int S[],int X){
	while(S[X]>=0)			//循环寻找X的根 
		X=S[X];
	return X;
}


//Union "并"操作，讲两个集合合并为一个
void Union(int S[],int Root1,int Root2){
	//要求Root1与Root2是不同集合
	
	if(Root1==Root2)	return;
	
	//将根Root2连接到另一根Root1下面
	
	S[Root2]=Root1; 
		 
}


//Union "并"操作，小树合并到大树
void Union1(int S[],int Root1,int Root2){
	if(Root1==Root2)	return;
	if(S[Root2]>S[Root1]){
		S[Root1]+=S[Root2];
		S[Root2]=Root1;		//小树合并到大树 
	}else{
		S[Root2]+=S[Root1];
		S[Root1]=Root2;
		 
	} 
} 

//用并查集判断一个图有几个连通分量（图用邻接矩阵表示）
 int ComponentCount(int g[5][5]){
 	//g[5][5]是一个二维数组表示的邻接矩阵
	 int S[5];
	 for(int i=0;i<5;i++) S[i]=-1;	//定义，初始化并查集
	 
	 for(int i=0;i<5;i++)
	 	for(int j=i+1;j<5;j++)
		 if(g[i][j]>0){
		 
		 	int iRoot=Find(S,i);	
			int jRoot=Find(S,j);
			if(iRoot!=jRoot)
				Union1(S,iRoot,jRoot); 
		 
		}
	 
		 
	int count=0;
	for(int i=0;i<5;i++)
		if(S[i]<0)	count++;
		return count;	 
		 	  
 } 

//用并查集判断一个图是否有环（图用邻接矩阵表示）
int hasAcyclic(int g[5][5]){
	//g[5][5]是一个二维数组表示的邻接矩阵
	int S[5];	//初始化并查集
	for(int i=0;i<5;i++)	S[i]=-1;
	for(int i=0;i<5;i++)
		for(int j=i+1;j<5;j++)
			if(g[i][j]>0){
				int iRoot=Find(S,i);
				int jRoot=Find(S,j);
				if(iRoot!=jRoot)
					Union(S,iRoot,jRoot);
				else
					return 1;//在一个连通子图中，但凡再多一条边，必有环 
			}
	return 0;//图中没环		 
}

int main(){
		
	return 0;
}

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%