算法 宽度优先搜索（BFS）和深度优先搜索（DFS）

宽度优先搜索（BFS）和深度优先搜索（DFS）是两种常见的图遍历算法，它们在计算机科学中被广泛使用。下面我们来分别介绍一下这两种算法。

宽度优先搜索（BFS）

宽度优先搜索是一种基于队列的搜索算法。它从起始节点开始，逐层地向外扩展搜索，直到找到目标节点或者搜索完整张图。BFS通过维护一个队列来实现搜索过程。每当搜索到一个节点时，将该节点加入到队列的末尾，然后按照先进先出的顺序从队列中取出一个节点，并将它的所有邻居节点加入队列。这样，就可以逐层地扩展搜索，直到找到目标节点。

BFS可以用于解决很多问题，比如最短路径问题、迷宫问题等。由于BFS的搜索过程是逐层扩展的，所以它可以找到最短路径。BFS的时间复杂度为nO(V+E)，其中V是图中的节点数，E是边数。

深度优先搜索（DFS）

深度优先搜索是一种递归的搜索算法。它从起始节点开始，递归地访问每一个节点，直到找到目标节点或者搜索完整张图。DFS通过维护一个栈来实现搜索过程。每当访问一个节点时，将该节点加入栈中，然后按照深度优先的顺序递归访问该节点的所有未访问过的邻居节点。这样，就可以递归地遍历整张图。

DFS可以用于解决很多问题，比如拓扑排序问题、欧拉回路问题等。由于DFS的搜索过程是递归的，所以它可以处理复杂的图结构。DFS的时间复杂度为nO(V+E)，其中V是图中的节点数，E是边数。

总的来说，BFS和DFS都是非常有用的算法，它们在不同的问题中有不同的应用。选择哪一种算法取决于具体的问题。

推荐阅读