匈牙利匹配算法 matlab

匈牙利算法（匈牙利匹配算法）是一种解决二分图最大匹配问题的算法。它的基本思想是从左侧的未匹配顶点开始，依次尝试与其右侧的顶点匹配，如果匹配成功，则继续处理下一个未匹配顶点，否则尝试为当前顶点寻找另一个可行的匹配。

以下是一份基于 MATLAB 的匈牙利算法实现代码，用于求解给定二分图的最大匹配：

function [match, maxMatch] = hungarianAlgorithm(BipartiteGraph)
% BipartiteGraph: 二分图的邻接矩阵表示
% match: 匹配结果（左侧顶点对应的右侧顶点编号，未匹配则为 0）
% maxMatch: 最大匹配数

n = size(BipartiteGraph, 1); % 左侧顶点数
m = size(BipartiteGraph, 2); % 右侧顶点数

match = zeros(1, n); % 匹配结果
maxMatch = 0; % 最大匹配数

for i = 1:n
    % 初始化标记数组
    S = false(1, n);
    T = false(1, m);
    P = zeros(1, m); % 右侧顶点的前驱顶点编号
    AugPath = zeros(1, n); % 增广路径
    
    % 寻找未匹配的左侧顶点
    if match(i) == 0
        % 在未匹配的左侧顶点中查找增广路径
        if dfs(i)
            % 更新匹配结果
            maxMatch = maxMatch + 1;
            j = i;
            while j ~= 0
                match(j) = AugPath(j);
                j = P(AugPath(j));
            end
        end
    end
end

% 深度优先搜索查找增广路径
function isPathFound = dfs(u)
    S(u) = true;
    for v = 1:m
        if BipartiteGraph(u, v) && ~T(v)
            T(v) = true;
            if P(v) == 0 || dfs(P(v))
                P(v) = u;
                AugPath(u) = v;
                isPathFound = true;
                return
            end
        end
    end
    isPathFound = false;
end

end

该算法的时间复杂度为 O(n^3)，其中 n 为图中顶点的数量。在实际应用中，可以通过一些优化技巧（如启发式算法、Kuhn-Munkres 算法）来提高算法的效率。