搜索与图论复习1

1深度优先遍历DFS  2宽度优先遍历BFS  3树与图的存储  4树与图的深度优先遍历  5树与图的宽度优先遍历  6拓扑排序

1DFS：

#include<bits/stdc++.h>
using namespace std;
const int N=10;
int n;
int path[N];
bool st[N];
void dfs(int u){if(n==u){for(int i=0;i<n;i++)cout<<path[i]<<" ";cout<<endl;return ;}for(int i=1;i<=n;i++){if(!st[i]){//第i个没用过 path[u]=i;st[i]=true;dfs(u+1);st[i]=false;}}
}
int main(){cin>>n;dfs(0);return 0;
}

 acwing843

#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(n==u){for(int i=0;i<n;i++)cout<<g[i]<<endl;cout<<endl;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;
}

 第二种代码

#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++)cout<<g[i]<<endl;cout<<endl;}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,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;
}

2BFS：acwing844

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef pair<int,int>PII;
const int N=110;
int n,m;
int g[N][N];
int d[N][N];
PII q[N*N];
int bfs(){int hh=0,tt=0;q[0]={0,0};memset(d,-1,sizeof d);d[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};}}}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;
}

acwing845八数码

3树和图的存储和遍历：acwing846DFS

#include<iostream>
#include<cstring>
using namespace std;
const int N=100010,M=N*2;
int n,m;
int h[N],e[M],ne[M],idx;
bool st[N];
int ans=N;//最小的最大值 
void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}//以u为根的子树中点的数量
int dfs(int u){st[u]=true;//标记下，已经被搜过了int sum=1,res=0;//当前子树的大小，答案 for(int i=h[u];i!=-1;i=ne[i]){int j=e[i];if(!st[j]){int s=dfs(j);res=max(res,s);//子树最大值sum+=s;}}res=max(res,n-sum);ans=min(ans,res);return sum; 
} 
int main(){cin>>n;memset(h,-1,sizeof h);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;return 0;
}

acwing847BFS

#include<iostream>
#include<cstring>
using namespace std;
const int N=100010;
int n,m;
int h[N],e[N],ne[N],idx;
int q[N],d[N];
void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int bfs(){int hh=0,tt=0;q[0]=1;memset(d,-1,sizeof d);d[1]=0;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拓扑序列---有向图

#include<iostream>
#include<cstring> 
using namespace std;
const int N=100010;
int n,m;
int h[N],e[N],ne[N],idx;
int q[N],d[N];
void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
bool toposort(){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]==0)q[++tt]=j;//为0就做起点入队 }}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(toposort()){for(int i = 0;i < n;i ++)cout<<q[i]<<" ";cout<<endl;}else cout<<"-1"<<endl;return 0;
}