什麼是匈牙利演算法
匈牙利演算法是一種用於解決二分圖最大匹配問題的貪心演算法。它的目標是找到一個最大匹配，即找到一個二分圖的最大邊集合，使得每個頂點最多和一個邊相連。
匈牙利演算法的原理
匈牙利演算法的基本思想是通過不斷增廣路徑，來找到一個最大匹配。首先，假設二分圖中沒有邊相連。然後，從一個頂點開始，通過深度優先搜索的方式，找到能夠和它相連的未訪問過的頂點。如果找到了一個增廣路徑，就把這條路徑上的邊加入匹配中，重複這個過程，直到沒有更多的增廣路徑。最終，得到的邊集合就是一個最大匹配。
匈牙利演算法的步驟
1. 初始化一個空的匹配。
2. 對於每個頂點，找到一個未訪問過的頂點，如果能夠找到增廣路徑，就把這條路徑上的邊加入匹配中。
3. 重複步驟2，直到沒有更多的增廣路徑。
匈牙利演算法的時間複雜度
匈牙利演算法的時間複雜度為O(V*E)，其中V是二分圖中左邊頂點的數量，E是二分圖的邊的數量。演算法的關鍵是通過路徑的增廣來提高匹配的數量，每次增廣的過程中，都需要遍歷二分圖的所有邊，所以演算法的時間複雜度為O(V*E)。
匈牙利演算法的應用
匈牙利演算法廣泛應用於圖論和組合優化領域。它可以用來解決二分圖最大匹配問題，也可以擴展到解決其他相關的問題，如最小頂點覆蓋問題、最大獨立集問題等。
