Data Structures Algorithms 简明教程
Depth First Search (DFS) Algorithm
Depth First Search (DFS) Algorithm
深度优先搜索（DFS）算法是一种递归算法，用于搜索图或树数据结构的所有顶点。此算法以深入运动遍历图，并使用堆栈记住要获取下一个顶点以开始搜索，当在任何迭代中发生死锁时。
Depth First Search (DFS) algorithm is a recursive algorithm for searching all the vertices of a graph or tree data structure. This algorithm traverses a graph in a depthward motion and uses a stack to remember to get the next vertex to start a search, when a dead end occurs in any iteration.
正如上面给出的示例中，DFS 算法首先从 S 到 A 到 D 到 G 到 E 到 B，然后到 F，最后到 C。它采用以下规则。
As in the example given above, DFS algorithm traverses from S to A to D to G to E to B first, then to F and lastly to C. It employs the following rules.
-
Rule 1 − Visit the adjacent unvisited vertex. Mark it as visited. Display it. Push it in a stack.
-
Rule 2 − If no adjacent vertex is found, pop up a vertex from the stack. (It will pop up all the vertices from the stack, which do not have adjacent vertices.)
-
Rule 3 − Repeat Rule 1 and Rule 2 until the stack is empty.
由于 C 没有任何未访问的邻接节点，因此我们将继续弹出堆栈，直到找到具有未访问邻接节点的节点。在这种情况下，没有，并且我们一直弹出，直到堆栈为空。
As C does not have any unvisited adjacent node so we keep popping the stack until we find a node that has an unvisited adjacent node. In this case, there’s none and we keep popping until the stack is empty.
Example
下面是深度优先搜索 (DFS) 算法在各种编程语言中的实现 −
Following are the implementations of Depth First Search (DFS) Algorithm in various programming languages −
单击检查 C 实现 Depth First Search (BFS) Algorithm
Click to check C implementation of Depth First Search (BFS) Algorithm