匈牙利算法matlab

匈牙利算法是一种解决二分图最大匹配问题的经典算法，它的实现方法有很多种。在 MATLAB 中实现匈牙利算法可以采用递归实现，具体步骤如下：

1. 构造二分图的邻接矩阵，其中二分图的左部顶点为行，右部顶点为列，矩阵中的值表示该行和该列对应的顶点是否有连边；

2. 定义一个数组 match，用于记录右部顶点与左部顶点匹配的情况，初始值为 -1；

3. 定义一个函数 dfs，用于实现递归搜索匹配过程。在 dfs 函数中，首先遍历当前节点的邻接点，如果该邻接点未被匹配，则将其与当前节点匹配，并递归搜索其对应的左部顶点，直到找到一个未被匹配的左部顶点或者搜索到了已经被匹配的左部顶点；

4. 遍历所有的右部顶点，对于每个未被匹配的右部顶点，调用 dfs 函数进行匹配，更新 match 数组；

5. 统计匹配的点对数，即为二分图的最大匹配。

下面是 MATLAB 代码实现匈牙利算法：

function [matchNum,match] = HungarianAlgorithm(adjMat)
% adjMat: 二分图的邻接矩阵
% matchNum: 二分图的最大匹配数
% match: 右部顶点与左部顶点的匹配情况
match = -1*ones(1,size(adjMat,2)); % 初始化match数组
for i = 1:size(adjMat,2) % 遍历右部顶点
    visited = false(1,size(adjMat,1)); % 初始化visited数组
    matchNum = matchNum + dfs(adjMat,i,visited,match); % 统计匹配的点对数
end
end

function [flag] = dfs(adjMat,v,visited,match)
% adjMat: 二分图的邻接矩阵
% v: 当前右部顶点的编号
% visited: 左部顶点的访问状态
% match: 右部顶点与左部顶点的匹配情况
% flag: 是否找到增广路径的标志
flag = false; % 初始化flag标志
for i = 1:size(adjMat,1) % 遍历当前节点的邻接点
    if adjMat(i,v) && ~visited(i) % 如果该邻接点未被匹配
        visited(i) = true; % 标记该节点已被访问
        if match(i) == -1 || dfs(adjMat,match(i),visited,match) % 如果该节点未被匹配或者可以找到增广路径
            match(i) = v; % 更新匹配情况
            flag = true; % 标记已找到增广路径
            break; % 停止搜索
        end
    end
end
end

在上述代码中，matchNum 表示二分图的最大匹配数，match 数组记录右部顶点与左部顶点的匹配情况。函数 dfs 实现了递归搜索匹配过程，flag 标志表示是否找到增广路径。