(摘录 @Chase )
1.DFS：递归结束条件的选择+状态标记+递归后的恢复
2.BFS：模拟队列 q[N], d[N] 使用d数组标记状态 当边权都为一时
3.搜索：解空间的搜索往往需要dfs+剪枝，bfs用来找最短路
4.树和图的存储：邻接表 h[N], e[N], ne[N], idx
5.树和图的遍历：遍历不用像搜索解空间一样递归后恢复，只用遍历一次即可

深度优先搜索 与 广度优先搜索

    数据结构    空间复杂度  时间复杂度

DFS stack O(n) 不具有最短性
BFS queue O(2的n次方) “最短路” 最短。。

n 皇后问题

//深搜
#include<iostream>

using namespace std;


const int N=20;
int n;
int col[N],dg[N],udg[N];
char a[N][N];


void dfs(int u){
    if(u==n){
        for(int i=0;i<n;i++)puts(a[i]);
        puts("");
        return ;
    }
    for(int i=0;i<n;i++){
        //u是y，i是x
        if(!col[i] && !dg[i+u] && !udg[n-u+i]){
            a[u][i]='Q';
            col[i]=true,dg[i+u]=true,udg[n-u+i]=true;
            dfs(u+1);
            a[u][i]='.';
            col[i]=false, dg[i+u]=false,udg[n-u+i]=false;
        }
    }
}
int main(){
    cin>>n;

    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            a[i][j]='.';

    dfs(0);        
    return 0;        
}

回溯与剪枝

宽搜

dsa

图的存储与遍历

题： 树的重心

//邻接表方式
#include<iostream>
#include<cstring>

using namespace std;
const int N=1e5+9;
bool st[N]; //标记是否遍历过
int h[N],e[N*2],ne[N*2],idx;
int n;
int ans=N;///////////

void add(int a,int b){//头插法
    e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}

int dfs(int u){
    st[u]=1;

    int sum=0,size=0;

    for(int i=h[u];i!=-1;i=ne[i]){
        int j=e[i];
        if(st[j])continue;
        int s=dfs(j);
        size=max(size,s);
        sum+=s;
    }
    size=max(size,n-sum-1);/////
    ans=min(ans,size);
    return sum+1;////////
}
int main(){
    cin>>n;
    memset(h,-1,sizeof(h));///////////////头节点初始为-1
    for(int i=0;i<n;i++){
        int a,b;
        cin>>a>>b;
        add(a,b);add(b,a);
    }
    dfs(1);
    cout<<ans;
}