搜索与图论——DFS与BFS

DFS与BFS

由于这个博客是个人笔记性质的，且我接触DFS/BFS太多次了，就贴个代码算了

1. DFS（暴搜，广度优先算法）

• 注意要防止爆栈，DFS空间复杂度高

• 优化剪枝

int dfs(int u) {
    if (...)	return;//找到结果或者无路可走
    
    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);
    }
}

2. BFS（深度优先算法）

queue 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);
        }
    }
}