0

私は最近、グラフとアルゴリズムを発見し、ユーザーとエンティティという2つの異なるタイプの頂点に関連する特定の問題を解決しようとしています。詳細は以下のとおりです。

  • グラフは
  • AからBまでのすべてのパスを見つけようとしています
  • Aは常にユーザーです
  • Bはユーザーまたはエンティティにすることができます
  • Bがユーザーの場合、検索の最大深度は3エッジです。
  • Bがエンティティの場合、最大深度は2エッジです
  • ユーザーがAでない限り、ユーザーからアウトバウンドのエッジをトラバースすることはできません。

グラフには2種類の頂点がありますが、2部グラフではありません。

これまでのところ、隣接リストの頂点インデックス付き配列を保持するグラフオブジェクトを作成することができました。隣接リストはリンクリストに基づいています。

All Pathsアルゴリズムに何らかのバリエーションが必要だと思いますが、よくわかりません。さらに、DFSとBFSのどちらを見るべきかわからない。

ほとんどの例はJavaであるため、私はPHPで作業していますが、これは問題を複雑にします。私が本当に欲しいのは擬似コードです。

何か案は？ありがとう！

4

1 に答える 1

2

ある種のLDAP実装をトラバースしているようです。一般的なアルゴリズムが必要な場合は、コーディングが簡単なため、DFSを使用してください。深さが変わらない限り、これを行うのはやり過ぎです。

最も一般的な方法

 dfs(A,B):
     return dfs(A,B,1);

 dfs_(u,B,depth):
     if u == B:
          return u;

     if (u is User and depth > 3) or (u is Group and depth > 2):
          return None;       

     out = [];
     for children of thing:
          return max( dfs_(children,depth+1) ) # take the non-null one
     out.append(u);
     return out;
于 2012-12-06T00:54:34.047 に答える