6

アルゴリズム設計マニュアルでは、BFSとDFSについて詳しく説明しています。本のdfsのコードには、エッジの二重処理を回避するかどうかを決定するときに問題があります。エラッタを見つけてコードにエラッタを適用しましたが、それでも洗練されたコードには二重処理エッジのチェックに問題があると思います。

洗練されたコードを次のように貼り付けます。

dfs(graph *g, int v) {
       edgenode *p;
       int y;
       if (finished) return;
       discovered[v] = TRUE;
       time = time + 1;
       entry_time[v] = time;
       process_vertex_early(v);
       p = g->edges[v];
       while (p != NULL) {
             /* temporary pointer */
             /* successor vertex */
             /* allow for search termination */
             y = p->y;
             if (discovered[y] == FALSE) {
                   parent[y] = v;
                   process_edge(v,y);
                   dfs(g,y);
             }
             else if (**(!processed[y] && parent[v] != y)** || (g->directed))
                   process_edge(v,y);
             if (finished) return;
             p = p->next;
       }
       process_vertex_late(v);
       time = time + 1;
       exit_time[v] = time;
       processed[v] = TRUE;
}

問題があると思う場所は****でマークされています。

したがって、疑わしい場所は条件の1つです。無向グラフであると仮定して、の条件を無視することができます(g->directed)。

さて、最初に焦点を当てましょうparent[v] != y。parent[v] == yもちろん、頂点yを処理するときにy-> vがすでに一度処理されているため、エッジv->yを再度処理する必要がない場合。

そして、もしそうならparent[v] != y、私の質問は!processed[y] &&必要かどうかです。

したがって、yがvの親ではなく、processed[y] == falseyが見つかった（そうでない場合は実行がelse if一部に到達できない）が処理されていない場合、yはvの祖母以上である必要があります。これはバックエッジですが、問題は、まだ処理されていないので処理できます。

さて、もしもprocessed[y] == true？この「if」は決して起こらず、この条件は決して真ではないと思います。

なんで？processed[y]さて、本当であると仮定しましょう。これは、yを含むすべてのパスが処理され、それらのパスのすべての頂点も処理されたことを意味します。それで、これが事実である場合、「まだ処理が完了していない」頂点vはどのようにyに近づくことができますか？

dfsでは、処理された頂点に頂点が近づくことはないと思いますが、正しいですか？

したがって、処理された頂点を肉付けしない場合は、!processed[y]常に真であるため、削除するだけで済みます。

4

1 に答える 1

6

いいえ、processed[y] == true真になる可能性があります。

次のグラフを見て、次の[実行可能な]DFSトラバーサルを想定します。

v0,v1,v2

グラフの例

v0dfs(v1)を開始し、処理後に再帰的に呼び出します(v0,v1)。ここで、をv1処理(v1,v2)して再帰的に呼び出しdfs(v2)ます。v2がv0検出されてelse ifステートメントに移動し、(v0,v2)処理されていないことを確認し、parent[v2] != v0[v2を介して検出されたv1]を確認します。

さて、再帰から戻るv0と戻ってきて、次の「息子」をチェックすると-ですv2。v2はすでに検出されているので、に移動しelse if、v2の親ではないv0ので、!processed[y]パーツがなければ、(v0,v2)2回処理することになります。

それが発生するのを防ぐ唯一のことは、processed[y] == true

于 2012-04-05T17:50:29.143 に答える