算法篇 : 并查集

介绍

        英文名：union find set

        作用：合并集合，查询集合

        合并：将有直接关系的顶点放在一个集合里面

        查找：查询某个顶点所属的集合

        集合的标志：用祖先点的标号作为每个集合的标识

案例 

          如果说将下图的集合2合并至集合1

         那么应该让3的祖先为1，即：

 

实现流程

        1）对所有顶点标号，其祖先节点默认为自己

        2）合并：以两个点中祖先标号小的作为新祖先进行合并

        3）查找：查找点的祖先，并更新查找路径点的祖先

Java代码实现

//顶点类
public class Vertex {public Integer id;public Vertex(Integer id){this.id=id;}
}//并查集的操作类
public class UnionFindSetOperator {private List<Vertex>vertexs;    //所有顶点private List<List<Vertex>>connectVertexs;    //所有有直接关系的顶点private Map<Vertex,Vertex>ancestor;public UnionFindSetOperator(List<Vertex> vertexs, List<List<Vertex>> connectVertexs) {this.vertexs = vertexs;this.connectVertexs = connectVertexs;this.ancestor=new HashMap<>();//将所有顶点的祖先初始化默认设置为自己for(int i=0;i< vertexs.size();i++){ancestor.put(vertexs.get(i),vertexs.get(i));}//合并所有直接相连的顶点for(int i=0;i< connectVertexs.size();i++){Union(connectVertexs.get(i).get(0),connectVertexs.get(i).get(1));}}public void Union(Vertex vertex1,Vertex vertex2){Vertex ancestor1=Find(vertex1);Vertex ancestor2=Find(vertex2);//选取两个祖先id小的作为新祖先if(ancestor1.id<ancestor2.id)ancestor.put(vertex2,ancestor1);elseancestor.put(vertex1,ancestor2);}public Vertex Find(Vertex vertex){if(ancestor.get(vertex)!=vertex){//寻找该节点的祖先Vertex ancestorVertex=Find(ancestor.get(vertex));//如果祖先发生了变化，则更新记录新的祖先if(ancestorVertex!=ancestor.get(vertex))ancestor.put(vertex,ancestorVertex);}//返回其祖先return ancestor.get(vertex);}
}

 

测试函数

//测试函数
public class Main {/*并查集：简述：对集合进行分类合并，方便后续查找实现步骤：1）对所有顶点标号，其祖先节点默认为自己2）合并：以两个点中祖先标号小的作为新祖先进行合并3）查找：查找点的祖先，并更新查找路径点的祖先*/public static void main(String[] args) {//扫描器Scanner scanner=new Scanner(System.in);//存放顶点List<Vertex>vertexs=new LinkedList<>();//有直接关联的顶点List<List<Vertex>>connectVertexs=new LinkedList<>();System.out.println("请输入顶点的数量:");Integer vexcnt= scanner.nextInt();System.out.println("请输入这些顶点的编号");for(int i=0;i<vexcnt;i++){vertexs.add(new Vertex(scanner.nextInt()));}System.out.println("请输入有关系顶点的对数:");Integer connectVertexCnt= scanner.nextInt();System.out.println("请输入有关系顶点的编号:");for(int i=0;i<connectVertexCnt;i++){Integer id1= scanner.nextInt();Integer id2= scanner.nextInt();//获取这两个顶点Vertex v1=null;Vertex v2=null;for(int j=0;j<vertexs.size();j++){if(vertexs.get(j).id==id1)v1=vertexs.get(j);if(vertexs.get(j).id==id2)v2=vertexs.get(j);}LinkedList<Vertex>conVertexs=new LinkedList<>();conVertexs.add(v1);conVertexs.add(v2);connectVertexs.add(conVertexs);}//用并查集的操作类实现这些点的分类和查找UnionFindSetOperator ufs=new UnionFindSetOperator(vertexs,connectVertexs);//查找每一个点的祖先for(int i=0;i<vertexs.size();i++){Vertex ancestor=ufs.Find(vertexs.get(i));System.out.println("顶点:"+vertexs.get(i).id+"的祖先id为:"+ancestor.id);}}
}

自测

        测试模型：

        测试结果：