使用Java/Python生成几何随机图、检测连通性并绘制r-连通性曲线求助

方案选型 #

优先选Python，比Java实现难度低很多，原因是有成熟的图计算、可视化库可以直接调用，不需要手动实现随机图生成、连通性检测、绘图的底层逻辑。

步骤1：环境准备 #

需要安装三个依赖库，安装命令：
pip install networkx numpy matplotlib

• networkx：负责随机图生成、连通性检测
• numpy：负责数值计算、参数遍历
• matplotlib：负责结果绘图

步骤2：核心功能实现逻辑 #

2.1 1000节点几何随机图生成+连通性检测 #

直接调用networkx内置API即可，无需手动实现：

• 生成随机几何图调用nx.random_geometric_graph(n=1000, r=阈值)，默认节点均匀分布在单位正方形[0,1]×[0,1]上，两个节点欧氏距离小于r时自动连边
• 连通性检测调用nx.is_connected(图对象)，返回布尔值，True表示是有效连通图，False表示非连通

2.2 不同r取值的连通性关系图绘制 #

绘制逻辑如下：

1. 设定r的遍历范围：根据1000节点的随机几何图临界连通值约为0.05，可设置r的取值范围为0~0.1，步长设为0.005，总共20个左右的采样点即可画出平滑的S型曲线
2. 每个r值重复多次实验（建议5~10次，消除随机波动影响），统计该r下的连通概率 = 连通的实验次数 / 总实验次数
3. 以r为横轴，连通概率为纵轴绘制折线图/散点图即可得到目标关系图

核心代码示例 #

import networkx as nx
import numpy as np
import matplotlib.pyplot as plt

# 参数配置
NODE_NUM = 1000
TEST_TIMES_PER_R = 8  # 每个r重复实验次数
R_RANGE = np.arange(0.01, 0.1, 0.005)  # r的取值范围

connect_probs = []
for r in R_RANGE:
    connect_count = 0
    for _ in range(TEST_TIMES_PER_R):
        G = nx.random_geometric_graph(NODE_NUM, r)
        if nx.is_connected(G):
            connect_count += 1
    connect_probs.append(connect_count / TEST_TIMES_PER_R)

# 绘图
plt.plot(R_RANGE, connect_probs, 'o-', color='#2c7fb8')
plt.xlabel('邻接阈值r')
plt.ylabel('连通概率')
plt.title('1000节点随机几何图连通性随r变化关系')
plt.grid(alpha=0.3)
plt.show()

注意事项 #

• 如果需要提升运行速度，可以开启networkx的并查集优化，或者将重复实验的逻辑用多进程加速
• 若需要调整节点分布的空间范围，可以在生成随机图时传入pos参数自定义节点坐标

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