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

Question

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

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

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

用手来做这件事并不难。但是因为我想了解一些关于 BGL 的知识，所以我想知道哪种算法最适合我的问题。

score 4 · Accepted Answer

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

（我说“听起来像”是因为“与迄今为止存在的图相连的最短边”这句话有点含糊。）

score 2 · Accepted Answer

你会得到一个最小生成树！

不确定你是否会倾向于使用 BGL，但无论如何，这个想法的困难在于找到“最小边缘”：查看维基百科页面上的伪代码，看看如何使用二进制堆来完成. 为了获得更好的复杂性，您将需要斐波那契堆。

2 回答 2