如何在NetworkX图中连接节点生成无边交叉的连通图？

你提到的「无边交叉连通图」正式名称为平面嵌入连通图，欧几里得最小生成树和Delaunay三角剖分图两类结构都天然满足全连通、边无交叉的要求，可直接通过NetworkX实现：

方案1：欧几里得最小生成树（边数最少） #

该结构仅保留n-1条边即可实现全连通，几何上已证明不存在边交叉。

import networkx as nx
import numpy as np

# 1. 生成n个[0,1]区间的随机点，初始化图
n = 20
points = np.random.uniform(0, 1, size=(n, 2))
G = nx.Graph()
for idx in range(n):
    G.add_node(idx, pos=(points[idx, 0], points[idx, 1]))

# 2. 为完全图添加欧氏距离权重
for u in range(n):
    x1, y1 = G.nodes[u]['pos']
    for v in range(u + 1, n):
        x2, y2 = G.nodes[v]['pos']
        dist = np.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)
        G.add_edge(u, v, weight=dist)

# 3. 生成最小生成树，即为无交叉连通图
mst = nx.minimum_spanning_tree(G)

方案2：Delaunay三角剖分图（边数更丰富） #

该结构为平面三角化的无交叉图，连通性更强，边数远多于最小生成树，适合需要更多连接的场景。

import networkx as nx
import numpy as np
from scipy.spatial import Delaunay

# 1. 生成随机点
n = 20
points = np.random.uniform(0, 1, size=(n, 2))

# 2. 执行Delaunay三角剖分
tri = Delaunay(points)

# 3. 转成NetworkX图对象
G_delaunay = nx.Graph()
for idx in range(n):
    G_delaunay.add_node(idx, pos=(points[idx, 0], points[idx, 1]))
# 遍历所有三角形单元添加边
for simplex in tri.simplices:
    u, v, w = simplex
    G_delaunay.add_edges_from([(u, v), (v, w), (u, w)])

效果验证 #

可以直接调用NetworkX的绘图接口查看无交叉效果：

import matplotlib.pyplot as plt
# 以最小生成树为例
pos = nx.get_node_attributes(mst, 'pos')
nx.draw(mst, pos, node_size=150, with_labels=True)
plt.show()

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