这是一个有趣的问题！

在学术搜索和 Wiki 出现后，我挖掘了 SageMath 的源代码。这让我们明白了这一点：

#A graph is called *cactus graph* if it is connected and every pair of
simple cycles have at most one common vertex.

# Special cases
if self.order() < 4: #Number of vertices
    return True

# Every cactus graph is outerplanar
if not self.is_circular_planar():
    return False

if not self.is_connected():
    return False

# the number of faces is 1 plus the number of blocks of order > 2
B = self.blocks_and_cut_vertices()[0]
return len(self.faces()) == sum(1 for b in B if len(b) > 2) + 1

确定图是否连通是一个O(N)操作。只需在任何节点上启动 DFS，将您访问的节点保存在哈希集中，然后检查您是否访问了所有节点。

您可以使用Boyer 和 Myrvold的O(N)算法检查圆形平面度：

John M. Boyer 和 Wendy J. Myrvold，在尖端：通过边缘添加简化 O(n) 平面度。图算法与应用杂志，卷。8，第 3 期，第 241-273 页，2004 年。

并且可以使用Tarjan的O(N)算法找到块和切割：

重新塔里安。深度优先搜索和线性图算法。暹罗学家计算机。1（2）：146-160（1972）。

您还可以通过注意仙人掌图中的边数最多为$\lfloor1.5(n-1)\rfloor$在哪里$n$是顶点的数量。

如果您有一个找到所有循环的算法，请执行以下步骤：

• 以循环 1 为例，标记属于它的所有边。
• 以循环 2 为例，遍历它的所有边：
  • 如果边缘已经被标记，那么显然该边缘是另一个循环的一部分并且您没有仙人掌
  • 否则，标记该边缘
• 重复循环 3...n