2

突然頭に浮かびました。

BFSグラフトラベラルで2色のみを使用するのはなぜですか

と3はDFSに必要ですか？

例：ウィキペディアから：

BFS：

procedure BFS(G,v):
2      create a queue Q
3      enqueue v onto Q
4      mark v
5      while Q is not empty:
6          t ← Q.dequeue()
7          if t is what we are looking for:
8              return t
9          for all edges e in G.adjacentEdges(t) do
12             u ← G.adjacentVertex(t,e)
13             if u is not marked:
14                  **mark u**
15                  enqueue u onto Q
16     return none

DFS：

  procedure DFS(G,v):
2      label v **as explored**
3      for all edges e in G.adjacentEdges(v) do
4          if edge e is unexplored then
5              w ← G.adjacentVertex(v,e)
6              if vertex w is unexplored then
7                  label e as a **discovery edge**
8                  recursively call DFS(G,w)
9              else
10                 label e as a **back edge**

DFSには2色では不十分なのはなぜですか？なぜ3色がBFSに冗長なのですか？

ここに別のBFS（今回は3色）があります：

ここに画像の説明を入力してください

4

3 に答える 3

3

基本的に異なるタイプの情報を表すために使用されるため、2つのアルゴリズムのそれぞれに異なる数の色があります。

BFSとDFSの両方で、ノードは未探索ノードまたは探索済みノードのいずれかとしてマークする必要があります。この情報を表すには、少なくとも2色が必要です。

上記のDFS実装では、実装は色を使用して、エッジを「検出エッジ」（アルゴリズムによって生成される深さ優先探索ツリーを形成するエッジ）または「バックエッジ」（より深い位置から移動するエッジ）のいずれかに分類します。 DFSツリーの一部からDFSツリーの浅い部分へ）。これらの色は、ノードではなく、エッジの色付けに使用されます。その結果、エッジには3つの色が必要になります。未探索のエッジ、「検出」エッジ、およびバックエッジです。

お役に立てれば！

于 2013-02-03T19:57:12.847 に答える
0

これを簡単な言葉で説明すると、BFSでは、ノードにアクセスすると、そのすべての隣接ノードにもアクセスされることを意味し、その頂点に再度アクセスする必要はありません。しかし、DFSには、バックトラッキングと呼ばれる操作があります。これは、すでにアクセスしたノードに再度アクセスする必要があり、そのすべてのネイバーに一度にアクセスする必要がないことを意味します。したがって、3番目の色の灰色を使用すると、「はい、アクセスしました。印刷する必要はありませんが、このノードにはまだアクセスされていないネイバーがあります。」

于 2017-10-26T04:44:13.320 に答える
0

ノードにも3色が必要なBFSのアプリケーションが存在する可能性があります。簡単な例は、 BFSを使用して、無向グラフの各頂点とエッジを1回だけ印刷することです。2色だけではできません。その理由を理解するために、現在調査している（反復のために）エッジのもう一方の端にある頂点のステータスについて考えてみましょう。もう一方の端の頂点は、（a）すでに処理されている（b）まだ検出されていない（c）すでにキューにあり、処理されるのを待っている可能性があります。（a）の場合、以前に現在のエッジを確認したことがあるので、再度印刷する必要はありません。（b）と（c）については、初めて表示されるので、印刷する必要があります。わかりました、十分です。したがって、フラグを1つだけ使用することにしますvisited。truefalse（b）と（c）の場合、エッジを印刷するタイミングと印刷しないタイミングを決定できます。しかし、結果として、キューにある頂点のvisitedフラグを保持する必要があることを確認しました。つまり、ケース（c）です。falseそのため、キューにプッシュするときにマークを付けることはできません。それに接続されているすべてのエッジを探索した場合にのみ、マークを付けることができます。結果として、反復でケース（c）に直面すると、（キューを明示的に検索しない限り）もう一方の端の頂点がすでにキューにあるかどうかを判断できません。結局、それを再びキューにプッシュして、間違った答えになってしまいます。

于 2018-09-26T23:00:42.490 に答える