python分支限界算法

Question

用python语言实现最小代价生成树问题，利用分支限界算法python

Answer 1

def mctFromLeafValues( arr):
    res = 0
    while len(arr) > 1:
        min_val = min(arr)
        idx = arr.index(min_val)
        if idx > 0 and idx < len(arr) - 1: #有左有右
            left_val, right_val = arr[idx - 1], arr[idx + 1]
        elif idx == len(arr) - 1: #有左没右
            left_val, right_val = arr[idx - 1], 16 #为什么是16？因为最大只有15
        elif idx == 0: #有右没左
            left_val, right_val = 16, arr[idx + 1]
            
        res += min(min_val * left_val, min_val * right_val)
        arr.remove(min_val) #把当前最小值删掉，已经用完了
    return res
arr = [5,1,4]
print(mctFromLeafValues(arr))