MATLAB实现匈牙利算法求解二分图最大匹配

匈牙利算法（也称为Kuhn-Munkres算法）是解决二分图最大匹配问题的经典算法。

代码

function [matching, max_match] = hungarian_algorithm(adjMatrix)% HUNGARIAN_ALGORITHM 实现匈牙利算法求解二分图最大匹配% 输入：%   adjMatrix - 二分图的邻接矩阵，大小为m×n，m表示左侧顶点数，n表示右侧顶点数% 输出：%   matching - 匹配结果向量，matching(i)表示左侧第i个顶点匹配的右侧顶点索引（0表示未匹配）%   max_match - 最大匹配数[m, n] = size(adjMatrix);% 初始化匹配数组：matching_left表示左侧顶点的匹配，matching_right表示右侧顶点的匹配matching_left = zeros(1, m);    % 左侧匹配结果，初始为0（未匹配）matching_right = zeros(1, n);    % 右侧匹配结果，初始为0（未匹配）% 定义DFS函数用于寻找增广路径function found = dfs(u, visited)for v = 1:n% 如果存在边且右侧顶点v未被访问if adjMatrix(u, v) && ~visited(v)visited(v) = true;  % 标记右侧顶点v为已访问% 如果右侧顶点v未被匹配，或者已匹配的左侧顶点可以找到其他匹配if matching_right(v) == 0 || dfs(matching_right(v), visited)matching_left(u) = v;       % 将左侧u匹配到右侧vmatching_right(v) = u;      % 将右侧v匹配到左侧ufound = true;               % 找到增广路径return;endendendfound = false;  % 未找到增广路径end% 主算法：对每个左侧顶点尝试寻找匹配for u = 1:mvisited = false(1, n);  % 初始化访问标记数组dfs(u, visited);        % 尝试为当前左侧顶点u寻找匹配end% 统计匹配数max_match = sum(matching_left > 0);% 返回左侧匹配结果matching = matching_left;
end

算法测试与示例

1：简单二分图

% 创建邻接矩阵 (3x3)
adjMatrix = [1, 0, 1;  % 左侧顶点1连接右侧顶点1和30, 1, 0;  % 左侧顶点2连接右侧顶点21, 1, 0;  % 左侧顶点3连接右侧顶点1和2
];% 运行匈牙利算法
[matching, max_match] = hungarian_algorithm(adjMatrix);% 显示结果
disp('匹配结果:');
for i = 1:length(matching)if matching(i) > 0fprintf('左侧顶点 %d 匹配到右侧顶点 %d\n', i, matching(i));elsefprintf('左侧顶点 %d 未匹配\n', i);end
end
fprintf('最大匹配数: %d\n', max_match);

2：更大规模的二分图

% 创建随机二分图 (10x8)
rng(42); % 设置随机种子确保可重复性
adjMatrix = randi([0, 1], 10, 8); % 随机生成0-1矩阵% 运行匈牙利算法
[matching, max_match] = hungarian_algorithm(adjMatrix);% 显示结果
disp('邻接矩阵:');
disp(adjMatrix);disp('匹配结果:');
disp(matching);
fprintf('最大匹配数: %d\n', max_match);% 可视化结果
figure;
hold on;
title('二分图匹配结果');
xlim([0, 3]);
ylim([0, max(10, 8)+1]);% 绘制左侧顶点
for i = 1:10plot(0.5, i, 'bo', 'MarkerSize', 10, 'MarkerFaceColor', 'b');text(0.4, i, sprintf('L%d', i));
end% 绘制右侧顶点
for j = 1:8plot(2.5, j, 'ro', 'MarkerSize', 10, 'MarkerFaceColor', 'r');text(2.6, j, sprintf('R%d', j));
end% 绘制所有边
for i = 1:10for j = 1:8if adjMatrix(i, j)plot([0.5, 2.5], [i, j], 'k:', 'LineWidth', 0.5);endend
end% 绘制匹配边
for i = 1:10if matching(i) > 0plot([0.5, 2.5], [i, matching(i)], 'g-', 'LineWidth', 2);end
endlegend('左侧顶点', '右侧顶点', '可能边', '匹配边');
hold off;

算法分析与解释

匈牙利算法核心思想

匈牙利算法基于以下关键概念：

增广路径：从一个未匹配顶点开始，交替经过匹配边和非匹配边，最终到达另一个未匹配顶点的路径
核心操作：找到一条增广路径并"翻转"路径上的边（匹配变非匹配，非匹配变匹配），从而增加匹配数

MATLAB实现特点

深度优先搜索(DFS)：使用递归DFS寻找增广路径
高效匹配：时间复杂度为O(mn)，其中m和n分别是左右两侧顶点数
简洁实现：利用递归函数和访问标记数组优化搜索过程

算法步骤详解

初始化：
- 创建匹配数组matching_left和matching_right，初始化为0（未匹配）
遍历左侧顶点：
- 对每个左侧顶点u，尝试寻找匹配的右侧顶点
DFS寻找增广路径：
- 标记已访问的右侧顶点
- 对于当前左侧顶点u连接的每个右侧顶点v：
  - 如果v未访问，则标记为已访问
  - 如果v未匹配，或者v已匹配但可以找到替代匹配，则更新匹配
更新匹配：
- 当找到增广路径时，更新匹配关系
结果统计：
- 计算并返回最大匹配数

参考代码 matlab实现匈牙利算法二分图最大匹配的程序 www.youwenfan.com/contentcsd/97883.html

应用场景

匈牙利算法在以下领域有广泛应用：

任务分配：将任务分配给最合适的工人
资源调度：最优资源分配问题
图像处理：特征点匹配
网络流：求解最大流问题的辅助算法
化学：分子结构中的键合分析

性能优化建议

对于大型二分图，可以考虑以下优化：

% 优化版本：添加早期终止和预处理
function [matching, max_match] = optimized_hungarian(adjMatrix)[m, n] = size(adjMatrix);matching_left = zeros(1, m);matching_right = zeros(1, n);% 预处理：先尝试贪心匹配for u = 1:mfor v = 1:nif adjMatrix(u, v) && matching_right(v) == 0 && matching_left(u) == 0matching_left(u) = v;matching_right(v) = u;endendendfunction found = dfs(u, visited)for v = 1:nif adjMatrix(u, v) && ~visited(v)visited(v) = true;% 使用匹配数组直接访问，提高效率if matching_right(v) == 0 || dfs(matching_right(v), visited)matching_left(u) = v;matching_right(v) = u;found = true;return;endendendfound = false;end% 只对未匹配的左侧顶点尝试DFSfor u = 1:mif matching_left(u) == 0visited = false(1, n);dfs(u, visited);endendmax_match = sum(matching_left > 0);matching = matching_left;
end