BFS和DFS

广度优先搜索（BFS）与深度优先搜索（DFS）的思路,伪代码和代码实现。

一、简介

BFS和DFS是树和图中非常经典的搜索方法，他们分别用了队列和栈来记录节点以遍历整个数据。

二、BFS

BFS 使用队列（Queue）从一个起始节点出发，逐层访问其邻接节点，适合用于最短路径查找等场景。

复杂度分析

（1） 在邻接表
$$O(V+E)$$
原因：先走完一个节点的所有邻接点（遍历时放入队列中），之后从队列中取出头，然后遍历该点的所有邻接点。所以经过的是：所有的点+所有点接触的边

（2）邻接矩阵
$$O(V^2)$$
原因：存储的是一整个矩阵，所以需要遍历这个矩阵中的所有位置。矩阵的坐标是任意2点的情况，所以是节点数的平方

::: info
思考：图结构相比于树结构，会新遇到什么问题？

树是一种无环结构，不需要担心BFS中出现一个节点被多多次访问的情况。图则可能有环，已经访问过得节点可能再次出现在队列中，陷入死循环。解决方法：设置visited标记，记录已经访问过的节点。
:::

伪代码

breadthFirstSearch(v)
{
    Label vertex V as reached.
    Initialize Q to be a queue withi only v in it.
    While(Q is not empty)
    {
        Delete a vertex w from the queue.
        Let u be a vertex(if any) adjacent from w.
        while(u!= NULL)
        {
            if (u has not been labeled)
            {
                Add u to the queue.
                Label u as reached.
            }
            u = next vertex that is adjacent from w.
        }
    }
}

算法实现

实现方式：

• 使用 队列（通常是 collections.deque）

C++版

virtual void bfs(int v, int reach[], int label)
{
    arrayQueue<int> q(10);
    reach[v] = label;
    q.push(v);
    while(!q.empty())
    {
        int w = q.front(); // 从队列中删除一个标记过的点
        q.pop();

        // 标记所有没有到达过的w的邻接点
        vertexIterator<T> *iw = iterator(w);
        int u;
        while((u = iw->next()) != 0)
        {
            // 访问w的一个相邻顶点
            if (reach[u]==0)
            {
                q.push(u);
                reach[u]  = label;
            }
            delete iw;
        }
    }
}

vertexIterator：表示一个模板类型的 顶点迭代器 类。
*iw：声明了一个指针 iw，类型是 vertexIterator。
iterator(w)：调用函数 iterator()，传入参数 w，返回的是一个 vertexIterator 类型的对象指针。

Python版

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)

    while queue:
        node = queue.popleft()
        print(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

# 使用示例
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': [],
    'F': []
}
bfs(graph, 'A')

三、深度优先搜索

与树的前中后遍历相似。DFS 使用回溯的方式，从一个起始节点出发，尽可能深地探索每一条路径，直到走不通再回退。

时间复杂度

（1）邻接表
$$O(V+E)$$
（2）邻接矩阵
$$O(V^2)$$

伪代码

depthFirstSearch(v)
{
    Label vertex v as reached.
    for(each unrearched vertex u adjacent from v){
        depthFirstSearch(u);
    }
}

代码实现

🔹 实现方式：

• 递归实现
• 使用栈实现（模拟递归）

C++

void dfs(int v, int reach[], int label)
{
    graph<T>::reach = reach;
    graph<T>::label = label;
    rDFS(v);
}

void rDFS(int v)
{
    //递归方法
    reach[v] = label;
    vertexIterator<T> *iv = iterator(v);
    int u;
    while((u= iv->next()) != 0)
    {
        if (reach[u] != 0)
        {
            rDFS(u);
        }
    }
    delete iv;
}

Python

def dfs(graph, node, visited):
    if node in visited:
        return
    visited.add(node)
    print(node)  # 访问节点
    for neighbor in graph[node]:
        dfs(graph, neighbor, visited)

# 使用示例
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': [],
    'F': []
}
dfs(graph, 'A', set())

四、对比总结

⚖️ DFS vs BFS 对比总结

特性	DFS（深度优先）	BFS（广度优先）
数据结构	栈（递归或手动）	队列
遍历策略	一路到底、回溯	一层一层遍历
是否找到最短路径	不一定	✅ 是（在无权图中）
易陷入死循环	是（图中需 visited）	是（图中需 visited）
空间复杂度	O(h)，h 为树高	O(w)，w 为最大宽度
应用场景	拓扑排序、连通块标记等	最短路径、层级遍历等