0

線分のセットがあります。それぞれに 2 つのノードのみが含まれます。線分を結合することによって生成される利用可能な閉じたサイクルを見つけたいです。実際には、複数のオカレンスが存在する場合、最小のループを探しています。できれば、これに対する良い解決策を教えてください。したがって、たとえば、m ケースについてのアイデアを得るために、ポイント インデックスと共にライン リストの下に追加しました。(最初の値 = 行番号、2 番目の 2 つの値はポイント インデックス)

0 - 9 11  
1 - 9 18  
2 - 9 16  
3 - 11 26  
4 - 11 45  
5 - 16 25
6 - 16 49  
7 - 18 26 
8 - 18 25  
9 - 18 21  
10 - 25 49  
11 - 26 45

では、1 行目から始めたとします。つまり、ポイント 9、18 から接続されたループを見つけ始めたとします。次に、その行から「閉じたループ」を取得する方法を (段階的に) 説明していただけますか。

4

1 に答える 1

1

ええと、C ++コードは表示されませんが、C ++ソリューションを提案しようと思います（ただし、これを作成するつもりはありません）。

グラフが無向（有向の場合、s /隣接/エッジ内の頂点/）で、頂点Nを通過する最短のサイクルをすべて見つけたい場合は、次の手順に従うことができると思います。

G <= a graph
N <= some vertex in G
P <= a path (set of vertexes/edges connecting them)
P_heap <= a priority queue, ascending by distance(P) where P is a path

for each vertex in adjacent(N):
  G' = G - edge(vertex, N)
  P = dijkstraShortestPath(vertex, N, G')
  push(P, P_heap)

最短のループを除いてすべてを破棄することもできますが、それはそれほど簡潔ではありません。負のエッジウェイトを許可しない限り（ウェイトに線分長を使用するため、許可しません）、これは機能するはずです。また、幸いなことに、Boost.Graphは、C ++でこれを行うために必要なすべての機能を提供します（ダイクストラのアルゴリズムを実装する必要はありません）。ここでそれに関するドキュメントを見つけることができます：

http://www.boost.org/doc/libs/1_47_0/libs/graph/doc/table_of_contents.html

編集：これを行う前に、最初にリストしたデータからグラフを作成する必要があるため、グラフのproperty_mapを適宜定義し、挿入しようとしている頂点と現在あるすべての頂点の間の距離を確認します。グラフはゼロより大きくなります。それ以外の場合、頂点はすでにグラフにあり、再度挿入したくないためです。

ハッピーグラフ！

于 2011-09-27T18:28:31.813 に答える