深度优先搜索（DFS）、宽度优先搜索（BFS）和深度优先遍历、宽度优先遍历：基础与对比

在计算机科学中，图和树的遍历算法是非常重要的。其中，深度优先搜索（DFS）和宽度优先搜索（BFS）是两种常见的遍历方法。每种方法都有其独特的性质和应用场景。
一、深度优先搜索（DFS）
深度优先搜索是一种用于遍历或搜索树或图的算法。这个算法会尽可能深地搜索树的分支。当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。
示例代码（Python）：

from collections import defaultdict, deque
def dfs(graph, start):
    visited = set()
    stack = deque([start])
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            stack.extend(graph[vertex] - visited)
    return visited

二、宽度优先搜索（BFS）
宽度优先搜索是另一种图遍历算法，它从根节点开始，探索最左边的分支，然后是下一层级的节点，以此类推，直到达到目标节点。BFS 使用队列数据结构来保存遍历节点的顺序。
示例代码（Python）：

def bfs(graph, root):
    visited = set()
    queue = deque([root])
    while queue:
        vertex = queue.popleft()
        if vertex not in visited:
            visited.add(vertex)
            queue.extend(graph[vertex] - visited)
    return visited

三、深度优先遍历（DFS遍历）
深度优先遍历分为前序、中序和后序遍历三种方式。前序遍历的顺序是：根节点 -> 左子树 -> 右子树。中序遍历的顺序是：左子树 -> 根节点 -> 右子树。后序遍历的顺序是：左子树 -> 右子树 -> 根节点。
四、宽度优先遍历（BFS遍历）
宽度优先遍历也分为三种方式，即层次遍历、宽幅遍历和宽线遍历。层次遍历按照层级顺序进行遍历，从根节点开始，逐层向下进行遍历。宽幅遍历则是在同一层级内按照一定的顺序进行遍历，例如从左到右或从上到下。而宽线遍历则是根据一定的规则，在树或图中按照一定的宽度进行遍历。
五、比较与选择
深度优先搜索和宽度优先搜索都是常用的图和树的遍历算法，它们各有优缺点。DFS可以更深入地探索图的细节，但对于大型图来说可能会陷入死循环。BFS则能够更快地访问更多的节点，但可能会忽略一些较深的节点。在实际应用中，我们可以根据具体需求选择合适的算法。例如，在寻找最短路径或广度优先搜索等场景下，BFS更为适用；而在需要挖掘图的深层次结构或依赖关系等场景下，DFS更为适合。