2

私は、何度か、またいくつかの雇用主のために、独自のグラフ データ構造を実装する理由がありました。アクセスの完全な柔軟性のために、Nodeクラスとクラスの 2 つのクラスを使用してこれを実装する必要があることがよくありEdgeます。

ノードには一連の発信エッジ (およびおそらく着信エッジ) があり、エッジにはソースとシンク (両方ともノードへのマネージド ポインター) があります。多くの場合、これらのグラフにはサイクルがあります。

私の質問は、特にグラフを変換および変更するときに、そのようなグラフのデータ構造でメモリを管理する最良の方法は何ですか? 循環が存在するため、参照カウントには向いていません (ウィーク ポインターを使用しようとしても、循環がどこにあるのか、したがってどこにウィーク リンクを配置するのかが明確でないことがよくあります)。

私のさまざまな実装では、グラフおよびグラフへのエントリ ポイントのリストとは別に、割り当てられたすべてのノードとエッジを追跡することがよくありました。次に、実際には単純なガベージ コレクターを実装しました。一定の間隔で、さまざまなグラフ変換 (いくつかのノード/エッジのリンク解除を含む) を適用して、以下を含む gc を実行します。

  1. エントリ ポイント ノードから開始し、そこからグラフを介して到達可能なすべてのノードとエッジをアクティブとしてマークします (BFS/DFS 経由)。
  2. 完全なセット内のすべてのノードとエッジを繰り返し処理し、前の手順でマークされていないものを削除します。

これはうまく機能します (そして、マーク/スイープの単純な実装です)。しかし、それはいつも少し不器用に見えてしまいます。誰かがこの問題、またはより良い代替ソリューションについての洞察を持っていますか?

4

1 に答える 1

0

有限グラフがある場合は、ポインター構造として表現しないでください。代わりに、次のいずれかを使用します

  • 辺のリスト ( vector、listなど) と頂点のリスト、または
  • 頂点からインデックスへのマッピング (mapまたは) と、頂点とが接続されているunordered_mapかどうかを示すブール値 (重み付きグラフの場合は float) の行列 (2 次元配列) 。ij

前者の表現は隣接リストと呼ばれ、後者は隣接行列と呼ばれます。どちらを使用するかは、使用しているグラフと実行する操作によって異なります。どちらもメモリ管理の点ではるかに単純であり、多くの場合、ポインター構造よりもはるかにパフォーマンスが優れています。

于 2012-07-09T22:25:01.770 に答える