深度优先搜索与广度优先搜索：原理与实践

深度优先搜索（DFS）和广度优先搜索（BFS）是两种常见的图遍历算法，它们在处理图和树等数据结构时非常有用。这两种算法的主要区别在于它们搜索节点的顺序不同。

一、深度优先搜索（DFS）

深度优先搜索是一种递归算法，它沿着树的深度遍历树的节点，尽可能深地搜索树的分支。当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。

在Python中，我们可以使用递归实现深度优先搜索。以下是一个使用DFS解决小哈问题的示例代码：

def dfs(graph, start):
    visited = set()  # 记录已访问的节点
    stack = [start]  # 使用栈实现递归
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            stack.extend(graph[vertex] - visited)  # 将未访问的邻居节点加入栈中
    return visited

在这个例子中，graph是一个字典，表示图的邻接表表示。start是开始遍历的节点。函数返回一个集合，包含了从起始节点开始可以访问的所有节点。

二、广度优先搜索（BFS）

广度优先搜索是一种按照层次遍历图的算法。它从根（通常是源节点）开始并探索最靠近根的节点。BFS 使用队列数据结构来保存信息。首先将根节点放入队列中，然后进入循环，在循环中，处理队列的头部元素，将该元素的所有未访问过的相邻节点放入队列的尾部，然后继续处理队列中的下一个元素，直到队列为空。

在Python中，我们可以使用队列实现广度优先搜索。以下是一个使用BFS解决小哈问题的示例代码：

from collections import deque
def bfs(graph, start):
    visited = set()  # 记录已访问的节点
    queue = deque([start])  # 使用队列实现广度优先搜索
    while queue:
        vertex = queue.popleft()  # 从队列头部取出一个节点
        if vertex not in visited:
            visited.add(vertex)  # 标记该节点为已访问
            queue.extend(graph[vertex] - visited)  # 将未访问的邻居节点加入队列中
    return visited

在这个例子中，graph是一个字典，表示图的邻接表表示。start是开始遍历的节点。函数返回一个集合，包含了从起始节点开始可以访问的所有节点。

在实际应用中，我们可以根据具体问题选择使用深度优先搜索或广度优先搜索。例如，在寻找最短路径问题中，我们通常使用广度优先搜索；在寻找图的连通分量或生成树等问题中，我们通常使用深度优先搜索。