深度優先遍歷

深度優先搜尋演算法

深度優先搜尋演算法(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;
   }        
}