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

Kruskal算法初始化空集

kruskals-algorithm minimum-spanning-tree set graph python

Maxxx · 技术社区 · 7 年前

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

如果我有一个用

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

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

我试过这样的方法:

v_set = [0] * 11

1 回复 | 直到 7 年前

Reblochon Masque 7 年前

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

[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

推荐文章

Rosie Lomas · 在ggplot中设置数字刻度

2 年前

Mahin Rahman · 我的培训和测试图表保持不变,有人能帮我解释一下,或者解释一下我哪里出错了?

4 年前

nedlaback · 在O(V+E)图中寻找瓶颈边

8 年前

Skampak · R visNetwork:创建新类型的边

8 年前

Habil Ganbarli · 在完整图上进行MST聚类(用于余弦相似性)

8 年前

Vaibhav · 在r Shinny中的Visnetwork中撤消单击事件

8 年前

Anuja · 长度l在R中的最短路径

8 年前

Cbhihe · 优化Neo4j查询,有条件地创建新关系

8 年前

fghjk · 绘制轨迹(python)

8 年前

LBerger · 计算图形图像中的名称使用(TensorBoard)

8 年前