9.13

[Ryanlyt]

DFS 深度优先搜索（又称暴力搜索，dfs没有一个通用的模板，最重要的是把顺序想清楚（同一题目搜索的顺序可能有很多种））

数据结构：stack（不需要真的把栈写出来） 空间O(h) 不具有最短性 （用树的形式搜索） DFS重要概念：回溯（记得恢复现场）、剪枝（提前判断，没有必要继续往下搜了，直接回溯）
（凡是求最短、最少之类的用BFS，思路比较奇怪的或者对空间要求比较高的用DFS）

全排列问题

n-皇后问题
以全排列的搜索顺序(按行枚举)
#include <bits/stdc++.h>

using namespace std;

const int N = 20;

int n;
char g[N][N];
bool col[N], dg[N], udg[N];

void dfs(int u){
    if(u == n){
        for(int i = 0; i < n; i++) puts(g[i]);
        puts("");
        return;
    }

    for(int i = 0; i< n; i++){
        if(!col[i] && !dg[u + i] && !udg[n - u + i]){    //u+i，n-u+i怎么来的？小技巧：用截距的思想来看，y-x，y+x，为了非负加一个n
            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 main(){
    cin >> n;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            g[i][j] = '.';
        }
    }

    dfs(0);

    return 0;
}

n-皇后问题
以更原始的搜索顺序(一个一个枚举)
#include <bits/stdc++.h>

using namespace std;

const int N = 20;

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]);
            puts("");
        }
        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 + 1, 0, s + 1);
        // dfs(x, y + 1, s + 1); 上下两种都可以
        row[x] = col[y] = dg[x + y] = udg[x - y + n] = false;
        g[x][y] = '.';
    }
}

int main(){
    cin >> n;
    for(int i = 0 ; i < n; i++){
        for(int j = 0; j < n; j ++){
            g[i][j] =  '.';
        }
    }

    dfs(0, 0, 0);

    return 0;
}

[Ryanlyt]

BFS 广度优先搜索（有一个常用的模板）

数据结构：queue 空间O(2^h) 最短路（最短路问题是包含dp(动态规划)问题的，dp问题实际上是一种特殊的最短路问题，dp问题是没有环的最短路问题） 边权都是1是才能用BFS求最短路，否则要用专门的最短路算法

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

[Ryanlyt]

树和图的存储

树是一种特殊的图（无环连通图），无向图是一种特殊的有向图 所以只需要考虑有向图如何存储： 邻接矩阵（不能存储重边，用得比较少，占空间太大，适合存储稠密图） g[a][b] 存储边a->b 邻接表（用的最多，用单链表实现，和拉链法相似）

// 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点
int h[N], e[N], ne[N], idx;

// 添加一条边a->b
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

// 初始化
idx = 0;
memset(h, -1, sizeof h);

[Ryanlyt]

树和图的深度优先遍历

只需要考虑有向图是怎么遍历的

int dfs(int u)
{
    st[u] = true; // st[u] 表示点u已经被遍历过

    for (int i = h[u]; i != -1; i = ne[i])    //要先memset(h, -1, sizeof h)
    {
        int j = e[i];
        if (!st[j]) dfs(j);
    }
}

[Ryanlyt]

树和图的广度优先遍历

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

[Ryanlyt]

拓扑排序