Алгоритм Крускала, инициализирующий пустое множество

Question

Одним из требований алгоритма Крускала является сначала инициализация пустого набора для вершин, но у меня возникают проблемы с ним.

Если бы у меня был график, представленный

[1,2,4]
[10,3,5]
[6,1,3]

, где первое значение индекса - это вершина источника, а второе - вершина назначения, а третье - вес. Как бы я инициировал пустой набор для вершины?

Я пробовал что-то вроде:

v_set = [0] * 11

но я ограничиваю вершину только до 11, следовательно, если бы была, например, вершина 12, это привело бы к ошибке индекса вне диапазона.Был бы признателен за помощь в этом.

Answer 1

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

Ваш график может выглядеть примерно так:

[1, [(2, 14), (3, 10)]]
[2, [(1, 14), (4, 2)]]
[3, [(1, 10)]]
[4, [(2, 2)]]

где:

       edge
      -----
[3, [(1, 10)]]
 ^    ^   ^ weight
 |    destination vertice   
 Vertice number