带权重随机图生成及顶点度数约束的技术咨询

一、给Erdős–Rényi图加随机权重 #

NetworkX的gnp_random_graph()或fast_gnp_random_graph()确实没有内置权重参数，但生成无向图后，手动给每条边加权重非常简单：

import networkx as nx
import random

# 生成基础ER图
city_count = 20
edge_prob = 0.3
G = nx.gnp_random_graph(city_count, edge_prob)

# 为每条边添加0-10之间的随机权重
for u, v in G.edges():
    G.edges[u, v]['weight'] = random.uniform(0, 10)

二、保证每个顶点至少2条边 #

ER图的顶点度数可能为0或1，无法直接满足最小度要求，有两种处理方式：

方式1：补全ER图的低度数顶点

生成ER图后，遍历所有顶点，给度数小于2的节点补充边：

for node in G.nodes():
    while G.degree(node) < 2:
        # 随机选一个非自身且未连接的节点
        candidates = [n for n in G.nodes() if n != node and not G.has_edge(node, n)]
        if not candidates:
            raise ValueError("顶点数过少，无法满足每个顶点至少2条边")
        target = random.choice(candidates)
        G.add_edge(node, target, weight=random.uniform(0, 10))

方式2：用内置生成器直接生成最小度符合要求的图

如果不想手动补全，推荐用random_regular_graph()，它能生成每个顶点度数完全相等的正则图（度数≥2），之后再加权重：

# 生成每个顶点有3条边的正则图
G = nx.random_regular_graph(3, city_count)
# 添加随机权重
for u, v in G.edges():
    G.edges[u, v]['weight'] = random.uniform(0, 10)

如果不需要度数完全一致，也可以用gnm_random_graph()生成足够边数的图，再补全低度数节点。

结论 #

Erdős–Rényi生成器本身不能直接满足最小度2的要求，但可以通过后续补全实现；如果追求更直接的方案，random_regular_graph()是更合适的选择，再配合手动加权重就能满足你的项目需求。

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