0

私は有向グラフについて読んでいます。アプリケーションで抽象グラフ データ型を動作させることができましたが、特に直感的ではなく、通常の多次元配列に置き換えることを検討しています。

私のグラフはまばらで非循環的です。各頂点は、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]

さて、このグラフでできるようにしたい主なことは次のとおりです。

  1. 階層としてナビゲートします。一部の子頂点が複数のカテゴリ (例: #5) で機能することはわかっていますが、それがこの特定のユース ケースに必要なことです。この点については、配列とグラフの実際の違いはわかりません。
  2. 重複のないリスト (頂点名に従ってアルファベット順) としてレイアウトします。おそらく DFS を実行し、訪問した頂点にフラグを立てて、それらを複数回探索しないようにします。しかし、私が見る限り、これはグラフまたは配列のいずれかを使用して、同じコストで達成可能です。
  3. ポイントの任意のペアに対して「すべてのパス」分析を実行します。「すべてのパス」が必要なため (つまり、単に到達可能性をチェックしているわけではありません)、グラフ全体をトラバースする必要があるように思われますが、配列よりもグラフに利点が見られません。

何かが足りない気がしますが、指を置くことはできません。あなたはできる???アイデア、提案、洞察、またはアドバイスを喜んで受け入れます...(ちなみに、私はPHPを使用しており、データソースはリレーショナルDBです。ただし、これが実際の違いを生むとは思いません)。

ありがとう!

4

2 に答える 2

2

理解する必要があることの 1 つは、有向グラフ(またはダイグラフ) は概念であるのに対し、連想配列データ構造であるということです。

有向グラフの概念のインスタンスは、さまざまなデータ構造に格納できます。そのうち最も一般的なものは、このウィキペディア ページで見つけることができます。

多次元配列で何をしているのかわかりません...すべてのパスを保存していますか? N³ スペースが複雑になり、構築に問題が生じます。ツリーベースの構造は、少なくともより効率的です。

グラフでやりたいことは次のとおりです。

  1. 階層としてナビゲートします。基本的な digraph の概念では、階層を上ることはできませんが、逆グラフも簡単に保存できます (特に行列ベースの表現では、2 つの値ではなく 3 つの値を使用するだけです - 前方、後方、および何もありません)。
  2. name に従って、リストとしてレイアウトします。名前をどこかに保存する必要がありますが (サイド マップまたは頂点オブジェクトのいずれか)、名前に従って他のものを並べ替えるよりも難しいことはありません。
  3. 「すべてのパス」分析を行います。おそらく、DP とパスの共有表現を使用して、線形の複雑さ (パスの数) を回避できます。
于 2013-01-17T14:45:19.363 に答える
0

データ構造が複雑すぎるようです。有向グラフを多次元配列として表す場合、ほとんどの場合、2次元であるため、

$array[$x][$y]

はブール値であり、グラフのノード$xからノード$yへのエッジがある場合にのみTRUEになります。あなたの例では、例えば

$array[1][2] = TRUE
$array[1][5] = FALSE

しかし、まばらなグラフの場合、このブール行列表現を使用することは通常適切ではありません。通常、すべてのノードをエッジのあるノードのセットにマップする1次元配列があります。

$array[1] = { 2, 3, 4 }

ここで、{...}は、ある種の順序付けられていないコレクションデータ構造を意味します。これには、たとえば、バイナリ検索ツリーまたはハッシュセット(ハッシュテーブル)があります。

このデータ構造により、特定のノードからアークが存在するノードをすばやく見つけることができます。これは、グラフアルゴリズムの重要な機能です。

グラフを逆方向にトラバースできるようにしたい場合もあります。その場合、ノードを先行ノードのリストにマップする別の配列があります。

于 2013-01-17T13:11:27.753 に答える