如何基于NetworkX计算二分图？附示例带权边列表

嘿，我来一步步带你用NetworkX处理你的带权二分图数据，咱们直接上手实操，用你给的边列表作为示例～

第一步：准备工作 #

首先得确保你已经安装了NetworkX，如果还没装，打开终端跑这个命令：

pip install networkx

然后在Python脚本里导入需要的库：

import networkx as nx
from networkx.algorithms import bipartite  # 可选，专门的二分图工具集

第二步：整理你的边列表数据 #

你给的边列表是source,target,weight格式的，咱们先把它转换成NetworkX能识别的三元组列表（每个元素是(源节点, 目标节点, 权重)）。比如你给的前几条可以写成这样：

# 把你所有的边都按这个格式补全就行，这里列部分示例
edge_list = [
    (162600, 117237, 200),
    (192084, 50240, 200),
    (200854, 125014, 200),
    (166729, 37059, 5),
    (157279, 77297, 1),
    (186788, 35124, 2),
    # ... 剩下的边继续添加到这里
]

第三步：构建带权二分图 #

接下来咱们创建图对象，并且添加带权边，同时标记二分图的两个节点组（假设你的source属于一组，target属于另一组）：

# 创建无向图对象
bipartite_graph = nx.Graph()

# 添加所有带权边，NetworkX会自动识别三元组里的权重值
bipartite_graph.add_edges_from(edge_list, weight="weight")

# 提取两个节点组
source_group = {u for u, v, w in edge_list}
target_group = {v for u, v, w in edge_list}

# 给节点添加「bipartite」属性，标记它属于哪一组（0或1）
bipartite_graph.add_nodes_from(source_group, bipartite=0)
bipartite_graph.add_nodes_from(target_group, bipartite=1)

第四步：常见的二分图计算操作 #

现在图已经构建好了，咱们可以做一些常用的计算：

1. 验证是否是合法的二分图 #

虽然咱们是按二分图的结构构建的，但可以用这个命令确认一下：

print("是否为二分图:", nx.is_bipartite(bipartite_graph))

2. 统计两组节点的数量 #

print(f"源节点组数量: {len(source_group)}")
print(f"目标节点组数量: {len(target_group)}")

3. 计算节点的加权度 #

加权度就是该节点所有相连边的权重之和，比如查看源节点组里每个节点的加权度：

for node in source_group:
    weighted_degree = nx.degree(bipartite_graph, node, weight="weight")
    print(f"节点{node}的加权度: {weighted_degree}")

4. 计算带权最大匹配 #

如果需要找权重总和最大的节点匹配（二分图经典问题），可以用NetworkX的max_weight_matching方法：

# maxcardinality=False表示优先追求权重最大，而非匹配数量最多
max_weight_matching = nx.max_weight_matching(bipartite_graph, maxcardinality=False)

print("\n带权最大匹配结果:")
for u, v in max_weight_matching:
    edge_weight = bipartite_graph[u][v]["weight"]
    print(f"{u} ↔ {v}, 权重: {edge_weight}")

小提示 #

如果你的边列表是从文件里读取的（比如CSV），可以用csv模块或者pandas来批量读取，不用手动写列表，比如用pandas的话：

import pandas as pd
df = pd.read_csv("你的边列表文件.csv", header=None, names=["source", "target", "weight"])
edge_list = list(df.itertuples(index=False, name=None))

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