一、DFS
往深里搜，搜到葉子結點那里，回溯，到可以繼續(xù)到葉子結點深搜的位置。
1、回溯一定要恢復現場
2、定義一個與當前遞歸層數有關的終止條件（題目要求的東西）
3、每層都用循環(huán)判斷是否存在可以dfs的路
輸出數字組合
#include<bits/stdc++.h>
//842排列數字 按照字典序將n個數
using namespace std;
const int N=1e5+10;
int path[N];//記錄走過的路徑
int st[N];//用來記錄某個元素是否被用過
int n;
void dfs(int u)
{
//先判斷是否已經得到一個答案
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])//剪枝的過程找到可以構成dfs路徑的方向
{
st[i]=true;
path[u]=i;
dfs(u+1);
path[i]=0;//恢復現場
st[i]=false;
}
}
}
int main()
{
cin>>n;
dfs(0);
return 0;
}
全排列的思想解決n皇后問題，用三個bool數組描述限制條件，用二維char數組保存結果，在恢復現場的時候也要恢復g數組，因為后面的其他結果可能不會將其覆蓋掉。
#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)
{
//先判斷是否已經得到一個答案
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兩個參數
//因為這個思路不是循環(huán)式地剪枝，是利用遞歸進行搜索
//處理坐標
//不放當前位置
dfs(x,y+1,u);
//放當前位置
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第一次搜到的點具有最短路性質
1、具有最短路性質的原因：因為bfs每次都向外擴展一層，依次找到距離起點為1,2,3的所有點。
#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];//模擬隊列
PII pre[N][N];//路徑的前驅
//由于最短路性質，可以直接將當前節(jié)點前的一個結點作為前驅
int n,m;
void bfs()
{
memset(d,-1,sizeof 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)//只要非空
{
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數組作為槽，利用e和ne數組和idx構造單鏈表存槽中相應結點有邊相連的節(jié)點、
根據題意利用從1深搜，每一層用res存最大的子圖的點數,每次計算出一個子連通圖添加到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個頭結點
//在用數組模擬鏈表時，e保存鏈表結點值，ne保存邊
//idx讓這一切有序
int ans=N,n;//存結果
int dfs(int u)//u是結點的名字不是idx性質的
{
st[u]=true;//標記這個結點已經被搜索過了
//在遍歷當前節(jié)點的所有子樹之前
int sum=1;//存所有子樹的節(jié)點個數
int res=0;//記錄各個連通子圖的節(jié)點個數
for(int i=h[u];i!=-1;i=ne[i])
{
int j =e[i];
if(st[j]==false)//只要這個結點的子樹還沒計算
{
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;//每個idx都代表一個鏈表上的節(jié)點
ne[idx]=h[a];
h[a]=idx++;
}
int main()
{
memset(h,-1,sizeof h);
//memset(st,false,sizeof st);
//所有結點的單鏈表指向的位置都為空
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計算最短路文章來源：http://www.zghlxwxcb.cn/news/detail-827329.html
#include<bits/stdc++.h>
//847圖中點的層次
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是結點的名字，入隊
d[1]=0;//到第一個結點的距離為0
//數組模擬隊列的時候hh永遠指向隊列的第一個元素，tt永遠指向隊尾，所以判斷隊列不為空的判斷條件是hh<=tt。
while(hh<=tt)
{
int t=q[hh++];//拿出隊頭元素
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)圖一定有拓撲序列，拓撲排序的實現文章來源地址http://www.zghlxwxcb.cn/news/detail-827329.html
#include<bits/stdc++.h>
//848拓撲排序
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("");
}
}
到了這里，關于搜索與圖論（一）（深搜，廣搜，樹與圖的存儲遍歷，拓撲排序）的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！
