1

xグラフ内のノードからノードへの道があるかどうかを検証するアルゴリズムを作成する必要がありyます。グラフのエッジには一連の権利が付与されています (r, w, eなど)。私のアルゴリズムには|e| + |v|複雑さが必要です。ノードの前のノードとのエッジがパラメータとして与えられた特定の権限セットを持っているノードのみを通過できます。

たとえば、set of rights: がr, w, e, gあり、これらの権利をエッジにランダムに分散し、検索メソッドのパラメーターとして set of rights: を指定した場合e, g、エッジが right を持つノードのみを通過できe,gます。

|e| + |v|DFSアルゴリズムが時間の複雑さを正しく思い出し|e| + |v|、エッジが必要な権利のセットを持っているかどうかを検索する必要がある場合、時間の複雑さでこれを行うにはどうすればよいですか。

4

1 に答える 1

2

幅優先検索(DFS とは異なり、最短パスを見つけます)を適用して、必要な権限を持つノードのみを考慮に入れるように少し変更する必要があります。

これが疑似コードです。Javaに翻訳できると確信しています：

procedure BFS(G,v):
        create a queue Q
        create a set V
        enqueue v onto Q
        add v to V
        while Q is not empty:
                t ‹ Q.dequeue()
                if t is what we are looking for:
                        return t
             for all edges e in G.adjacentEdges(t) do
                     u ‹ G.adjacentVertex(t,e)
                     if u is not in V and t.hasRights(allowedRights):
                                add u to V
                                enqueue u onto Q
     return none

ウィキペディアと違うのはt.hasRights(allowedRights)状態を確認するだけです。

Java HashSetを使用すると、一連の権利のチェックは O(1) 時間で簡単に実行でき、BFS アルゴリズムの E+V の複雑さは何も追加されません (使用可能な権利の数が一定であると仮定)。

各ノードに権利のセットを保存し、必要なすべての権利がセットに含まれているかどうかを確認します ( HashSet.contains(Object)は O(1) です)。

また、自分の権利を次のように表し、EnumSetenumを使用して権利セットを格納することもできます。EnumSet はビット ベクトルとして実装されるため、セットと同じくらい高速です。

于 2013-10-05T09:13:10.620 に答える