3

まず・・・問題は・・・

有向グラフ G = (V, E)、V のソース頂点 s、および E に含まれる一連のツリー エッジ F の例を示して、V に含まれる各頂点に対して、グラフ内の一意の単純なパス ( V, F) s から v への最短経路は G の最短経路ですが、頂点が各隣接リストでどのように順序付けられていても、エッジのセット F は G で BFS を実行しても生成できません。

さて...これは宿題なので、率直な答えは望んでいませんが、見たり試したりするためのアイデアがもっと欲しいです. でも、ここまでで思ったことは…

私は基本的に、特定の頂点へのいくつかの最短経路を持つグラフを作成できると考えました。もちろん、これらのパスの 1 つは BFS にあります。しかし、代替ルートの 1 つを使用して F に適合させることができます。ただし、「頂点がどのように順序付けられていても」私を悩ませている部分は...それをどのように私の処理する。ループ、さまざまな方向フローを試しましたが、まだ何も試していません。

他のアイデアはありますか？

4

3 に答える 3

2 
    3
 s ---- x
 |     /  
1|    / 1
 |   /
 |  /
 y

上の写真が表示されない場合

推定

E = {（（s、x）：3）、（（s、y）：1）、（（y、x）：1）}

ここで、2つのタプルは、ウェイトが付加された順序対です。

エッジセットF = { (s, y), (y, x) }には、グラフのすべての頂点が含まれています。さらに、sからxまでの一意の単純なパスは、グラフ内でsからxまでの最短パスです。ただし、FはBFSによって検出されることはありません。

sから始まり、xとyが検出され、灰色でマークされます。次に、yを探索すると、他の1つの灰色の頂点、つまりxのみが検出され、結果の幅優先ツリーに子孫として追加されません。

于 2011-05-17T03:28:36.227 に答える
1

質問は古いですが、何度も閲覧されているため、別の回答を投稿しています。これは Cormen/Leiserson/Rivest/Stein の Algorithms 本の質問 22-2.6 であり、他の人が遭遇する可能性があります。

上記の回答は、グラフが重み付けされていることを前提としています。グラフが重み付けされていない場合、BFS はどちらの応答でもエッジ セットを生成できます。問題は、グラフが重み付けされているとは言っていません。コーメンでは、重み付けされていないグラフに関するセクションにあります。

これは、重み付けされていない場合の解決策です。手順は次のとおりです。

  1. ソース s から 2 つの頂点 x と y に向かうグラフを取得します。s の出次数は 2 です。x と y はそれぞれ a と b に出て、他のどこにも出ません。
  2. BFS で到達できないツリーは、s から x、x から a、s から y、y から b です。

これは、a と b が x と y から同じ距離にあるため機能します。最初に x をキューに入れると、BFS 経由のパスは x から a と b の両方になります。最初に y をキューに入れると、BFS 経由のパスは y から a と b の両方になります。BFS では、ソリューションのように混在させることはできません。

于 2013-04-09T08:12:11.400 に答える