用MATLAB实现匈牙利算法

匈牙利算法（也称作Kuhn-Munkres算法）是一种用于解决二分图最大匹配问题的算法。下面是使用MATLAB实现匈牙利算法的示例代码：

function [matching, cost] = hungarianAlgorithm(costMatrix)
    % 输入: costMatrix - 二维矩阵，表示二分图的权重矩阵
    % 输出: matching - 最大匹配的匹配情况
    %       cost - 最大匹配的总权重

    % 初始化
    n = size(costMatrix, 1);
    m = size(costMatrix, 2);
    labelX = zeros(n, 1);
    labelY = zeros(m, 1);
    matching = zeros(n, 1);
    slack = inf(m, 1);
    slackX = zeros(m, 1);
    prev = zeros(m, 1);
    
    % 找到最大匹配
    for i = 1:n
        % 更新标签
        labelX(i) = max(costMatrix(i, :));
        
        while true
            % 初始化
            visitedX = false(n, 1);
            visitedY = false(m, 1);
            slack(:) = inf;
            
            % 尝试找到增广路径
            if dfs(i)
                break;
            end
            
            % 无法找到增广路径，调整标签
            d = min(slack(~visitedY));
            labelX(visitedX) = labelX(visitedX) - d;
            labelY(visitedY) = labelY(visitedY) + d;
            slackX(visitedY) = slackX(visitedY) + d;
        end
    end
    
    % 计算最大匹配的总权重
    cost = sum(costMatrix(sub2ind([n, m], (1:n)', matching)));
    
    function found = dfs(x)
        visitedX(x) = true;
        
        for y = 1:m
            if visitedY(y)
                continue;
            end
            
            if labelX(x) + labelY(y) == costMatrix(x, y)
                visitedY(y) = true;
                
                if matching(x) == 0 || dfs(matching(x))
                    matching(x) = y;
                    found = true;
                    return;
                end
            else
                slackVal = labelX(x) + labelY(y) - costMatrix(x, y);
                
                if slackVal < slack(y)
                    slack(y) = slackVal;
                    prev(y) = x;
                    slackX(y) = x;
                end
            end
        end
        
        found = false;
    end
end

使用示例：

costMatrix = [1, 2, 3; 4, 5, 6; 7, 8, 9];  % 二分图的权重矩阵
[matching, cost] = hungarianAlgorithm(costMatrix);
disp(matching);  % 输出最大匹配的匹配情况
disp(cost);  % 输出最大匹配的总权重

请注意，该示例代码中的costMatrix是一个二维矩阵，其中每个元素表示二分图中的边的权重。matching是一个向量，表示最大匹配的匹配情况，其中matching(i)表示左侧第i个节点与右侧第matching(i)个节点匹配。cost表示最大匹配的总权重。

此外，算法还使用了一些辅助向量和变量，如labelX，labelY，slack，slackX和prev，用于辅助计算和调整标签