談匈牙利演算法自然避不開Hall定理，即是：對於二部圖G，存在一個匹配M，使得X的所有頂點關於M飽和的充要條件是：對於X的任意一個子集A，和A鄰接的點集為T(A)，恆有：│T(A)│>=│A│ 匈牙利演算法是基於Hall定理中充分性證明的思想，其基本步驟為： 1．任給初始匹配M； 2．若X已飽和則結束，否則進行第3步； 3．在X中找到一個非飽和頂點x0，作V1←{x0},V2←Φ； 4．若T(V1)=V2則因為無法匹配而停止，否則任選一點y∈T(V1)\V2； 5．若y已飽和則轉6，否則做一條從x0→y的可增廣道路P，M←M?E(P)，轉2； 6．由於y已飽和，所以M中有一條邊(y,z)，作V1←V1∪{z},V2←V2∪{y}，轉4； 設陣列up[1..n]---標記二分圖的上半部分的點。 down[1..n]---標記二分圖的下半部分的點。 map[1..n，1..n]---表示二分圖的上，下部分的點的關係。 True-相連，false---不相連。 over1[1..n]，over2[1..n]標記上下部分的已蓋點。 use[1..n，1..n]-表示該條邊是否被覆蓋。 首先對讀入資料進行處理，對於一條邊(x，y)，起點進集合up，終點進集合down。標記map中對應元素為true。 1.尋找up中一個未蓋點。 2.從該未蓋點出發，搜尋一條可行的路線，即由細邊出發，由細邊結束，且細粗交錯的路線。 3.若找到，則修改該路線上的點所對應的over1，over2，use的元素。重複步驟1。 4.統計use中已覆蓋的邊的條數total，總數n減去total即為問題的解。
談匈牙利演算法自然避不開Hall定理，即是：對於二部圖G，存在一個匹配M，使得X的所有頂點關於M飽和的充要條件是：對於X的任意一個子集A，和A鄰接的點集為T(A)，恆有：│T(A)│>=│A│ 匈牙利演算法是基於Hall定理中充分性證明的思想，其基本步驟為： 1．任給初始匹配M； 2．若X已飽和則結束，否則進行第3步； 3．在X中找到一個非飽和頂點x0，作V1←{x0},V2←Φ； 4．若T(V1)=V2則因為無法匹配而停止，否則任選一點y∈T(V1)\V2； 5．若y已飽和則轉6，否則做一條從x0→y的可增廣道路P，M←M?E(P)，轉2； 6．由於y已飽和，所以M中有一條邊(y,z)，作V1←V1∪{z},V2←V2∪{y}，轉4； 設陣列up[1..n]---標記二分圖的上半部分的點。 down[1..n]---標記二分圖的下半部分的點。 map[1..n，1..n]---表示二分圖的上，下部分的點的關係。 True-相連，false---不相連。 over1[1..n]，over2[1..n]標記上下部分的已蓋點。 use[1..n，1..n]-表示該條邊是否被覆蓋。 首先對讀入資料進行處理，對於一條邊(x，y)，起點進集合up，終點進集合down。標記map中對應元素為true。 1.尋找up中一個未蓋點。 2.從該未蓋點出發，搜尋一條可行的路線，即由細邊出發，由細邊結束，且細粗交錯的路線。 3.若找到，則修改該路線上的點所對應的over1，over2，use的元素。重複步驟1。 4.統計use中已覆蓋的邊的條數total，總數n減去total即為問題的解。