DFS（深度优先遍历） 与 BFS（广度优先遍历）

发表于 更新于 分类于 ，
本文字数： 533

DFS 与 BFS 的思想

以遍历树为例

DFS

使用了栈思想

思路：

  • 将根节点入栈
  • 检查与栈顶元素相连的元素是否存在未被遍历(标记)过的元素，如果有则将其入栈，如果无则将堆顶元素弹出
  • 重复第二步直到遍历结束

代码实现：

1
2
3
4
5
6
7
8
9
10
int dfs(int u)
{
    st[u] = true; // st[u] 表示点u已经被遍历过

    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j]) dfs(j);
    }
}

BFS

使用了队列的实现方式

思路：

  • 将根节点入队
  • 弹出队头并将与队头节点相连的未遍历过的节点依次入队
  • 重复第二步直到遍历结束(队列为空)

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
queue<int> q;
st[1] = true; // 表示1号点已经被遍历过
q.push(1);

while (q.size())
{
    int t = q.front();
    q.pop();

    for (int i = h[t]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!s[j])
        {
            st[j] = true; // 表示点j已经被遍历过
            q.push(j);
        }
    }
}