c++ - 使用 BGL 创建生成树

Question

我有一个 BGL 图，想使用 BGL 创建一个生成树。

从指定的顶点开始，我想将最短的边添加到与该顶点相连的图形中。从那时起，我想始终选择与迄今为止存在的图形相连的最短边。

因此，我想添加一个约束，即每条新边都必须已经连接到图形，同时保持没有循环的生成树标准。

手工操作并不难；但是因为我想学习一些关于 BGL 的知识，所以我想知道哪种算法最适合我的问题。

Answer 1

这听起来像是您正在种植一棵树，从您指定的顶点开始，通过添加将树中的顶点连接到不在您的树中的顶点的最轻边。如果是这种情况，您正在实现 Prim 的算法，它确实为您提供了 MST。在 Cormen、Leiserson、Rivest 和 Stein 的“算法”的 MST 章节中对此进行了很好的描述。

(我说“听起来像”是因为“与目前存在的图相连的最短边”这个说法有点含糊。)