Python中Prim的MST算法

Question

我正在尝试实现Prim的算法来处理一个以城市为顶点的图，但是我被卡住了。任何建议都将不胜感激。你知道吗

我从一个txt文件中读取数据，并试图得到分数（总距离）的输出和元组中的边列表。例如，从Houston开始，第一条边将是（'Houston'、'SAN ANTONIO'）。你知道吗

我使用字典实现了图/树，其中包含相邻顶点及其距离，如下所示：

{'HOUSTON': [('LUBBOCK', '535'), ('MIDLAND/ODESSA', '494'), ('MISSION/MCALLEN/EDINBURG', '346'), ('SAN ANTONIO', '197')], 
'HARLINGEN/SAN BENITO': [('HOUSTON', '329')], 
'SAN ANTONIO': [], 
'WACO': [], 
'ABILENE': [('DALLAS/FORT WORTH', '181')], 
'LUBBOCK': [('MIDLAND/ODESSA', '137')], 
'COLLEGE STATION/BRYAN': [('DALLAS/FORT WORTH', '181'), ('HOUSTON', '97')], 
'MISSION/MCALLEN/EDINBURG': [], 
'AMARILLO': [('DALLAS/FORT WORTH', '361'), ('HOUSTON', '596')], 
'EL PASO': [('HOUSTON', '730'), ('SAN ANTONIO', '548')], 
'DALLAS/FORT WORTH': [('EL PASO', '617'), ('HOUSTON', '238'), ('KILLEEN', '154'), ('LAREDO', '429'), ('LONGVIEW', '128'), ('LUBBOCK', '322'), ('MIDLAND/ODESSA', '347'), ('MISSION/MCALLEN/EDINBURG', '506'), ('SAN ANGELO', '252'), ('SAN ANTONIO', '271'), ('WACO', '91'), ('WICHITA FALLS', '141')], 
'KILLEEN': [], 
'SAN ANGELO': [], 
'MIDLAND/ODESSA': [], 
'WICHITA FALLS': [], 
'CORPUS CHRISTI': [('DALLAS/FORT WORTH', '377'), ('HOUSTON', '207')], 
'AUSTIN': [('DALLAS/FORT WORTH', '192'), ('EL PASO', '573'), ('HOUSTON', '162')], 
'LONGVIEW': [], 
'BROWNSVILLE': [('DALLAS/FORT WORTH', '550'), ('HOUSTON', '355')], 
'LAREDO': [('SAN ANTONIO', '157')]} 

到目前为止，我掌握的情况如下：

import csv
import operator

def prim(file_path):
    with open(file_path) as csv_file:
        csv_reader = csv.reader(csv_file, delimiter = "\t")
        dict = {}
        for row in csv_reader:
            if row[0] == 'City':
                continue
            if row[0] in dict:
                dict[row[0]].append((row[1],row[3]))
                if row[1] not in dict:
                    dict[row[1]] = []
            else:
                dict[row[0]] = [(row[1], row[3])]

    V = dict.keys()
    A = ['HOUSTON']
    score = 0 # score result
    E = [] # tuple result

    while A != V:
        for x in A:
            dict[x].sort(key=lambda x: x[1])
            for y in dict[x]:
                if y[0] in V and y[0] not in A:
                    A.append(y[0])
                    E.append((x, y[0]))
                    score += int(y[1])
                    break
            break
        break

    print("Edges:")
    print(E)
    print("Score:")
    print(score)

prim("Texas.txt")

由于最后一个break语句，这给出了正确的第一条边，但是当我删除break语句时，它会无限循环，我无法确切地找出原因或如何修复它。我意识到我实现这个算法可能是完全错误和低效的，所以我真的很感激任何提示或建议从这里/什么做不同的，为什么。提前谢谢！！你知道吗