1回答

liuyubobobo

2020-04-05

已采纳

课程中举了这样一个例子，就是并查集使用的典型场景：已知很多点，和点与点之间的连接关系（进行 union 操作），查询两点之间是否连通？（执行 isConnected 操作。）】

这是一个抽象模型，具体在一个问题中，点和边可能代表不同的意义。

比如每个点是一个人，每个边表示两个人认识；那么，通过并查集，我们就可以快速查找，任意两个人之间是否可能经过“朋友介绍”，认识彼此？

再比如每个点可能表示一个地方，每个边表示两个地方之间存在交通，通过并查集，我们也可以快速查找两个地方之间是否可达。

在 Leetcode 上，专门有一个问题分类，是并查集，如果对此感兴趣，可以看看这个分类下的问题：https://leetcode.com/tag/union-find/

另外，求解最小生成树的 Kruskal 算法，要想做到最优，也必须使用并查集，这在我的图论课程中有详细介绍，有兴趣可以参考：https://coding.imooc.com/class/370.html

继续加油！：）

0

1

car

老师说的很好，收益匪浅

2020-04-05

共1条回复