什么情况下2个节点还没加入一个集合就已经在一个集合了?就说明如果把这2个节点画进图里连起来,那么一定构成了一个环。
举个简单的栗子
对于join函数,只要加入了2个节点,那么至少这两个节点就构成了1个集合,如果还没加入它们就以及有同一个根节点了那么就说明对应的图里存在环,如果连接这两个节点那么就能形成环。
另外,对于并查集来说,join就是告诉你把n,v节点加入到一个集合里,这个集合最小就是n,v。然后issame就是告诉你n,v,节点是不算属于1个集合。
而且由于每次join和issame都要findf,那么就是会把那个节点及其父节点及其父节点直到根节点全部挂载在根节点上,当然实现是father实现的,不过这个结构是抽象出来的。也叫路径压缩可以快速判断节点的根节点。
一个节点的入度就是指向这个节点的边的个数,出度就是从这个节点出去的边的个数。
对于并查集的操作之一检查树是否成环,就是遍历每一个边然后先判断是否issame,然后再join。一旦issame=1,就说明有成环。当然也可以跳过某一个边去检查,毕竟原理一样,遇到continue了就行。 注意::这里的环是指无向环。
总之 并查集一般用于集合、无向图,可以把两个元素加入1个集合,也可以检查2个元素是否属于1个集合,也可以检查树是否成环。一般情况下不适用于有向图(除了力扣那个冗余连接2它太特殊了首先它本身就是一个树只不过加了一条边而已,有一个情况下,那条边就是指向根节点的,这种情况下等同于无向边,我是这么想的。)
标签:issame,感受,查集,成环,关于,集合,join,节点 From: https://www.cnblogs.com/NiShu7777/p/17780322.html