本文目录导读：
我来帮你了解如何使用NetworkX解决匹配问题，我会从基础到进阶,给出几个实用的案例。
基本概念
NetworkX中的匹配主要分为：
- 最大匹配：找到最多数量的匹配边
- 最大权匹配：找到权重和最大的匹配
基础案例：二分图最大匹配
示例：工人-任务分配
import networkx as nx
import matplotlib.pyplot as plt
# 创建二分图
G = nx.Graph()
# 添加工人节点（左侧）
workers = ['W1', 'W2', 'W3', 'W4']
# 添加任务节点（右侧）
tasks = ['T1', 'T2', 'T3']
# 添加所有节点并标记二分属性
G.add_nodes_from(workers, bipartite=0) # 工人属于左侧
G.add_nodes_from(tasks, bipartite=1) # 任务属于右侧
# 添加可行的匹配边（工人可以做的任务）
edges = [
('W1', 'T1'), ('W1', 'T2'),
('W2', 'T1'), ('W2', 'T3'),
('W3', 'T2'), ('W3', 'T3'),
('W4', 'T1')
]
G.add_edges_from(edges)
# 求最大匹配
matching = nx.maximal_matching(G)
print("最大匹配结果:")
for edge in matching:
print(f" {edge[0]} -> {edge[1]}")
# 可视化
pos = nx.bipartite_layout(G, workers)
plt.figure(figsize=(10, 6))
nx.draw(G, pos, with_labels=True, node_color='lightblue',
node_size=2000, font_size=12, font_weight='bold')
# 高亮匹配边
nx.draw_networkx_edges(G, pos, edgelist=matching,
edge_color='red', width=3)"工人-任务匹配")
plt.show()
带权重的匹配问题
示例：最优任务分配
import networkx as nx
import numpy as np
# 创建带权重的二分图
G = nx.Graph()
workers = ['张三', '李四', '王五', '赵六']
tasks = ['设计', '开发', '测试']
# 添加节点
G.add_nodes_from(workers, bipartite=0)
G.add_nodes_from(tasks, bipartite=1)
# 添加带权重的边（表示匹配的得分或效率）
weighted_edges = [
('张三', '设计', 0.9), ('张三', '开发', 0.3), ('张三', '测试', 0.6),
('李四', '设计', 0.4), ('李四', '开发', 0.8), ('李四', '测试', 0.5),
('王五', '设计', 0.7), ('王五', '开发', 0.6), ('王五', '测试', 0.8),
('赵六', '设计', 0.2), ('赵六', '开发', 0.5), ('赵六', '测试', 0.3),
]
for w, t, score in weighted_edges:
G.add_edge(w, t, weight=score)
# 计算最大权重匹配
matching = nx.max_weight_matching(G, maxcardinality=True)
print("最优匹配结果:")
total_score = 0
for w, t in matching:
score = G[w][t]['weight']
total_score += score
print(f" {w} -> {t} (得分: {score})")
print(f"总得分: {total_score:.2f}")
实际应用：课程时间表安排
import networkx as nx
from collections import defaultdict
def schedule_courses(teachers, courses, time_slots):
"""安排课程时间表"""
G = nx.Graph()
# 添加节点
G.add_nodes_from(teachers, bipartite=0)
G.add_nodes_from(courses, bipartite=1)
# 构建可行性矩阵
availability = {
'张老师': {'数学': [1,2], '物理': [2,3]},
'李老师': {'数学': [2,3], '化学': [1,3]},
'王老师': {'物理': [1,2], '化学': [1,2]},
}
# 添加可能的匹配
for teacher, courses_dict in availability.items():
for course, slots in courses_dict.items():
# 权重表示可用时间段的优先级
weight = len(slots) / len(time_slots)
G.add_edge(teacher, course, weight=weight)
# 求最大匹配
matching = nx.max_weight_matching(G)
# 输出结果
schedule = defaultdict(list)
for teacher, course in matching:
slots = availability[teacher][course]
schedule[course].append((teacher, slots[0]))
return schedule
# 使用示例
teachers = ['张老师', '李老师', '王老师']
courses = ['数学', '物理', '化学']
time_slots = [1, 2, 3]
result = schedule_courses(teachers, courses, time_slots)
print("课程安排结果:")
for course, assignments in result.items():
print(f"\n{course}:")
for teacher, slot in assignments:
print(f" - {teacher} 在时段 {slot}")
完整示例：相亲匹配系统
import networkx as nx
import matplotlib.pyplot as plt
import random
class MatchMaker:
"""相亲匹配系统"""
def __init__(self):
self.graph = nx.Graph()
self.men = []
self.women = []
def add_person(self, name, gender, interests, preferences):
"""添加人员"""
if gender == '男':
self.men.append(name)
self.graph.add_node(name, bipartite=0, interests=interests)
else:
self.women.append(name)
self.graph.add_node(name, bipartite=1, interests=interests)
# 存储偏好
self.graph.nodes[name]['preferences'] = preferences
def calculate_compatibility(self, person1, person2):
"""计算兼容性分数"""
inter1 = set(self.graph.nodes[person1]['interests'])
inter2 = set(self.graph.nodes[person2]['interests'])
# 共同兴趣数
common = len(inter1 & inter2)
total = len(inter1 | inter2)
if total == 0:
return 0
interest_score = common / total
# 偏好匹配
pref1 = self.graph.nodes[person1]['preferences']
pref2 = self.graph.nodes[person2]['preferences']
pref_score = 0
if person2 in pref1 and person1 in pref2:
pref_score = 1.0
return 0.6 * interest_score + 0.4 * pref_score
def find_best_matches(self):
"""找到最佳匹配"""
# 计算所有可能的配对兼容性
for man in self.men:
for woman in self.women:
score = self.calculate_compatibility(man, woman)
if score > 0:
self.graph.add_edge(man, woman, weight=score)
# 求最大权重匹配
matching = nx.max_weight_matching(self.graph, maxcardinality=True)
return matching
def visualize_matching(self, matching):
"""可视化匹配结果"""
pos = nx.bipartite_layout(self.graph, self.men)
plt.figure(figsize=(12, 8))
# 绘制所有边
nx.draw(self.graph, pos, with_labels=True,
node_color='lightgray', node_size=2000,
font_size=10, alpha=0.3)
# 高亮匹配边
nx.draw_networkx_edges(self.graph, pos, edgelist=matching,
edge_color='red', width=2)
# 添加兼容性分数标签
for man, woman in matching:
score = self.graph[man][woman]['weight']
x = (pos[man][0] + pos[woman][0]) / 2
y = (pos[man][1] + pos[woman][1]) / 2
plt.text(x, y, f'{score:.2f}', fontsize=12,
color='blue', fontweight='bold')
plt.title("相亲匹配结果")
plt.show()
# 使用示例
match_system = MatchMaker()
# 添加参与者
match_system.add_person('小明', '男',
['运动', '音乐', '旅行'],
['小红', '小芳'])
match_system.add_person('小强', '男',
['游戏', '电影', '美食'],
['小芳', '小丽'])
match_system.add_person('大伟', '男',
['读书', '运动', '摄影'],
['小红', '小丽'])
match_system.add_person('小红', '女',
['旅行', '读书', '运动'],
['小明', '大伟'])
match_system.add_person('小芳', '女',
['音乐', '美食', '电影'],
['小明', '小强'])
match_system.add_person('小丽', '女',
['摄影', '旅行', '游戏'],
['小强', '大伟'])
# 找到最佳匹配
matches = match_system.find_best_matches()
print("最佳匹配结果:")
for man, woman in matches:
score = match_system.graph[man][woman]['weight']
print(f" {man} <-> {woman} (兼容性: {score:.2f})")
# 可视化
match_system.visualize_matching(matches)
注意事项
- 数据类型：确保节点可哈希（字符串、元组等）
- 二分图：使用
nx.bipartite_layout时需正确设置节点属性 - 权重处理：权重值应为数值类型，越大表示越优
- 性能优化：大规模图建议使用
max_weight_matching的maxcardinality参数
这些案例覆盖了NetworkX解决匹配问题的主要场景，根据你的具体需求,可以选择相应的实现方式。
