求解带空间位置约束的不连通图最小节点添加连通算法

现有一图，每个节点具备(x,y)空间位置，节点间仅当处于同一竖直线（xAxB）或水平线（yAyB）时存在边，部分节点因无同x或同y的节点而孤立。需求是计算需添加最少节点数，使图完全连通（任意节点间可达）。

示例代码 #

import networkx as nx

G = nx.Graph()

# 添加竖线x=1上的节点
G.add_node(1, pos=(1,1))
G.add_node(2, pos=(1,2))
G.add_node(3, pos=(1,3))
G.add_node(4, pos=(1,4))
G.add_node(5, pos=(1,5))

# 添加水平线y=1上的节点
G.add_node(6, pos=(2,1))
G.add_node(7, pos=(3,1))
G.add_node(8, pos=(4,1))

# 添加孤立或半孤立节点
G.add_node(9, pos=(5,3))
G.add_node(10, pos=(6,7))
G.add_node(11, pos=(10,6))

# 添加现有边
G.add_edge(1,2)
G.add_edge(2,3)
G.add_edge(3,4)
G.add_edge(4,5)

G.add_edge(1,6)
G.add_edge(6,7)
G.add_edge(7,8)

G.add_edge(3,9)

# 获取节点位置并绘图
pos = nx.get_node_attributes(G, 'pos')
nx.draw(G, pos)

示例图说明 #

示例图包含4个连通分量：

• 由节点1-8构成的连通块（x=1的竖线与y=1的横线交叉相连）
• 节点9（仅与节点3相连）
• 节点10（无相邻节点）
• 节点11（无相邻节点）

核心思路：转化为二分图连通性问题 #

把原图的连通性问题转化为二分图的连通分量合并问题，具体步骤如下：

1. 构建二分图

   • 左节点集合：收集原图所有节点的x坐标（去重）
   • 右节点集合：收集原图所有节点的y坐标（去重）
   • 边：对于原图中每个节点(x,y)，在二分图中添加一条连接x（左节点）和y（右节点）的边

2. 统计二分图连通分量数目
   使用DFS或BFS等图遍历算法，找出二分图的所有连通分量，记分量总数为k

3. 计算最少添加节点数
   要将k个连通分量合并为一个，只需添加k-1个节点。每个添加的节点对应二分图中一条跨两个分量的边，从而将两个分量合并，重复此操作直到所有分量连通。

示例验证 #

示例中的二分图共有4个连通分量，因此最少需要添加4-1=3个节点，比如：

• 添加节点(5,1)：连接x=5（对应节点9）和y=1（对应节点1、6等），合并前两个分量
• 添加节点(6,3)：连接x=6（对应节点10）和y=3（对应节点3、9等），合并前三个分量
• 添加节点(10,7)：连接x=10（对应节点11）和y=7（对应节点10），最终所有节点连通

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