2

私は、2つのノードが接続されているかどうか、および接続されている場合はそれらの間の分離度、つまりソースノードからターゲットノードに到達するために移動する必要のあるノードの数を判別する必要があるグラフライブラリに取り組んでいます。

重み付けされていないグラフであるため、bfsは最短経路を示します。しかし、ターゲットノードに到達する前に検出されたノードの数を追跡する方法。

新しいノードの検出時に増分する単純なカウンターは、パスに含まれていないノードを含む可能性があるため、間違った答えを返します。

別の方法は、これを均一な重み付きエッジの重み付きグラフとして扱い、Djkastraの最短経路アルゴリズムを使用することです。

しかし、私はそれをbfsだけで管理したいと思います。

どうやってするの ？

4

3 に答える 3

2

BFS中に、各ノードにその前のノード（ノードが最初に検出されたエッジに沿ったグラフ内のノード）へのポインターを格納させます。次に、BFSを実行すると、宛先ノードから送信元ノードまでこのポインターを繰り返したどることができます。これにかかるステップ数を数えると、宛先からソースノードまでの距離がわかります。

または、ノード間の距離を繰り返し決定する必要がある場合は、Floyd-Warshall全ペア最短経路アルゴリズムを使用することをお勧めします。これを事前に計算すると、ノードの任意のペア間の距離をすぐに読み取ることができます。

お役に立てれば！

于 2013-01-14T17:52:14.167 に答える
2

単純なカウンターが機能しない理由がわかりません。この場合、幅優先探索は間違いなく最短経路を提供します。したがって、実行したいのは、「count」と呼ばれるすべてのノードにプロパティをアタッチすることです。ここで、まだアクセスしていないノードに遭遇したら、「count」プロパティに現在のカウントを入力して次に進みます。

後でノードに戻った場合は、入力されたcountプロパティによって、ノードがすでにアクセスされていることを知る必要があります。

編集：ここで私の答えを少し拡張するには、グラフをナビゲートするときに開始ノードからの分離の程度を追跡する変数を維持する必要があります。キューにロードする新しい子のセットごとに、必ずその変数の値をインクリメントしてください。

于 2013-01-14T17:53:11.220 に答える
0

知りたいのが距離だけであり（距離が大きすぎる場合は検索を中断する可能性があります）、すべてのエッジの重みが同じ（つまり1）の場合：

擬似コード：

Let Token := a new node object which is different from every node in the graph.
Let Distance := 0
Let Queue := an empty queue of nodes
Push Start node and Token onto Queue 

(Breadth-first-search):
While Queue is not empty:
    If the head of Queue is Target node:
        return Distance
    If the head of Queue is Token:
        Increment Distance
        Push Token onto back of the Queue
    If the head of Queue has not yet been seen:
        Mark the head of the Queue as seen
        Push all neighbours of the head of the Queue onto the back of Queue
    Pop the head of Queue
(Did not find target)
于 2013-01-14T18:31:06.210 に答える