c++ - ブースト グラフのレベル順トラバーサル

Question

A,B,C,D,E,F私はブースト グラフ ライブラリを初めて使用し、有向グラフが与えられた場合、頂点のレベル順ベクトル、つまり与えられた頂点とエッジを構築したいと考えています。

A->B、A->C、B->D、C->E、E->F

グラフ（またはツリー）で同じ深さにある頂点のベクトルを取得します。

[ [A]、[B、C]、[D、E]、[F] ]

ご協力いただきありがとうございます。

Answer 1

これまでに何を試しましたか？

これは、私がこれに取り組む方法の一般的で高レベルな説明です。

1. 「レベル順ベクトル」を保持するデータ構造を作成する

2. この構造と現在の深度カウンターを保持するビジターを作成します

3. A から始まるグラフ トラバーサルを実行します。これにより、A からの深さと「レベル順ベクトル」の正しい場所にある現在のノードでビジターが更新されます。

別の方法：

1. バンドルされたプロパティ機能を使用して、各ノードの深さを保存します

2. グラフをトラバースし、ノード プロパティを正しい深さで更新します。

3. ノードを反復処理して、前のステップでトラバーサルによって設定された深度プロパティに従って、「レベル順ベクトル」内のどこに配置する必要があるかを決定します。

参考までに、幅優先トラバーサルの方法を次に示しますhttp://www.boost.org/doc/libs/1_54_0/libs/graph/doc/breadth_first_search.html