Алгоритм MST Прима в Python

Есть три основные проблемы с вашей реализацией:

1. Ваш график хранится как ориентированный граф. Алгоритм Прима нельзя применять к ориентированным графам (ссылка). Если вы действительно хотите обработать ориентированный граф, комментарии в связанном вопросе содержат информацию о том, как вычислить MST-эквивалент ориентированного графа (ссылка).

   Это также связано с тем, почему ваш алгоритм застревает: он исследует все вершины, достижимые через направленное ребро из начальной вершины. Вершин в графе больше, но они не могут быть достигнуты из начальной вершины при обходе ребер в фиксированном направлении. Следовательно, алгоритм не может увеличить промежуточное дерево, чтобы включить дополнительные вершины, и зависает.

   Однако я предполагаю, что вы действительно хотите, чтобы граф был неориентированным. В этом случае вы могли бы, например, вычислить симметричное замыкание графа, продублировав каждое ребро в обратном направлении. Или, в качестве альтернативы, вы можете адаптировать свой алгоритм для проверки как исходящих, так и входящих ребер.

2. В алгоритме Прима каждая итерация добавляет ребро к промежуточному дереву. Это делается путем выбора ребра минимального веса, соединяющего промежуточное дерево с вершиной из оставшейся части графа. Однако в вашем коде вместо этого вы сортируете исходящие ребра каждой вершины в промежуточном дереве по их весу и добавляете все ребра, указывающие на вершину, которая еще не включена в промежуточное дерево. Это даст вам неправильные результаты. Рассмотрим следующий пример:

   

   Предположим, мы начинаем с 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 в том же порядке, в котором ключи были вставлены в словарь.

   Следовательно, вы должны использовать другой подход для условия цикла. Одним из возможных решений было бы инициализировать V и A как sets, то есть с V = set(dict.keys()) и A = set(['HOUSTON']). Это позволит вам сохранить A != V в качестве условия цикла. Или вы можете сохранить A список, но только проверять, равен ли размер A размеру V на каждой итерации. Поскольку алгоритм вставляет в A только в том случае, если вершина еще не содержится в A, когда len(A) == len(dict) следует, что A содержит все вершины.

Вот пример фиксированного кода. Сначала выполняется симметричное замыкание входного графа. В качестве условия цикла проверяется, не равен ли размер A общему количеству вершин. В цикле он вычисляет ребро минимального веса, которое соединяет вершину в A с вершиной, не входящей в 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).