一、DFS

往深里搜，搜到葉子結(jié)點(diǎn)那里，回溯，到可以繼續(xù)到葉子結(jié)點(diǎn)深搜的位置。

1、回溯一定要恢復(fù)現(xiàn)場

2、定義一個(gè)與當(dāng)前遞歸層數(shù)有關(guān)的終止條件（題目要求的東西）

3、每層都用循環(huán)判斷是否存在可以dfs的路

輸出數(shù)字組合

#include<bits/stdc++.h>
//842排列數(shù)字 按照字典序?qū)個(gè)數(shù)
using namespace std;
const int N=1e5+10;
int path[N];//記錄走過的路徑
int st[N];//用來記錄某個(gè)元素是否被用過
int n;
void dfs(int u)
{//先判斷是否已經(jīng)得到一個(gè)答案if(u==n){for(int i=0;i<n;i++)cout<<path[i]<<" ";puts("");return;}for(int i=1;i<=n;i++){if(!st[i])//剪枝的過程找到可以構(gòu)成dfs路徑的方向{st[i]=true;path[u]=i;dfs(u+1);path[i]=0;//恢復(fù)現(xiàn)場st[i]=false;}}
}
int main()
{cin>>n;dfs(0);return 0;
}

全排列的思想解決n皇后問題，用三個(gè)bool數(shù)組描述限制條件，用二維char數(shù)組保存結(jié)果，在恢復(fù)現(xiàn)場的時(shí)候也要恢復(fù)g數(shù)組，因?yàn)楹竺娴钠渌Y(jié)果可能不會將其覆蓋掉。

#include<bits/stdc++.h>
//843 n皇后問題（全排列問題）
using namespace std;
const int N=20;
int path[N];//記錄走過的路徑
char g[N][N];
bool col[N],row[N],dg[N],udg[N];
int n;
void dfs(int u)
{//先判斷是否已經(jīng)得到一個(gè)答案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[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>
//843 n皇后問題（全排列問題）
using namespace std;
const int N=20;
int path[N];//記錄走過的路徑
char g[N][N];
bool col[N],row[N],dg[N],udg[N];
int n;
void dfs(int x,int y,int u)//x為行，y為列
{if(y==n)y=0,x++;if(x==n){if(u==n)//有可能到頭了也沒有找到全部的皇后{for(int i=0; i<n; i++)puts(g[i]);puts("");}return;}//為什么要添加xy兩個(gè)參數(shù)//因?yàn)檫@個(gè)思路不是循環(huán)式地剪枝，是利用遞歸進(jìn)行搜索//處理坐標(biāo)//不放當(dāng)前位置dfs(x,y+1,u);//放當(dāng)前位置if(!row[x]&&!col[y]&&!dg[x+y]&&!udg[n-y+x]){g[x][y]='Q';row[x]=col[y]=dg[x+y]=udg[n-y+x]=true;dfs(x,y+1,u+1);g[x][y]='.';row[x]=col[y]=dg[x+y]=udg[n-y+x]=false;}}
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

一層一層地搜索，如果邊都是1，bfs第一次搜到的點(diǎn)具有最短路性質(zhì)

1、具有最短路性質(zhì)的原因：因?yàn)閎fs每次都向外擴(kuò)展一層，依次找到距離起點(diǎn)為1,2,3的所有點(diǎn)。

#include<bits/stdc++.h>
//844走迷宮//添加路徑
using namespace std;
const int N=110;
typedef pair<int,int>PII;
int g[N][N];//存圖
int d[N][N];//存距離
PII q[N*N];//模擬隊(duì)列
PII pre[N][N];//路徑的前驅(qū)
//由于最短路性質(zhì)，可以直接將當(dāng)前節(jié)點(diǎn)前的一個(gè)結(jié)點(diǎn)作為前驅(qū)
int n,m;void bfs()
{memset(d,-1,sizeof d);//用于判斷是否是第一次訪問到//一個(gè)點(diǎn)可以有多個(gè)路徑到達(dá)，但是第一個(gè)到達(dá)的一定是最短路d[0][0]=0;int hh=0,tt=0;q[0]={0,0};int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};while(hh<=tt)//只要非空{(diào)auto 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&&g[x][y]==0&&d[x][y]==-1){d[x][y]=d[t.first][t.second]+1;q[++tt]={x,y};pre[x][y]=t;}}}int x=n-1,y=m-1;while(x||y){cout<<x<<" "<<y<<endl;x=pre[x][y].first;y=pre[x][y].second;}
}int main()
{cin>>n>>m;for(int i=0; i<n; i++)for(int j=0; j<m; j++)cin>>g[i][j];bfs();cout<<d[n-1][m-1];return 0;
}

三、鄰接表鄰接矩陣存圖

1、鄰接表的存法

2、使用h數(shù)組作為槽，利用e和ne數(shù)組和idx構(gòu)造單鏈表存槽中相應(yīng)結(jié)點(diǎn)有邊相連的節(jié)點(diǎn)、

根據(jù)題意利用從1深搜，每一層用res存最大的子圖的點(diǎn)數(shù),每次計(jì)算出一個(gè)子連通圖添加到sum中。

#include<bits/stdc++.h>
//846 樹重心
using namespace std;
const int N=1e5+10,M=N*2;
typedef pair<int,int>PII;
int h[N],e[M],ne[M],idx;
bool st[N];
//h保存n個(gè)頭結(jié)點(diǎn)
//在用數(shù)組模擬鏈表時(shí)，e保存鏈表結(jié)點(diǎn)值，ne保存邊
//idx讓這一切有序
int ans=N,n;//存結(jié)果
int dfs(int u)//u是結(jié)點(diǎn)的名字不是idx性質(zhì)的
{st[u]=true;//標(biāo)記這個(gè)結(jié)點(diǎn)已經(jīng)被搜索過了//在遍歷當(dāng)前節(jié)點(diǎn)的所有子樹之前int sum=1;//存所有子樹的節(jié)點(diǎn)個(gè)數(shù)int res=0;//記錄各個(gè)連通子圖的節(jié)點(diǎn)個(gè)數(shù)for(int i=h[u];i!=-1;i=ne[i]){int j =e[i];if(st[j]==false)//只要這個(gè)結(jié)點(diǎn)的子樹還沒計(jì)算{int t=dfs(j);res=max(res,t);//存最大連通子圖sum+=t;//所有子樹}}res=max(res,n-sum);ans=min(ans,res);//保存最小的最大連通子圖return sum;}void add(int a,int b)//頭插法
{e[idx]=b;//每個(gè)idx都代表一個(gè)鏈表上的節(jié)點(diǎn)ne[idx]=h[a];h[a]=idx++;
}int main()
{memset(h,-1,sizeof h);//memset(st,false,sizeof st);//所有結(jié)點(diǎn)的單鏈表指向的位置都為空cin>>n;for(int i=0;i<n-1;i++){int a,b;cin>>a>>b;add(a,b),add(b,a);}dfs(1);cout<<ans<<endl;}

3、鄰接表利用bfs計(jì)算最短路

#include<bits/stdc++.h>
//847圖中點(diǎn)的層次
using namespace std;
const int N=1e5+10,M=2*N;
int n,m;
int h[N],e[N],ne[N],idx;
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=0;memset(d,-1,sizeof d);q[0]=1;//1是結(jié)點(diǎn)的名字，入隊(duì)d[1]=0;//到第一個(gè)結(jié)點(diǎn)的距離為0//數(shù)組模擬隊(duì)列的時(shí)候hh永遠(yuǎn)指向隊(duì)列的第一個(gè)元素，tt永遠(yuǎn)指向隊(duì)尾，所以判斷隊(duì)列不為空的判斷條件是hh<=tt。while(hh<=tt){int t=q[hh++];//拿出隊(duì)頭元素for(int i=h[t];i!=-1;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;
}

4、有向無環(huán)圖一定有拓?fù)湫蛄?#xff0c;拓?fù)渑判虻膶?shí)現(xiàn)

#include<bits/stdc++.h>
//848拓?fù)渑判?using namespace std;
const int N=1e5+10,M=2*N;
int n,m;
int h[N],e[N],ne[N],idx;
int d[N],q[N];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++){if(!d[i])q[++tt]=i;}while(hh<=tt){int t=q[hh++];for(int i=h[t];i!=-1;i=ne[i]){int j=e[i];d[j]--;if(!d[j])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;add(a,b);d[b]++;}if(!topsort())puts("-1");else{for(int i=0;i<n;i++)cout<<q[i]<<" ";puts("");}
}