私は有向グラフについて読んでいます。アプリケーションで抽象グラフ データ型を動作させることができましたが、特に直感的ではなく、通常の多次元配列に置き換えることを検討しています。
私のグラフはまばらで非循環的です。各頂点は、1 つの特定の「マスター」頂点から到達可能です。ツリーの場合、このマスター頂点は「ルート」になります。ソーシャル ネットワークの場合、このマスター頂点は「私」になります。
私のグラフには数十万の頂点があるかもしれませんが、その深さは有限です: 任意の 2 つのノード間の最大距離は 3 つのエッジです。
基礎となるデータ表現は隣接リストです。小さな例は次のようになります。
Head | Tails
--------------
1 | 2, 3, 4
2 | 5
3 | 5
4 | 5
5 | 6
グラフ データ型の代わりに通常の multi-dim 配列を使用していた場合、次のようになります。
$me[1][2][5][6]
$me[1][3][5][6]
$me[1][4][5][6]
さて、このグラフでできるようにしたい主なことは次のとおりです。
- 階層としてナビゲートします。一部の子頂点が複数のカテゴリ (例: #5) で機能することはわかっていますが、それがこの特定のユース ケースに必要なことです。この点については、配列とグラフの実際の違いはわかりません。
- 重複のないリスト (頂点名に従ってアルファベット順) としてレイアウトします。おそらく DFS を実行し、訪問した頂点にフラグを立てて、それらを複数回探索しないようにします。しかし、私が見る限り、これはグラフまたは配列のいずれかを使用して、同じコストで達成可能です。
- ポイントの任意のペアに対して「すべてのパス」分析を実行します。「すべてのパス」が必要なため (つまり、単に到達可能性をチェックしているわけではありません)、グラフ全体をトラバースする必要があるように思われますが、配列よりもグラフに利点が見られません。
何かが足りない気がしますが、指を置くことはできません。あなたはできる???アイデア、提案、洞察、またはアドバイスを喜んで受け入れます...(ちなみに、私はPHPを使用しており、データソースはリレーショナルDBです。ただし、これが実際の違いを生むとは思いません)。
ありがとう!