基于非邻接表实现O(m)时间复杂度的图连通性检测算法设计

常规的DFS/BFS思路之所以达不到O(m)的要求，核心问题是需要遍历所有节点来筛选出邻接节点，最坏时间复杂度会达到O(n²)，我们可以反过来利用非邻接表的有序性，通过维护未访问节点集合的方式优化遍历过程：

核心思路 #

维护一个全局的升序未访问节点集合，每次处理当前连通分量里的节点时，用双指针同时遍历当前节点的有序非邻接表和未访问集合，快速筛选出所有和当前节点有边的未访问节点，直接划入当前连通分量。整个过程只会遍历所有非邻接表元素一次，以及所有节点一次，满足时间复杂度要求。

具体实现步骤 #

• 初始化阶段
  • 将所有1~n的节点按升序存入双向链表unvisited，记录还未被划入任何连通分量的节点
  • 初始化连通分量计数器count = 0
• 遍历处理阶段，直到unvisited为空
  • 取出unvisited的头节点u，连通分量计数count += 1，将u加入遍历队列，同时把u从unvisited中移除
  • 当队列非空时，取出队头节点v：
    • 初始化双指针：p指向v的有序非邻接表头节点，q指向unvisited的头节点
    • 同时遍历两个有序序列：
      • 若q指向的节点值 < p指向的非邻接节点值：说明v和q节点存在边且q未被访问，将q加入当前遍历队列，删除unvisited中的q节点，q向后移动
      • 若q指向的节点值 == p指向的非邻接节点值：说明v和q节点不存在边，p和q同时向后移动
      • 若q指向的节点值 > p指向的非邻接节点值：说明当前p指向的非邻接节点已经被访问过，p向后移动
    • 遍历结束后如果q还未走到unvisited末尾，剩余的所有未访问节点都和v存在边，全部加入遍历队列并清空unvisited
• 结果判断
  • 最终如果count == 1，说明图连通，否则图不连通

复杂度分析 #

所有非邻接表的元素只会被指针p遍历一次，总遍历次数为m；所有节点只会被从unvisited中删除一次，总操作次数为n。题目给定条件m>n，因此整体时间复杂度为O(m)，符合要求。

内容的提问来源于stack exchange，提问作者Muffinlicious