BGL グラフがあり、BGL を使用してスパニング ツリーを作成したいと考えています。
指定された頂点から始めて、この頂点に接続するグラフに最短のエッジを追加したいと考えています。そこから先は、これまでに存在するグラフにつながる最短の辺を常に選びたいと思っています。
そのため、サイクルがないというスパニング ツリーの基準を維持しながら、すべての新しいエッジが既にグラフに接続されている必要があるという制約を追加したいと考えています。
これを手動で行うのはそれほど難しくありません。しかし、私は BGL について何かを学びたいので、どのアルゴリズムが自分の問題に最も適しているかを知りたいと思っています。
ツリー内の頂点をツリー内にない頂点に接続する最も明るいエッジを追加することにより、指定した頂点から開始してツリーを成長させているように聞こえます。その場合、MST を提供する Prim のアルゴリズムを実装しています。Cormen、Leiserson、Rivest & Stein による「アルゴリズム」の MST の章でうまく説明されています。
（「これまでに存在するグラフに接続する最短のエッジ」というステートメントは少しあいまいなので、「ように聞こえる」と言います。）
それが Prim アルゴリズムです: http://en.wikipedia.org/wiki/Prim%27s_algorithm
最小スパニング ツリーが得られます。
それを使って多くの BGL を使用するかどうかはわかりませんが、とにかくこのアイデアで難しいのは、「最小エッジ」を見つけることです。ウィキペディア ページの疑似コードを見て、バイナリ ヒープを使用してそれを行う方法を確認してください。 . より複雑にするには、フィボナッチヒープが必要です。