DFS与BFS用于树与图的搜索

        数据结构      空间         性质
DFS        栈         O(h)     不具有最短性
BFS       队列       O(2^h)     最短路问题

DFS

DFS将所有可能的情况都搜索一遍
DFS在回溯时要注意恢复现场

ex1: 排列数字

int n;
// 存储路径，状态
int path[N], st[N]; 
// 每次dfs搜索一个数字
void dfs( int u ) {
    if ( u == n ) {
        for ( int i=0; i<n; i++ ) cout << path[i] << " ";
        cout << endl;
        return;
    }
    for ( int i=1; i<=n; i++ ) {
        // 使用没有用过的数字
        if ( !st[i] ) {
            path[u] = i;
            st[i] = true;
            dfs(u+1);
            // 递归结束后要恢复现场
            // path[u] = 0; path[]每次都被覆盖, 可省略
            st[i] = false;
        }
    }
}

DFS搜索过程需可以进行剪枝，将不满足条件的树的分支去掉
ex2: n皇后

void dfs( int u ) {
    if ( u == n ) {
        for ( int i=0; i<n; i++ ) puts(g[i]);
        cout << endl;
        return;
    }
    for ( int i=0; i < n; i++ ) 
        if ( !col[i] && !dg[u+i] && !udg[n-u+i] ) {
            g[u][i] = 'Q';
            col[i] = dg[ u+i ] = udg[n-u+i] = true;
            dfs(u+1);
            col[i] = dg[ u+i ] = udg[n-u+i] = false;
            g[u][i] = '.';
        }

}

枚举每一个格子需不需要放皇后

int n;
char g[N][N];
bool row[N],col[N],dg[N],udg[N];
void dfs ( int x,int y ,int s ) { // 坐标与皇后个数 
    if ( y == n ) y=0, x++;
    if ( x == n ) {
        if ( s == n ) {
        for ( int i=0; i<n; i++ ) puts(g[i]);
        cout << endl;
        }
         return;
    }
    // 不放皇后
    dfs(x,y+1,s);
    // 放皇后
    if ( !row[x] && !col[y] && !dg[x+y] && !udg[x-y+n])  {
        g[x][y] = 'Q';
        row[x] = col[y] = dg[x+y] = udg[x-y+n] = true;
        dfs( x,y+1,s+1);
         // 恢复现场 
        row[x] = col[y] = dg[x+y] = udg[x-y+n] = false;
        g[x][y] = '.';
    }
}

BFS

当图的边权均为1时使用BFS
框架：

初始状态 -> queue
while( 队列不空 ) {
    // 取出队头
    队头 -> t;
    扩展t
}

int bfs ( ) {
    int hh = 0, tt = 0;
    // 初始化队列
    q[0] = {0,0};
    // 初始化
    memset(d,-1 ,sizeof(d)); 
    d[0][0] = 0;
    // 方向向量,顺序不会造成影响
    int dx[4] = {-1,1,0,0}, dy[4] = {0,0,-1,1}; // 向上，向下，向左，向右

    while ( hh <= tt ) {

        auto t  = q[hh++]; // 取出队头 hh++;

        for ( int i = 0; i < 4; i++ ) {
            int x = t.first + dx[i], y = t.second + dy[i];
            if ( x >=0 && x < n &&  y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1 ) {
                d[x][y] = d[t.first][t.second] + 1;
                q[++tt] = { x , y };  // ++tt;
            }
        }
    }
    return d[n-1][m-1];
}