一、深度优先搜索
判边界，写递归
//k表示当前个数 void dfs(前k-1个数已经固定，当前需要进行搜索的片段的位置数k(已累计搜素k-1个数)) { 如果k>总数n，即已得到结果，结束return 否则，定义i从1到n循环 如果i没有用过，固定i(有效数)到当前位置并标记已使用，调用dfs(k+1) 调用完dfs(k+1)后，去除固定到当前位置的i， 即取消标记 }
以PTA浙大数据结构习题集 习题2.8 输出全排列 为例
输出前n个数的全排列
#include<iostream> #include<cstdio> using namespace std; const int maxn=100; int n; int vis[maxn]; int ans[maxn]; void Print() { for(int i=1;i<=n;i++) printf("%d",ans[i]); cout<<endl; return ; } void dfs(int x) { if(x>n)//递归结束标志 { Print(); return ; } for(int i=1;i<=n;i++)//遍历搜索 { if(!vis[i])//判断是否被使用过 { vis[i]=1;//标记 ans[x]=i;//记录 dfs(x+1);//进一步搜索 vis[i]=0;//取消标记 } } return ; } int main() { cin>>n; dfs(1); return 0; }
二、广度优先搜索
//首先要建立一个队列用来处理结点 void bfs() { /*将第一节点即开始节点加入队列 进入一个循环 把一步以内能够到达的节点加入队列 对队列元素进行处理，筛选，即从队列中删除这个节点A，然后再把这个结点A能够一步走到的节点键入队列 直到队列空为止 */ }
以牛客竞赛中 例题 走出迷宫 为例
代码如下：
#include<iostream> #include<cstdio> #include<queue> #include<cstring> using namespace std; const int maxn=800; int n,m; char mp[maxn][maxn]; int vis[maxn][maxn]; int nextt[4][2]={{0,1},{0,-1},{1,0},{-1,0}}; struct Node//设置节点 { int x,y;//当前位置下标 int s;//表示步数 int f;//表示路径 }; Node start;//开始节点 void bfs() { queue<Node> q;//声明队列 q.push(start);//将开始节点入队 bool flag=false;//是否已到达目标点的判断标志 while(!q.empty()) { Node tmp=q.front(); q.pop();//节点出队使用 for(int k=0;k<4;k++) { Node nextn;//下一个点，试探用 nextn.x=tmp.x+nextt[k][0]; nextn.y=tmp.y+nextt[k][1];//移动位置 if(nextn.x<1||nextn.x>n||nextn.y<1||nextn.y>m)//判断是否越界 continue; if(mp[nextn.x][nextn.y]=='.'&&vis[nextn.x][nextn.y]==0)//判断该点是符合题目要求 { vis[nextn.x][nextn.y]=1;//标记已经走过 q.push(nextn);//符合条件入队 } if(mp[nextn.x][nextn.y]=='E')//判断是否到达终点 { flag=true; break; } } if(flag) break; } if(flag) cout<<"Yes"<<endl; else cout<<"No"<<endl; } int main() { while(cin>>n>>m) { memset(vis,0,sizeof(vis)); char tt; tt=getchar(); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { scanf("%c",&mp[i][j]); if(mp[i][j]=='S') { start.x=i; start.y=j; } } tt=getchar(); } bfs(); } return 0; }