时间戳

首页 > 解决方案 > Prim 的 Python 中的 MST 算法

python - Prim 的 Python 中的 MST 算法

问题描述

我正在尝试为由城市作为顶点组成的图实现 Prim 算法，但我被卡住了。任何建议将不胜感激。

我正在从 txt 文件中读取数据并尝试获取分数（总距离）的输出和元组中的边列表。例如，从休斯顿开始，第一条边将是 ('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 语句时，它会无限循环，我无法确切地弄清楚为什么或如何修复它。我意识到我可能完全错误且低效地实施了这个算法，所以我非常感谢任何关于从这里去哪里/做什么不同以及为什么做的提示或建议。先感谢您！！

标签： pythonminimum-spanning-treeprims-algorithm

解决方案

您的实施存在三个主要问题：

  1. 您的图存储为有向图。Prim 的算法不能应用于有向图（参考）。如果您真的想处理有向图，链接问题中的评论提供了有关如何计算有向图的 MST 等效项的信息（参考）。

    这也与您的算法卡住的原因有关：它探索通过起始顶点的有向边可到达的所有顶点。图中的顶点比较多，但是沿固定方向遍历边时，无法从起始顶点到达。因此，该算法不能增长中间树以包含更多的顶点并卡住。

    但是，我假设您实际上希望图形是无向的。在这种情况下，您可以通过反向复制每条边来计算图形的对称闭包。或者，您可以调整您的算法来检查传出和传入边缘。

  2. 在 Prim 算法中，每次迭代都会向中间树添加一条边。这是通过选择连接中间树与图其余部分的顶点的最小权重边来完成的。但是，在您的代码中，您改为按其权重对中间树中每个顶点的传出边进行排序，并添加所有指向尚未包含在中间树中的顶点的边。这会给你不正确的结果。考虑以下示例：

    在此处输入图像描述

    假设我们从 开始a。您的方法按权重对边缘进行排序，a然后按顺序添加它们。因此，它将边a-b和添加a-c到中间树。图的所有顶点现在都包含在中间树中，因此算法终止。但是，该树b-a-c不是最小生成树。

    因此，a您应该从中选择最小边，即a-b. 然后，您应该从中间树的任何顶点中搜索最小权重边。这将是边缘b-c。然后，您将此边添加到中间树，最终生成 MST a-b-c。

  3. A != V即使A包含图形的每个顶点，循环条件也永远不会得到满足。这是因为A是一个列表，V是 的结果dict.keys()，它不是一个列表，而是一个视图对象。视图对象是可迭代的，并且键将按照插入时的顺序给出，但它永远不会评估为等于列表，即使列表包含相同的项目。

    即使您将V变成一个列表（例如，使用V = list(dict.keys())，这还不够，因为列表只有在它们包含相同顺序的相同项目时才相等。但是，您不能保证算法会将顶点插入A到与插入字典的键的顺序相同。

    因此，您应该对循环条件使用其他方法。一种可能的解决方案是将Vand初始化A为sets，即使用V = set(dict.keys())and A = set(['HOUSTON'])。这将允许您保持A != V循环条件。或者你可以保留A一个列表，但只检查每次迭代的大小A是否等于 的大小V。A由于该算法仅在顶点尚未包含在 中时才插入A，当 时len(A) == len(dict)，它遵循A包含所有顶点。

这是固定代码的示例。它首先采用输入图的对称闭包。作为循环条件，它检查 的大小A是否不等于顶点总数。在循环中，它计算连接顶点 inA和顶点 not in的最小权重边A：

    # Compute symmetric closure
    for v, edges in dict.items():
        for neighbor, weight in edges:
            edges_neighbor = dict[neighbor]
            if (v, weight) not in edges_neighbor:
              dict[neighbor].append((v, weight))

    A = ['HOUSTON']
    score = 0
    E = []

    while len(A) != len(dict):

        # Prepend vertex to each (target,weight) pair in dict[x]
        prepend_source = lambda x: map(lambda y: (x, *y), dict[x])
        edges = itertools.chain.from_iterable(map(prepend_source, A))

        # Keep only edges where the target is not in A
        edges_filtered = filter(lambda edge: edge[1] not in A, edges)

        # Select the minimum edge
        edge_min = min(edges_filtered, key=lambda x: int(x[2]))

        A.append(edge_min[1])
        E.append((edge_min[0], edge_min[1]))
        score += int(edge_min[2])

请注意，此实现仍然假设图是连接的。如果要处理断开连接的图，则必须对图的每个连接组件应用此过程（导致 MST 森林）。

推荐阅读