c++ - prim_minimum_spanning_tree() boost 函数

Question

我正在尝试将 Prim 算法与 boost 库的 prim_minimum_spanning_tree 函数结合使用，使用包含我所有图形点的文件。我使用 boost 库的 kruskal_minimum_spanning_tree 函数成功创建了我想要的图形。

但是对于 prim_minimum_spanning_tree，我只能得到每个点的直接父级，所以我的图表并不完整。

我使用了 boost 文档中给出的示例:

对于原始:http://www.boost.org/doc/libs/1_47_0/libs/graph/example/prim-example.cpp

和克鲁斯卡尔人 http://www.boost.org/doc/libs/1_47_0/libs/graph/example/kruskal-example.cpp

一个具体的例子:我有这个点文件:

10
0 0.655171
0.304819 0.674978
0.106754 0.516587
0.489669 0.602466
0.369945 0.256661
0.374187 0.825587
0.172704 0.2978
0.643544 0.789666
0.987823 0.800592
0.464248 0.538987

使用 krukal 函数我得到:

3 <--> 9
1 <--> 5
0 <--> 2
1 <--> 3
6 <--> 4
6 <--> 2
3 <--> 7
2 <--> 1
8 <--> 7

使用 prim 函数我得到:

1 <--> 5
2 <--> 0
3 <--> 9
4 <--> 6
5 <--> 1
6 <--> 4
7 <--> 3
8 <--> 7
9 <--> 3

我有这些图表的绘图，但我不能发布图片或多个链接。但如您所见，我错过了 3 个链接。

我怎样才能得到与使用 prim 函数的 kruskal 相同的结果？

谢谢，

PS : 我使用示例代码作为基础并尝试了一系列修改但没有成功，在网络或文档上找不到任何有用的信息。

Answer 1

我已经找到了我自己问题的答案，可能对其他人有用。

我将这些点链接了两次，这适用于 kruskal 的算法，但不适用于 prim 的算法，例如在我的边缘我有:

0 <--> 1
1 <--> 0

对于 prim 算法，我应该只将这些点链接一次。