搜索基础

DFS与BFS

深度优先搜索：一棵树从一个枝向下搜索，搜到头之后回溯，继续搜下一个枝
宽度优先搜索（Breath First Search 而不是 Brain Fuck Scheduler）（后者已经停止维护了）：一层一层搜到底部

DFS

注意回溯需要“恢复现场”

#include <cstdio>

const int N = 10;

int n; // 层数
int path[N]; // 存储状态
bool state[N]; // 存储各个枝是否被使用

void dfs(int a) {
    if (a == n) { // 到达最底层
        for (int i = 0; i < n; i ++) {
            printf("%5d",path[i]);
        }
        putchar('\n');
        return ;
    } 
    
    for (int i = 1; i <= n; i ++) {
        if (!state[i]) { // i没有被使用
            path[a] = i;
            state[i] = 1;
            dfs(a+1); // 搜索下一层
            state[i] = 0; // dfs结束之后，开始回溯，恢复现场
        }
    }
}

int main() { 
    scanf("%d",&n);

    dfs(0);

    return 0;
}

复制

本文采用 GNU 自由文档许可证许可协议，转载请注明出处。