Найти минимальный вес графика

Question

Я пытаюсь сделать программу, которая вычисляет минимальный вес span using алгоритм Kruskal, Я отсортировал края, используя их в порядке возрастания и поместил их в список 2d. тогда я должен написать метод, чтобы получить минимальный вес, используя sortededge, взять для образца, sortededge = [['1', '2', '1'], ['5', '6', '1'], ['2', '4', '2'], ['3', '6', '2'], ['3', '5', '3'], ['4', '6', '3'], ['3', '4', '5'], ['1', '3', '6']] метод

vertexcheck = [] 
minimumdistance = 0 
def MSW: 
    for i in range(len(sortededge)): 
     if (sortededge[i][0] not in vertexcheck) or (sortededge[i][1] not in vertexcheck): 
      if (sortededge[i][0] not in vertexcheck): 
       vertexcheck.append(sortededge[i][0]) 


      if (sortededge[i][1] not in vertexcheck): 
       vertexcheck.append(sortededge[i][1]) 
      minimumdistance += int(sortededge[i][2]) 

но оленья кожа работа для всех графиков и я хотел бы получить любую помощь

Answer 1

Ваша реализация алгоритма неверна.

Пусть пример, где ваши алго терпит неудачу:

И край будет выглядеть после сортировки:

Ребра:

1, 2, 1 
    3, 4, 2 
    2, 3, 5 

в 1-е итерации вы поместите 1 и 2 в вашей вершине. обновленный vertexcheck = [1,2]
на второй итерации вы разместите 3 и 4 в своей вершине. updated vertexcheck = [1,2,3,4]
Но на третьей итерации вы не можете добавить 2-> 3 ребра, потому что обе вершины присутствуют в вашем вершинном чеке.

Вот почему ваша реализация дает неправильный вывод :(

На самом деле, для реализации Крускала вы должны знать и использовать алгоритм структуры данных под названием Union-Find, который говорит вам, если текущие узлы, которые вы пытаетесь подключиться уже подключены :)

Если они уже подключены, то пропустите преимущество, потому что они уже связаны с меньшими затратами :) иначе соединить их ...

Как много реализации доступны для MST с помощью питона , я не буду беспокоить вас один :)

Вы можете найти псевдокод здесь: Kruskal's_algorithm

И пример реализации: Kruskal's_implementation