如何检测邻接链表无向图的3顶点相邻环及对应算法时间复杂度

问题说明 #

我们要检测的3个相邻顶点构成的环也叫三元环/三角形，即三个顶点两两之间都有边相连，符合a->b->c->a的结构。

检测步骤 #

• 首先给所有顶点赋予全局唯一的数值编号，约定仅检测满足u < v < w的顶点三元组，避免同一个三元环被重复遍历多次，减少冗余计算。
• 遍历所有无向边，仅处理符合u < v的边（无向图的同一条边会在两个顶点的邻接链表中各出现一次，该规则避免重复处理同一条边）。
• 对于每条符合要求的边(u, v)，查找同时存在于u、v的邻接链表中，且编号大于v的顶点w：如果存在任意满足条件的w，说明(u, v, w)构成三元环，即当前图存在符合要求的三顶点环。

优化技巧：可以提前将每个顶点的邻接链表排序，或者转为哈希集合，能大幅提升公共顶点的查找效率。

示例验证 #

题目给出的示例邻接链表如下：

1->2->5
2->3->1->4
3->2->4
4->2->5->3
5->1->4

我们处理边(2, 3)（符合2<3的规则）时，查找两个顶点的公共邻接顶点，且编号大于3的顶点，可以找到4，因此三元环2->3->4->2存在，和示例结果一致。

时间复杂度分析 #

该算法的整体时间复杂度为O(m√m)，其中m为图的边数，推导逻辑如下：

• 我们可以对每条边(u, v)，选择度更小的顶点遍历其邻接表，到度更大的顶点的邻接哈希集合中查找元素，单次查找的时间复杂度为O(1)。
• 度大于√m的顶点最多有√m个，这部分顶点参与的边的处理总开销为O(m√m)；度小于√m的顶点，每条边的处理开销不超过O(√m)，总开销同样为O(m√m)。
• 题目给定边数大于顶点数的前提，该复杂度结论完全适用。

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