3

I have conflicting information about depth first traversal and could use some help in understanding how to build a program. Given a certain graph, I want to print a sequence of vertices. The user will input a particular node to start the traversal from. I am looking at different examples and I don't understand how the order of the depth-first traversal works. I have the following pseudocode to work with:

public DFS() {
    DFS(v)
    {   num(v) = i ++;
       for all vertices u adjacent to v
       { if num(u) is 0
            attach edge(uv) to edges;
            DFS(u);
        }
    }



depthFirstSearch()
{     for all vertices v
        num(v) = 0;
  edges = null; //vector of all edges
  i=1;
  while there is a vertex v such that num(v) is 0
         DFS(v);
  output edges;
}
4

1 に答える 1

2

これらのスニペットの両方の鍵は、次のアイデアです。

check if item found at (v)
if item not found,
   for all vertices u adjacent to v
     depth_first_search(u)

すべてのノード (v) の子 (u のリスト) で終了条件をすぐにチェックする代わりに、現在のノード v でのみチェックします。終了条件が満たされない場合は、同じ深さ優先検索関数を適用します。 v の最初の子である u1 から開始します。u1 にも子がある可能性があるため、v の残りの子が処理される前に、まったく同じ関数が u1 の子に適用されます。これが深さ優先検索と呼ばれる理由です。これは、検索が最初にパス内の可能な限り低い子のセットを検索してから、戻って残りの子をチェックするためです。

于 2011-04-23T01:53:12.483 に答える