DFS与BFS模板

(1) 深度优先遍历

深度优先遍历，就是在每个点x上面对多条分支时，任意选一条边走下去，执行递归，直至回溯到点x后，再考虑走向其他的边。

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);
    }
}
1
2
3
4
5
6
7
8
9
10

(2) 宽度优先遍历

树与图的广度（宽度）优先搜索需要使用一个队列来实现，起初，队列中仅包含一个起点。在广度优先遍历的过程中，我们不断从对头取出一个节点x，对于x需要面对的多条分支，把沿着每条分支到达的下一个节点（如果尚未访问过）插入队尾，重复执行上述过程直到队列为空。

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 (!st[j])
        {
            st[j] = true; // 表示点j已经被遍历过
            q.push(j);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19