代码之家 › 专栏 › 技术社区 › Maxxx

Kruskal算法初始化空集

kruskals-algorithm minimum-spanning-tree set graph python

0

Maxxx · 技术社区 · 8 年前

Kruskal算法的一个要求是首先为顶点初始化一个空集,但是我有问题。

如果我有一个用

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

如果第一个索引值是源顶点,第二个值是目标顶点,第三个值是权重,那么如何为顶点初始化空集?

我试过这样的方法:

v_set = [0] * 11

1 回复 | 直到 8 年前

1

0

Reblochon Masque 8 年前

可以将顶点表示为一个由顶点编号和边列表组成的列表,作为与目标顶点和边的权重相对应的元组:

[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