总结:搜索这一块dfs思路很好懂，但是有时从题目中抽象出来很难，bfs相对简单。

        空间        时间        数据结构
DFS ：  O(n)      O(n + m)      stack          不具有最短性
BFS ：  O(2^h)    O(n + m)      queue          具有最短性

---

DFS

>排列数字

每层选一个未选过的数字，选n层后输出方案。

回溯时：确定没有一条路能走时才会回溯

#include<iostream>
using namespace std;


const int N = 10;
int path[N];
bool st[N];
int n;
void dfs(int u)
{
    if(u == n)
    {
        for(int i = 0;i < n;i++)
        {
            printf("%d ",path[i]);
        }
        puts("");
        return ;
    }
    
    for(int i = 1;i <= n;i++)
    {
        if(!st[i])
        {
            path[u] = i;
            st[i] = true;
            dfs(u+1);
            st[i] = false;
        }
    }
}

int main()
{
    cin>>n;
    dfs(0);
    return 0;
}

全排列stl--next_permutation

例:输出1到4的全排列

#include <iostream>
#include<algorithm>
using namespace std;
 
int main(int argc, char** argv) {
	int a[4]={1,2,3,4};
	sort(a,a+4);
	do{
		for(int i=0;i<4;i++)
		    cout<<a[i]<<" ";
		cout<<endl;
	}while(next_permutation(a,a+4));
	return 0;
}

---

>n皇后问题

法一:每一层选一个，其条件是正反对角线和当前列不能有元素(剪枝） 法二：从(0,0)开始选，每个点选或不选，同样剪枝。

恢复状态:上个状态什么样，就得恢复成什么样
法一

#include<iostream>
using namespace std;

const int N = 15;

int n;
char g[N][N];
bool col[N],dg[2 * N],udg[2 * 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])
        {
            g[u][i] = 'Q';
            col[i] = dg[i+u] = udg[n - u + i] = true;
            dfs(u+1);
            col[i] = dg[i+u] = 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;
}

法二

#include <iostream>
using namespace std;
const int N = 20;

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

// s表示已经放上去的皇后个数
void dfs(int x, int y, int s)
{
    // 处理超出边界的情况
    if (y == n) y = 0, x ++ ;

    if (x == n) { // x==n说明已经枚举完n^2个位置了
        if (s == n) { // s==n说明成功放上去了n个皇后
            for (int i = 0; i < n; i ++ ) puts(g[i]);
            puts("");
        }
        return;
    }

    // 分支1：放皇后
    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] = '.';
    }
    //分支2：不放皇后
    dfs(x,y+1,s);
}    


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

---

BFS

走迷宫

从队头开始扩展相邻的状态，每层更新一次距离，得出答案。

#include<iostream>
#include<cstring>
using namespace std;

typedef pair<int,int> PII;
const int N = 110;
int n,m;
int g[N][N],d[N][N];
PII q[N * N];

int bfs()
{
    memset(d,-1,sizeof d);
    int hh=0,tt = -1;
    d[0][0] = 0;
    q[++tt] = {0,0};
    
    int dx[] = {-1,1,0,0},dy[] = {0,0,-1,1};
    
    while(hh <= tt)
    {
        PII t = q[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 && d[x][y] == -1 && g[x][y] == 0)
            {
                d[x][y] = d[t.first][t.second] + 1;
                q[++tt] = {x,y};
            }
        }
    }
    return d[n-1][m-1];
    
}

int main()
{
    cin>>n>>m;
    for(int i = 0;i < n ;i++)
     for(int j = 0;j < m;j++)
      cin>>g[i][j];
      
    cout<<bfs()<<endl;
    return 0;
}

\(边权为1时，bfs处理最短路。\)

树与图的DFS

>树的重心

遍历每个点，找出具有最大结点数的子树s,s的结点数和n-总结点数作比较，遍历每个点时都能找到其比较后的最大值，最后找到这些最小的最大值。

#include<iostream>
#include<cstring>
using namespace std;

const int N = 1e5 + 10;

int e[N * 2],h[N],ne[N * 2],idx;
int n;

int res;
int ans = N;
bool st[N];
void add(int a,int b)//头插
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
    
}

int dfs(int u)//返回子树的结点数
{ 
    st[u] = true;
    
    int size = 0,sum = 0;//结点总数
    for(int i = h[u] ; ~i;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);
    for(int i = 0; i < n;i++)
    {
        int a,b;
        cin>>a>>b;
        add(a,b),add(b,a);
    }
    dfs(1);
    cout<<ans<<endl;
    return 0;
}

---

树与图的BFS

>图中点的层次

从1号点开始不断扩展,每次扩展到的点距离加1,直到n点被扩展到。

#include<iostream>
#include<cstring>

using namespace std;

const int N = 1e5 + 10;
int h[N],ne[N * 2],e[N * 2],idx;

int n,m;
int d[N],q[N];
void add(int a,int b)
{
    e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}

int bfs()
{
    int hh = 0,tt = -1;
    memset(d,-1,sizeof d);
    d[1] = 0;
    q[++tt] = 1;
    
    while(hh <= tt)
    {
        int t = q[hh++];
        for(int i = h[t];~i;i = ne[i])
        {
            int j = e[i];
            if(d[j] == -1)//未被遍历过
            {
                 d[j] = d[t] + 1;
                 q[++tt] = j;
            }
        }
    }
    return d[n];
}
int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i = 0;i < m;i++)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
    }
    
    cout<<bfs()<<endl;
    return 0;
}

---

>有向图的拓扑序列

有向无环图一定具有拓扑序，入度为0的点作起点。

#include<iostream>
#include<cstring>

using namespace std;

const int N = 1e5 + 10,M = 2e5 + 10;
int n,m;
int d[N],q[N];

int e[M],ne[M],h[N],idx;

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

bool Topsort()
{
    int hh = 0,tt = -1;
    for(int i = 1;i <=n;i++)//所有入度为0的点入队
     if(d[i] == 0)
         q[++tt] = i;
     
     
    while(hh <= tt)
    {
        int t = q[hh++];
        for(int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            d[j]--;
            if(d[j] == 0) q[++tt] = j;
        }
    }
    
    return tt == n - 1;
}


int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i = 0;i < m;i++)
    {
        int  a,b;
        cin>>a>>b;
        d[b]++;
        add(a,b);
    }
    
    if(Topsort())
    {
        for(int i = 0;i < n;i++) cout<<q[i]<<' ';
    }else {
        cout<<"-1"<<endl;
    }
    
    return 0;
}