1

ここでDFS擬似コードを見ています

dfs(node start) {
 stack s;
 s.push(start);
 while (s.empty() == false) {
  top = s.top();
  s.pop();
  mark top as visited;

  check for termination condition

  add all of top's unvisited neighbors to the stack.
  mark top as not visited;
 }
}

dfs(node current) {
 mark current as visited;
 visit all of current's unvisited neighbors by calling dfs(neighbor)
 mark current as not visited;
}

作成者が、すべての隣接する頂点を訪問した後、頂点を訪問されていないものとしてマークするのはなぜですか？それはここで必要なステップですか。頂点を検索しているだけなので、頂点を未訪問としてマークせずに機能するべきではありませんか？

ここでの別のリンクは、頂点を訪問済みとして設定した後、実際には頂点を未訪問としてマークしません。

4

1 に答える 1

4

頂点自体ではなく頂点へのパスを探している場合は、頂点を未訪問としてマークする必要があります。

トラバース後に頂点を未訪問としてマークせず、一部の検索でグラフの一部をトラバースし、問題の頂点へのパスを見つけたとします。ある時点で、検索は探索するためのエッジを使い果たし、そのステップを以前のポイントまでさかのぼり、そこから続行します。

最初に見つかったパス上にある頂点を通過する、検索対象の頂点への別のパスがある場合、アルゴリズムは、共通の頂点がすでにアクセスされていると見なすため、2番目のパスを見つけません。

一方、1つのパスだけを探している場合（または頂点の存在だけ、つまりパスがまったくない場合）は、「途中で」訪問されていないノードのマーク付けをスキップできます。

于 2012-12-12T13:26:45.297 に答える