Крускал МСТ без несвязанного множества союз и найди - PullRequest
Новая
       53

Крускал МСТ без несвязанного множества союз и найди

0 голосов
/ 26 октября 2019

Я решал эту проблему HackerRank , которая является лишь слегка измененной версией Крускала, в которой, когда два ребра имеют одинаковый вес, выберите ребро с более низким значением V1 + V2 + edge_weight(V1 и V2 - две вершины ребра).

Для заданного неориентированного взвешенного связного графа найдите действительно специальное поддерево в нем. Действительно специальное поддерево определяется как подграф, состоящий из всех узлов в графе и:

  • Существует только один исключительный путь от узла ко всем остальным узлам.

  • Подграф имеет минимальный общий вес (сумму всех ребер) среди всех таких подграфов.

  • Никаких циклов не сформировано

Чтобы создать действительно специальное поддерево, всегда выбирайте ребро с наименьшим весом. Определите, будет ли это включать цикл. Если так, игнорируйте край. Если есть доступные ребра равного веса:

  • Выберите ребро, которое минимизирует сумму V1 + V2 + edge_weight

  • Если еще естьстолкновение, выберите любой из них.

Я знаю стандартный способ решения проблемы MST Крускала, который состоит в том, чтобы сохранить несвязные множества, а затем для каждого минимального ребра веса выполнить FIND_SET каждой вершины, чтобы проверить, принадлежат ли они одному и тому же дереву. Если нет, сделайте UNION.

Я, однако, реализовал только set(), чтобы отследить, какие вершины были приняты в MST. Вот что я написал - 

def get_MST_weight(edges):
    nodes_in_MST = set()
    # x[2] = edge_weight
    # x[0] and x[1] = the two vertices
    edges.sort(key=lambda x:(x[2], x[0]+x[1]+x[2]))

    weight = 0
    for edge in edges:
        vertex_1 = edge[0]
        vertex_2 = edge[1]
        edge_weight = edge[2]
        if vertex_1 not in nodes_in_MST or vertex_2 not in nodes_in_MST:
            weight += edge_weight
            nodes_in_MST.add(vertex_1)
            nodes_in_MST.add(vertex_2)
    return weight


if __name__ == '__main__':
    no_of_nodes, no_of_edges = map(int, raw_input().split())
    edges = []
    for _ in xrange(no_of_edges):
        edges.append(map(int, raw_input().split()))
    print get_MST_weight(edges)

nodes_in_MST - это набор, содержащий только те вершины, которые мы учли при построении MST. Я думаю код в порядке, но, видимо, это не так, потому что 2 тестовых случая из 6 дают сбой.

Может кто-нибудь, пожалуйста, помогите мне понять, какие сценарии мой кодтерпит неудачу в?

...