深度優先遍歷

深度優先搜索算法

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

Depth

正如上面給出的例子，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;
}
}

數據結構和算法教程

深度優先搜索算法