提出背景 在图论问题中,我们经常性遇到一些关于两个点是否连通的问题。 比如在最小生成树kruskal算法中,我们在逐渐选取最小边的时候,我们需要判断当前要选的边的两个顶点是否已经在同一连通块中。 有基础的同学都知道,在大多数图论问题中,我们的图都是通过邻接表或点对表示边而非邻接矩阵存储的,这样能够提高遍历和存储的时间和空间效率。但实际上,这两种方式也有一个严重的缺陷:不方便查询、修改指定的两点u和v的关系。于是在这种情况下的这两种方式构成的图的连通性也非常难以判断。 这时我们需要一种数据结构能够方便的维护查询图的连…

2020年02月12日 0条评论 243点热度 0人点赞 阅读全文