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;

算法分析與解釋

匈牙利算法核心思想

匈牙利算法基于以下關鍵概念：

1. 增廣路徑：從一個未匹配頂點開始，交替經過匹配邊和非匹配邊，最終到達另一個未匹配頂點的路徑
2. 核心操作：找到一條增廣路徑并"翻轉"路徑上的邊（匹配變非匹配，非匹配變匹配），從而增加匹配數

MATLAB實現特點

1. 深度優先搜索(DFS)：使用遞歸DFS尋找增廣路徑
2. 高效匹配：時間復雜度為O(mn)，其中m和n分別是左右兩側頂點數
3. 簡潔實現：利用遞歸函數和訪問標記數組優化搜索過程

算法步驟詳解

1. 初始化：

   • 創建匹配數組matching_left和matching_right，初始化為0（未匹配）

2. 遍歷左側頂點：

   • 對每個左側頂點u，嘗試尋找匹配的右側頂點

3. DFS尋找增廣路徑：

   • 標記已訪問的右側頂點
   • 對于當前左側頂點u連接的每個右側頂點v：
     • 如果v未訪問，則標記為已訪問
     • 如果v未匹配，或者v已匹配但可以找到替代匹配，則更新匹配

4. 更新匹配：

   • 當找到增廣路徑時，更新匹配關系

5. 結果統計：

   • 計算并返回最大匹配數

參考代碼 matlab實現匈牙利算法二分圖最大匹配的程序 www.youwenfan.com/contentcsd/97883.html

應用場景

匈牙利算法在以下領域有廣泛應用：

1. 任務分配：將任務分配給最合適的工人
2. 資源調度：最優資源分配問題
3. 圖像處理：特征點匹配
4. 網絡流：求解最大流問題的輔助算法
5. 化學：分子結構中的鍵合分析

性能優化建議

對于大型二分圖，可以考慮以下優化：

% 優化版本：添加早期終止和預處理
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

此優化版本添加了：

1. 貪心預處理：先進行簡單匹配，減少后續DFS次數
2. 條件DFS：只對未匹配的左側頂點進行DFS
3. 直接訪問：避免重復計算

匈牙利算法是解決二分圖匹配問題的高效方法，本實現提供了清晰的MATLAB代碼和示例，可直接應用于各種匹配問題。