問題背景

給定一個x與y對應的連接圖，要求每個xi與yi最多只能匹配一次，求最大的匹配次數

求解思路

（1）將x與y的連接轉換成矩陣，可相互連接標記為1，其余為0

（2）最外層回圈x1到x6，即第一行到第六行，每一行分別從y1到y7遍歷

（3）其中used_b = [0, 0, 0, 0, 0, 0, 0]為某一行中被使用的y1

（4）conection_b = [-1,-1,-1,-1,-1,-1,-1]其中每個元素的取值范圍為0-5，代表了y對應的第幾行x

（5）從第一行開始，選中了y1，conection_b發生變化[0, -1, -1, -1, -1, -1, -1]

i: 0
find: 0
_index: 0
_used_b: [1, 0, 0, 0, 0, 0, 0]
_conection_b: [-1, -1, -1, -1, -1, -1, -1]
index: 0
conection_b: [0, -1, -1, -1, -1, -1, -1]
count

（6）第二行，選中了y2，conection_b發生變化[0, 1, -1, -1, -1, -1, -1]

i: 1
find: 1
_index: 1
_used_b: [0, 1, 0, 0, 0, 0, 0]
_conection_b: [0, -1, -1, -1, -1, -1, -1]
index: 1
conection_b: [0, 1, -1, -1, -1, -1, -1]
count

（7）第三行，選中了y1，由于第一行也選中了y1，因此進入遞回

i: 2
find: 2
_index: 0
_used_b: [1, 0, 0, 0, 0, 0, 0]
_conection_b: [0, 1, -1, -1, -1, -1, -1]
find: 0
_index: 1
_used_b: [1, 1, 0, 0, 0, 0, 0]
_conection_b: [0, 1, -1, -1, -1, -1, -1]
find: 1
_index: 4
_used_b: [1, 1, 0, 0, 1, 0, 0]
_conection_b: [0, 1, -1, -1, -1, -1, -1]
index: 4
conection_b: [0, 1, -1, -1, 1, -1, -1]
index: 1
conection_b: [0, 0, -1, -1, 1, -1, -1]
index: 0
conection_b: [2, 0, -1, -1, 1, -1, -1]
count

（8）得到沖突行的index為0，因此開始find(0)，發現y2也被使用，因此繼續遞回find(1)

（9）最后x2找到了y5，因此遞回結束，conection_b: [2, 0, -1, -1, 1, -1, -1]

（10）第四行，選中了y3，由于沒有沖突，所以conection_b: [2, 0, 3, -1, 1, -1, -1]

i: 3
find: 3
_index: 2
_used_b: [0, 0, 1, 0, 0, 0, 0]
_conection_b: [2, 0, -1, -1, 1, -1, -1]
index: 2
conection_b: [2, 0, 3, -1, 1, -1, -1]
count

（11）第五行，選中了y4，由于沒有沖突，所以conection_b: [2, 0, 3, 4, 1, -1, -1]

i: 4
find: 4
_index: 3
_used_b: [0, 0, 0, 1, 0, 0, 0]
_conection_b: [2, 0, 3, -1, 1, -1, -1]
index: 3
conection_b: [2, 0, 3, 4, 1, -1, -1]
count

（12）第六行，選中了y4，由于與第五行發生了沖突，所以進入遞回find(4)

i: 5
find: 5
_index: 3
_used_b: [0, 0, 0, 1, 0, 0, 0]
_conection_b: [2, 0, 3, 4, 1, -1, -1]
find: 4
used_b: [0, 0, 0, 1, 0, 0, 0]
conection_b: [2, 0, 3, 4, 1, -1, -1]
5

（13）由于第五行中除了y4，沒有其他可選線項，因此 find(4) = 0，conection_b沒有被改變，因此：conection_b: [2, 0, 3, 4, 1, -1, -1]

代碼

>>>def find(x):
...    print("find:", x)
...    for index in range(7):
...        if matrix[x][index] == 1 and used_b[index] == 0:
...            used_b[index] = 1
...            print("_index:", index)
...            print("_used_b:", str(used_b))
...            print("_conection_b:", str(conection_b))
...            if conection_b[index] == -1 or find(conection_b[index]) != 0:
...                print("index:", index)
...                conection_b[index] = x
...                print("conection_b:", str(conection_b))
...                return 1
...    return 0
>>>matrix = [
...    [1,1,0,1,0,0,0],
...    [0,1,0,0,1,0,0],
...    [1,0,0,1,0,0,1],
...    [0,0,1,1,0,1,0],
...    [0,0,0,1,0,0,0],
...    [0,0,0,1,0,0,0]
...    ]
>>>conection_b = [-1 for _ in range(7)]
>>>count = 0
>>>for i in range(6):
...    used_b = [0 for _ in range(7)]
...    print("i:",i)
...    if find(i):
...        print("count")
...        count += 1
>>>print("used_b:", str(used_b))
>>>print("conection_b:", str(conection_b))
>>>print(count)
i: 0
find: 0
_index: 0
_used_b: [1, 0, 0, 0, 0, 0, 0]
_conection_b: [-1, -1, -1, -1, -1, -1, -1]
index: 0
conection_b: [0, -1, -1, -1, -1, -1, -1]
count
i: 1
find: 1
_index: 1
_used_b: [0, 1, 0, 0, 0, 0, 0]
_conection_b: [0, -1, -1, -1, -1, -1, -1]
index: 1
conection_b: [0, 1, -1, -1, -1, -1, -1]
count
i: 2
find: 2
_index: 0
_used_b: [1, 0, 0, 0, 0, 0, 0]
_conection_b: [0, 1, -1, -1, -1, -1, -1]
find: 0
_index: 1
_used_b: [1, 1, 0, 0, 0, 0, 0]
_conection_b: [0, 1, -1, -1, -1, -1, -1]
find: 1
_index: 4
_used_b: [1, 1, 0, 0, 1, 0, 0]
_conection_b: [0, 1, -1, -1, -1, -1, -1]
index: 4
conection_b: [0, 1, -1, -1, 1, -1, -1]
index: 1
conection_b: [0, 0, -1, -1, 1, -1, -1]
index: 0
conection_b: [2, 0, -1, -1, 1, -1, -1]
count
i: 3
find: 3
_index: 2
_used_b: [0, 0, 1, 0, 0, 0, 0]
_conection_b: [2, 0, -1, -1, 1, -1, -1]
index: 2
conection_b: [2, 0, 3, -1, 1, -1, -1]
count
i: 4
find: 4
_index: 3
_used_b: [0, 0, 0, 1, 0, 0, 0]
_conection_b: [2, 0, 3, -1, 1, -1, -1]
index: 3
conection_b: [2, 0, 3, 4, 1, -1, -1]
count
i: 5
find: 5
_index: 3
_used_b: [0, 0, 0, 1, 0, 0, 0]
_conection_b: [2, 0, 3, 4, 1, -1, -1]
find: 4
used_b: [0, 0, 0, 1, 0, 0, 0]
conection_b: [2, 0, 3, 4, 1, -1, -1]
5

總結

匈牙利演算法的核心思想為：優先考慮最后一行，如果發生沖突，則尋找沖突行可替代項，如果沒有可替代項，丟棄最后一行，如果有可替代項，則使用其替代，如果替代之后發生沖突則進入遞回，發現沖突不可解除，則丟棄最后一行，沖突可以解除，則使用該方案，

find遞回函式的意義在于回溯上一階段方案能否找到可替代項，使得整個匹配方案之間兩兩不發生沖突，