深度優先遍曆

深度優先搜索演算法

深度優先搜索演算法(DFS)遍曆深度區運動的圖並使用堆疊記下要獲得的下一個頂點，當一個死尾發生時迭代開始搜索。

正如上面給出的例子，DFS演算法從A遍曆到B到C再到D到E，然後到F，最後到G它採用下列規則。

• 規則 1 − 訪問鄰近的未訪問頂點。標記它已訪問。並顯示它，最後將其推入堆疊。

• 規則 2 − 如果沒有相鄰頂點發現，從堆疊中彈出一個頂點。(它會從棧彈出沒有相鄰頂點的所有頂點)

• 規則 3 − 重複第1條和第2條，直到堆疊為空。

void depthFirstSearch(){
   int i;

   //mark first node as visited
   lstVertices[0]->visited = true;

   //display the vertex
   displayVertex(0);

   //push vertex index in stack
   push(0);

   while(!isStackEmpty()){
      //get the unvisited vertex of vertex which is at top of the stack
      int unvisitedVertex = getAdjUnvisitedVertex(peek());

      //no adjacent vertex found
      if(unvisitedVertex == -1){
         pop();
      }else{
         lstVertices[unvisitedVertex]->visited = true;
         displayVertex(unvisitedVertex);
         push(unvisitedVertex);
      }
   }

   //stack is empty, search is complete, reset the visited flag
   for(i = 0;i < vertexCount;i++){
      lstVertices[i]->visited = false;
   }
}