基于邻接表的无向图：删除单个顶点构造正则图的算法需求

嘿，咱们来一步步解决这个问题——要把邻接表实现的无向图，通过删除恰好一个顶点转换成正则图，对吧？下面给你一套实用高效的方案：

核心观察 #

首先得明确：删除顶点v后，所有与v相邻的顶点度数会减1，不相邻的顶点度数保持不变。而正则图要求所有剩余顶点的度数完全相同。

基于这个特性，我们可以先推导删除v后的目标正则度数d：

• 设原图总边数为total_edges，删除v后总边数变为total_edges - deg[v]（deg[v]是v的度数，因为v的每条边都会被移除）
• 剩余顶点数为n-1（n是原图顶点总数），正则图的总边数必须等于d*(n-1)/2，因此可得：
  d = 2*(total_edges - deg[v])/(n-1)
• 这个d必须是非负整数，否则v不可能是符合条件的顶点。

具体算法步骤 #

1. 预处理阶段 #

先对原图做一次遍历，完成以下计算：

• 计算每个顶点的度数，存入数组deg[]
• 计算原图总边数total_edges = sum(deg) // 2（无向图每条边会被两个顶点各统计一次，所以除以2）
• 保留原图的邻接表adj[]，方便后续快速判断顶点间的相邻关系

2. 枚举候选顶点 #

遍历每一个顶点v，按以下步骤验证是否符合条件：

1. 计算删除v后的总边数new_total = total_edges - deg[v]
2. 计算目标度数d：
   • 如果n == 1：删除后为空图，直接判定符合条件（空图默认属于正则图）
   • 否则，检查2*new_total是否能被n-1整除，若不能则跳过该顶点；若能，计算d = 2*new_total // (n-1)，且d必须≥0
3. 验证剩余顶点的度数是否都等于d：
   • 对于所有与v相邻的顶点u，必须满足deg[u] - 1 == d
   • 对于所有与v不相邻的顶点u（u ≠ v），必须满足deg[u] == d
4. 如果所有顶点都满足上述条件，那么v就是我们要找的顶点

优化技巧（降低时间复杂度） #

直接遍历所有顶点验证的时间复杂度是O(n²)，对于大图不够高效。我们可以通过度数频率统计来优化：

• 先统计每个度数出现的次数，存入数组count[]（count[x]表示度数为x的顶点数量）
• 对于候选顶点v，计算出d后，只需满足两个条件：
  1. count[d] + count[d+1] == n-1（除了v，其他顶点的度数只能是d或d+1）
  2. 所有与v相邻的顶点度数都是d+1（因为它们的度数减1后等于d），且相邻顶点的数量等于count[d+1]

这样优化后，总时间复杂度可以降到O(n + m)（m是边数），处理大规模图更高效。

示例演示 #

举个实际例子：
假设无向图有5个顶点，邻接表如下：

• 顶点0：[1, 3, 4]
• 顶点1：[0, 2]
• 顶点2：[1, 3]
• 顶点3：[0, 2]
• 顶点4：[0]

各顶点度数为3, 2, 2, 2, 1，总边数(3+2+2+2+1)/2 = 5。

现在枚举顶点0：

• 删除后总边数5 - 3 = 2，剩余顶点数4
• 计算d = 2*2 /4 = 1，是合法非负整数
• 验证：与0相邻的顶点1、3、4的度数分别是2、2、1，减1后为1、1、0，其中4的新度数0≠1，所以顶点0不符合。

再枚举顶点4：

• 删除后总边数5 -1 =4，剩余顶点数4
• 计算d=2*4/4=2，合法
• 验证：与4相邻的顶点0的度数3-1=2，符合；不相邻的顶点1、2、3度数都是2，符合。因此顶点4就是符合条件的删除对象，删除后剩余4个顶点都是2度，构成2-正则图（环）。

边界情况说明 #

• 当原图只有1个顶点：删除后得到空图，属于正则图
• 当原图已经是正则图：只有当原图是2个顶点的1-正则图（一条边）时，删除其中一个顶点后剩余单个顶点（0-正则图）符合条件；其他正则图删除任意顶点后，相邻顶点度数减1，无法保持所有顶点度数一致。

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