寻找图中是否存在路径

我们在《并查集》一节详细介绍了并查集这种存储结构，本节趁热打铁，带领读者用并查集解决一个实际问题，即判断图中指定的两个顶点之间是否存在有效的路径。

举个简单的例子，观察下图：

图 1 包含 6 个顶点的图

这是一张包含 6 个顶点的图，其中顶点 1 和顶点 2 是连通的，它们之间存在的有效路径是1-0-2；而顶点 1 和 顶点 5 之间是不连通的，它们之间不存在有效的路径。  

并查集判断图中是否存在路径

判断图中指定的两个顶点之间是否存在有效路径，用并查集解决此问题的思路是：将整张图存储到并查集中，图中相互连接的各个顶点同处一个集合，它们的根结点是相同的。也就是说，对于图中指定的两个顶点，如果他们的根结点相同，就表明它们是连通的，它们之间就一定存在有效的路径；反之如果它们的根结点不同，表明它们处于不同的集合，它们不是连通的，它们之间就不存在有效的路径。

仍以图 1 为例，把整张图（n = 6, edges = [ [0,1], [0,2], [3,5], [5,4], [4,3] ]）存储到并查集中，最终并查集的存储状态如下图所示：

图 2 存储图的并查集

可以看到，下标 0 、1 和 2 位置上存储的根结点都是 0，表明顶点 0、1 和 2 同处一个集合，它们之间是相互连通的；同理，下标 3、4 和 5 位置上存储的根结点都是 3，表明顶点 3、4 和 5 同处一个集合，它们之间是相互连通的。

判断图中两个顶点之间是否存在有效的路径，只需要分别找到两个顶点的根结点，如果它们的根结点相同，表明它们同处一个集合，它们之间就至少存在一条有效的路径；反之如果根结点不同，表明它们身处不同的集合，它们之间不存在有效的路径。

并查集解决图中是否存在路径

下面是用并查集解决“图中是否存在路径”的C语言程序：

1. #include <stdio.h>
2. #include <stdlib.h>
3. 
   
4. typedef enum { false, true } bool;
5. #define MAX_SIZE 1000  // 可以根据需要调整最大尺寸
6. 
   
7. // 并查集数组
8. typedef struct {
9. int parent[MAX_SIZE];
10. int count;
11. }UnionFind;
12. 
    
13. // 初始化并查集
14. void initialize(UnionFind* uf, int size) {
15. for (int i = 0; i < size; i++) {
16.        uf->parent[i] = i;
17. }
18.    uf->count = size;
19. }
20. 
    
21. // 查找根节点（代表元素）
22. int find(UnionFind* uf, int x) {
23. if (uf->parent[x] != x) {
24.        uf->parent[x] = find(uf, uf->parent[x]); // 路径压缩
25. }
26. return uf->parent[x];
27. }
28. 
    
29. // 合并两个元素所在的集合
30. void unionSets(UnionFind* uf, int x, int y) {
31. //找到两个元素所在集合的代表元素
32. int xRoot = find(uf, x);
33. int yRoot = find(uf, y);
34. //如果代表元素不同，表明它们是两个集合，将它们合并
35. if (xRoot != yRoot) {
36.        uf->parent[xRoot] = yRoot; // uf->parent[yRoot] = xRoot;
37.        uf->count--;
38. }
39. }
40. 
    
41. //判断图中是否存在路径，n 表示图中顶点的数量，edgs数组存储的是图中所有的边，len 表示边的数量，source 和 destination 表示要进行判断的两个顶点
42. bool validPath(int n, int(*edgs)[2], int len, int source, int destination) {
43. UnionFind uf;
44. initialize(&uf, n);
45. // 把图存储到并查集中
46. for (int  i = 0; i < len; i++)
47. {
48. unionSets(&uf, edgs[i][0], edgs[i][1]);
49. }
50. //判断 source 和 destination 是否同处一个集合
51. if (find(&uf, source) == find(&uf, destination)) {
52. return true;
53. }
54. else
55. {
56. return false;
57. }
58. }
59. 
    
60. // 主函数
61. int main() {
62. int edgs[5][2] = { {0,1},{0,2},{3,5},{5,4},{4,3} };
63. 
    
64. //判断顶点 1 和 2 之间是否存在有效的路径
65. bool ret = validPath(6, edgs, 5, 1, 2);
66. if (ret == true) {
67. printf("顶点 1 和顶点 2 之间存在有效的路径\n");
68. }
69. else
70. {
71. printf("顶点 1 和顶点 2 不存在有效的路径\n");
72. }
73. 
    
74. //判断顶点 1 和 5 之间是否存在有效的路径
75.    ret = validPath(6, edgs, 5, 1, 5);
76. if (ret == true) {
77. printf("顶点 1 和顶点 5 之间存在有效的路径\n");
78. }
79. else
80. {
81. printf("顶点 1 和顶点 5 不存在有效的路径\n");
82. }
83. 
    
84. return 0;
85. }

下面是用并查集解决“图中是否存在路径”的 Java 程序：

1. // 并查集类，用于处理集合合并和查找操作
2. public class UnionFind {
3. private int[] parent;  // 记录节点的父节点
4. private int count;     // 记录集合的数量
5. 
   
6. // 构造函数，初始化并查集，每个节点的父节点初始为自己，集合数量为节点个数
7. public UnionFind(int size) {
8.        parent = new int[size];
9. for (int i = 0; i < size; i++) {
10.            parent[i] = i;
11. }
12.        count = size;
13. }
14. 
    
15. // 查找根节点（代表元素）的方法，同时进行路径压缩
16. public int find(int x) {
17. if (parent[x] != x) {
18.            parent[x] = find(parent[x]);  // 路径压缩
19. }
20. return parent[x];
21. }
22. 
    
23. // 合并两个元素所在的集合
24. public void unionSets(int x, int y) {
25. int xRoot = find(x);
26. int yRoot = find(y);
27. if (xRoot != yRoot) {
28.            parent[xRoot] = yRoot;  // 合并集合
29.            count--;
30. }
31. }
32. 
    
33. // 获取当前集合的数量
34. public int getCount() {
35. return count;
36. }
37. }
38. 
    
39. // 主程序类，用于测试并查集是否存在有效路径
40. public class ValidPath {
41. // 判断图中是否存在路径的方法
42. public static boolean validPath(int n, int[][] edges, int len, int source, int destination) {
43. UnionFind uf = new UnionFind(n);
44. // 将图存储到并查集中
45. for (int i = 0; i < len; i++) {
46.            uf.unionSets(edges[i][0], edges[i][1]);
47. }
48. // 判断 source 和 destination 是否属于同一个集合
49. return uf.find(source) == uf.find(destination);
50. }
51. 
    
52. // 主函数，用于测试并查集是否能够判断有效路径
53. public static void main(String[] args) {
54. int[][] edges = {{0, 1}, {0, 2}, {3, 5}, {5, 4}, {4, 3}};
55. 
    
56. // 判断顶点 1 和 2 之间是否存在有效的路径
57. boolean ret = validPath(6, edges, 5, 1, 2);
58. if (ret) {
59.            System.out.println("顶点 1 和顶点 2 之间存在有效的路径");
60. } else {
61.            System.out.println("顶点 1 和顶点 2 不存在有效的路径");
62. }
63. 
    
64. // 判断顶点 1 和 5 之间是否存在有效的路径
65.        ret = validPath(6, edges, 5, 1, 5);
66. if (ret) {
67.            System.out.println("顶点 1 和顶点 5 之间存在有效的路径");
68. } else {
69.            System.out.println("顶点 1 和顶点 5 不存在有效的路径");
70. }
71. }
72. }

下面是用并查集解决“图中是否存在路径”的 Python 程序：

1. class UnionFind:
2. def __init__(self, size):
3. # 初始化并查集，每个节点的父节点初始为自己，集合数量为节点个数
4.        self.parent = [i for i in range(size)]
5.        self.count = size
6. 
   
7. def find(self, x):
8. # 查找根节点（代表元素）的方法，同时进行路径压缩
9. if self.parent[x] != x:
10.            self.parent[x] = self.find(self.parent[x])  # 路径压缩
11. return self.parent[x]
12. 
    
13. def union_sets(self, x, y):
14. # 合并两个元素所在的集合
15.        x_root = self.find(x)
16.        y_root = self.find(y)
17. if x_root != y_root:
18.            self.parent[x_root] = y_root  # 合并集合
19.            self.count -= 1
20. 
    
21. def get_count(self):
22. # 获取当前集合的数量
23. return self.count
24. 
    
25. def valid_path(n, edges, source, destination):
26.    uf = UnionFind(n)
27. # 将图存储到并查集中
28. for edge in edges:
29.        uf.union_sets(edge[0], edge[1])
30. # 判断 source 和 destination 是否属于同一个集合
31. return uf.find(source) == uf.find(destination)
32. 
    
33. if __name__ == "__main__":
34.    edges = [[0, 1], [0, 2], [3, 5], [5, 4], [4, 3]]
35. 
    
36. # 判断顶点 1 和 2 之间是否存在有效的路径
37.    ret = valid_path(6, edges, 1, 2)
38. if ret:
39. print("顶点 1 和顶点 2 之间存在有效的路径")
40. else:
41. print("顶点 1 和顶点 2 不存在有效的路径")
42. 
    
43. # 判断顶点 1 和 5 之间是否存在有效的路径
44.    ret = valid_path(6, edges, 1, 5)
45. if ret:
46. print("顶点 1 和顶点 5 之间存在有效的路径")
47. else:
48. print("顶点 1 和顶点 5 不存在有效的路径")

运行程序，输出结果为：

顶点 1 和顶点 2 之间存在有效的路径

顶点 1 和顶点 5 不存在有效的路径