代码随想录算法训练营第五十天 | 图 | 并查集
Day 50 总结
- 自己实现中遇到哪些困难
- 今日收获，记录一下自己的学习时间
- 15:00 - 16:00
- 18:00 - 19:45
图论
- 深度收缩 & 广度搜索
- BFS, DFS, visited数组, 四个方向
- 并查集
- 数组代表链表, 用集合中的一个元素代表集合的根
- 最小生成树
- 拓扑排序
- 最短路径算法
图论基础
- 图
- 二维空间里，多个点之间相互连接
- 图的种类
- 有向图
- 无向图
- 加权
- 度 Degree
- 连接某个节点的边的数量
- 出度，入度
- 连通性
- 节点联通情况
- 连通图
- 任意两个节点存在一条路径
- 强连通图
- 任务两个节点可以相互到达
- 连通分量
- 独立的连通子图（无向图中的极大连通子图）
- 强连通分量
- 有向图中极大强连通子图称之为该图的强连通分量
- 图的构造
- 邻接表
- 数组 + 链表
- 适用于稀疏图， 空间利用率高
- 邻接矩阵
- 二维数组
- 表达简单，检查连接的速度块，适合稠密图
- 邻接表
- 图的遍历方式
- 深度优先 dfs
- 广度优先 bfs
并查集
理论基础
-
并查集的作用
- 解决连通性的问题，判断两个元素是否在同一个集合里
- 并查集：1.两个元素添加到一个集合中 2.判断两个元素在不在同一个集合
-
原理讲解
- （集合的定义）将两个元素添加到同一个集合中
- （搜索集合）判断两个元素是否在同一个集合中
- 一维连通数组
- father[A] = B，father[B] = C 这样就表述 A 与 B 与 C连通了（有向连通图）
- 通过数组，以元素为下标，寻找找下一个元素，想链表一样
- 但是通过数组可以快速定位元素，并进行链表查询
- 链表的尽头是集合的根 （无所谓根是谁，可以是集合里任意元素）
-
// 将v，u 这条边加入并查集 void join(int u, int v) { u = find(u); // 寻找u的根 v = find(v); // 寻找v的根 if (u == v) return; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回 father[v] = u; } -
// 并查集里寻根的过程 int find(int u) { if (u == father[u]) return u; // 如果根就是自己，直接返回 else return find(father[u]); // 如果根不是自己，就根据数组下标一层一层向下找 } -
// 判断 u 和 v是否找到同一个根 bool isSame(int u, int v) { u = find(u); v = find(v); return u == v; } -
// 并查集初始化 void init() { for (int i = 0; i < n; ++i) { father[i] = i; } }
-
路径压缩
- 将链式搜索过程简化为直接指向根元素
-
// 并查集里寻根的过程 int find(int u) { if (u == father[u]) return u; else return father[u] = find(father[u]); // 路径压缩 }
代码模板
寻找根节点，
函数：find(int u)，也就是判断这个节点的祖先节点是哪个
将两个节点接入到同一个集合，
函数：join(int u, int v)，将两个节点连在同一个根节点上
判断两个节点是否在同一个集合，
函数：isSame(int u, int v)，就是判断两个节点是不是同一个根节点
int n = 1005; // n根据题目中节点数量而定，一般比节点数量大一点就好
vector<int> father = vector<int> (n, 0); // C++里的一种数组结构
// 并查集初始化
void init() {
for (int i = 0; i < n; ++i) {
father[i] = i;
}
}
// 并查集里寻根的过程
int find(int u) {
return u == father[u] ? u : father[u] = find(father[u]); // 路径压缩
}
// 判断 u 和 v是否找到同一个根
bool isSame(int u, int v) {
u = find(u);
v = find(v);
return u == v;
}
// 将v->u 这条边加入并查集
void join(int u, int v) {
u = find(u); // 寻找u的根
v = find(v); // 寻找v的根
if (u == v) return ; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回
father[v] = u;
}拓展
- 按秩（rank）合并，来压缩路径
- rank表示树的高度，进行多个树的合并
- 一定是 rank 小的树合入 到 rank大 的树，这样可以保证最后合成的树rank 最小，降低在树上查询的路径长度。
复杂度分析
路径压缩后的并查集时间复杂度在O(logn)与O(1)之间，且随着查询或者合并操作的增加，时间复杂度会越来越趋于O(1)。
在第一次查询的时候，相当于是n叉树上从叶子节点到根节点的查询过程，时间复杂度是logn，但路径压缩后，后面的查询操作都是O(1)，而 join 函数 和 isSame函数 里涉及的查询操作也是一样的过程
相关题目
107. 寻找存在的路径
题目连接：107. 寻找存在的路径
题目描述：
给定一个包含 n 个节点的无向图中，节点编号从 1 到 n （含 1 和 n ）。
你的任务是判断是否有一条从节点 source 出发到节点 destination 的路径存在。
输入：
N 个节点数, M条边 + node1 <---> node2 + startNode, endNode
输出：
存在路径 start -> end = 1, 不存在 = 0
实现思路：
使用邻接矩阵保存图的信息
DFS 从出发点开始进行路径搜索, 一旦搜索到目标节点, 返回True
也可以使用并查集, 在无向图中, 如果存在一条路径可以通向A到B, 那么他们一定属于一个集合. 反之, 如果在无向图中不存在一条路径连接两个节点, 说明他们在不同的集合分区里面.
但是怎么想要用集合来判断啊, 是因为是无向图, 然后无向图中所有节点都可达, 除非不在一格集合中.
代码实现：
import java.util.Scanner;
public class Main {
public static void main (String[] args) {
/* code */
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int M = in.nextInt();
// 构建邻接矩阵
int[][] graph = new int[N][N];
for (int i=0; i<M; i++) {
int n1 = in.nextInt()-1;
int n2 = in.nextInt()-1;
graph[n1][n2] = 1;
graph[n2][n1] = 1;
}
int startNode = in.nextInt()-1;
int endNode = in.nextInt()-1;
boolean[] visited = new boolean[N];
// dfs进行路径搜索
int result = dfs(graph, startNode, endNode, visited, N);
System.out.println(result);
}
public static int dfs(int[][] graph, int node, int endNode, boolean[] visited, int N) {
if (node == endNode) return 1;
visited[node] = true;
for (int i=0; i<N; i++) {
if (!visited[i] && graph[node][i] == 1) {
if (dfs(graph, i, endNode, visited, N) == 1) return 1;
}
}
return 0;
}
}并查集使用
public class Main {
public static void main (String[] args) {
/* code */
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int M = in.nextInt();
// 并查集
int[] father = new int[N];
init(father);
for (int i=0; i<M; i++) {
int n1 = in.nextInt()-1;
int n2 = in.nextInt()-1;
join(father, n1, n2);
}
int startNode = in.nextInt()-1;
int endNode = in.nextInt()-1;
int res = isSame(father, startNode, endNode) ? 1 : 0;
System.out.println(res);
}
public static void init(int[] father) {
for (int i=0; i<father.length; i++) {
father[i] = i;
}
}
public static int find(int[] father, int ele) {
// while (father[ele] != ele) {
// ele = father[ele];
// }
// return ele;
// if () return ele;
// return find(father, father[ele]);
// return father[ele] == ele ? ele : find(father, father[ele]);
return ele == father[ele] ? ele : (father[ele] = find(father, father[ele]));
}
public static boolean isSame(int[] father, int e1, int e2) {
int f1 = find(father, e1);
int f2 = find(father, e2);
return f1 == f2;
}
public static void join(int[] father, int root, int ele) {
root = find(father, root);
ele = find(father, ele);
if (root == ele) return;
father[ele] = root;
}
}1
题目连接：
题目描述：
输入：
输出：