一、DFS
? ? ? ? 主要思想：DFS是一种深度优先图遍历算法，当遍历的当前结点还存在子结点时，就去遍历它的子结点，直到没有子结点，即遍历到叶子结点时，再返回上一层寻找其他没有遍历过的子结点，若存在则进入该子结点对应的分支，不断向下寻找，若不存在再往上一层走，直到回到根结点为止。因此，DFS可以看做“从左往右”地遍历一个图或树，主要借助一个存储当前结点是否遍历过的bool数组st[]实现。在实际问题中，可以在遍历前对约束函数进行判断，如果满足再往下遍历，如果不满足则直接返回上一层，进行“剪枝”，减少不必要的遍历，缩短搜索时间。
? ? ? ? 例题1 完全序列：给定一个数n，输出所有从1到n的n个数不重复的序列。
#include<iostream>
const int N=10;
int path[N],n;//path数组存储遍历结果
bool st[N];//st数组存储第i个数是否已经用过
void dfs(int u){
if(u==n){//遍历到第n个数，即遍历到叶子结点，有一种答案
for(int i=0;i<n;i++) printf("%d ",path[i]);
printf("\n");
return;
}
for(int i=1;i<=n;i++){//数字从1开始
if(!st[i]){//第i个数没有被用过
path[u]=i;
st[i]=true;
dfs(u+1);
st[i]=false;//还原现场，为下一种答案的遍历做准备
}
}
}
int main(){
scanf("%d",&n);
dfs(0);//从根节点开始查找
return 0;
}
? ? ? ? 例题2 八皇后问题：在一个n*n的棋盘上放置n个皇后，保证每两个皇后彼此之间不在同一行、同一列、同一对角线，输出所有可能的答案。
#include<iostream>
const int N=20;//对角线有2n个
char g[N][N];//存储棋盘结果
int n;
bool row[N],col[N],dg[N],udg[N];//依次存储行、列、左对角线、右对角线是否已有皇后
void dfs1(int u){//第一种遍历方法，按行进行dfs
if(u==n){//最后一行也找到了满足的位置，进行答案输出
for(int i=0;i<n;i++) puts(g[i]);
printf("\n");
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;
dfs1(u+1);
col[i]=dg[u+i]=udg[n-u+i]=false;//还原现场
g[u][i]='.';
}
}
}
void dfs2(int x,int y,int s){//第二种遍历方法，按棋盘格进行dfs
if(y==n){//已经走到最后一列
y=0;//列数从0开始
x++;//进入下一行
}
if(x==n){//走到最后一行
if(s==n){//找到了满足个数的位置
for(int i=0;i<n;i++) puts(g[i]);
printf("\n");
}
return;//没有足够个数的位置也要返回才能重新找，return必须在if外面
}
dfs2(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;
dfs2(x,y+1,s+1);
row[x]=col[y]=dg[x+y]=udg[x-y+n]=false;//还原现场
g[x][y]='.';
}
}
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++) g[i][j]='.';
}
dfs2(0,0,0);
return 0;
}
二、BFS
? ? ? ? 主要思想：BFS是一种广度优先图遍历算法。当前结点还有其他未遍历到的邻接结点时，遍历该邻接结点，直到没有邻接结点再遍历子结点，子结点的邻接结点都遍历完以后，回过头找父结点的邻接结点中未遍历的子结点，直到“一层”结点都遍历完，再去下一层。因此，BFS可以看做“从上到下”地遍历一个图或树，主要借助队列实现，一个起始结点的边都遍历完后就从队头弹出，作为边的终点被遍历到的结点都作为邻接点从队尾进入，等待遍历。在实际应用中，如果边的权重为1，或者通过在两点之间插入n个结点模拟边的权重n，BFS也可以解决最短路径问题。
? ? ? ? 例题 迷宫：给出一个n*m的矩阵模拟迷宫，“0”代表通路，“1”代表墙，找出从迷宫左上角到迷宫右下角的最短路径。
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=10;
typedef pair<int,int> PII;//(x,y)坐标
int g[N][N];//存储迷宫
int d[N][N];//存储路径长度
PII q[N*N];//bfs遍历中用到的队列
int hh,tt,n,m;
int dfs(){
hh=tt=0;
q[0]={0,0};//从左上角开始遍历，左上角坐标入队列
memset(d,-1,sizeof(d));//路径长度初始化
d[0][0]=0;
int dx[4]={0,0,-1,1};//一个点的上下左右
int dy[4]={-1,1,0,0};
while(hh<=tt){
auto t=q[hh++];//从队头弹出元素进行边的遍历
for(int i=0;i<4;i++){//遍历上下左右四个相邻点
int x=t.first+dx[i];
int 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;//路径长度在原来的基础上+1
q[++tt]={x,y};//作为边的终点入队列等待遍历
}
}
}
return d[n-1][m-1];//返回右下角坐标对应的路径长度
}
int main(){
scanf("%d %d",&n,&m);
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>g[i][j];
}
}
cout<<dfs()<<endl;
return 0;
}
三、图的存储
? ? ? ? 主要思想：图的存储主要有两种方法，一种是用二维数组存储邻接矩阵，这种方法在稀疏情况下浪费内存，另一种是邻接表，类似与构建哈希表的“拉链法”，边的起点作为一个链表的表头，边的终点作为链表中的元素，这样定义n个链表，就可以存储n个结点构成的图。无向图则在插入边时add(a,b),add(b,a)插入两遍。
????????例题 拓扑序列：给出n个结点，m条边构建的图，判断该图是否有环，如果没有则输出拓扑序列，如果有则输出-1。
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1010,M=2*N;
int h[N],e[M],ne[M],idx;//数组模拟链表
bool st[M];
int q[N],d[N];//q为bfs遍历所需队列，d为每个结点的入度
int n,m;
void add(int a,int b){//添加边即为在起点的链表上插入终点
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
//图的dfs遍历方法，本题中用不到，仅为补充
void dfs(int u){
st[u]=true;
for(int i=h[u];i!=-1;i=ne[i]){
int j=e[i];
if(!st[j]) dfs(j);
}
}
//在bfs遍历的基础上添加入度判断
bool topsort(){
int hh=0,tt=-1;
for(int i=1;i<=n;i++){//找到入度为0的点加入队列
if(!d[i]) q[++tt]=i;
}
while(hh<=tt){//bfs遍历
int t=q[hh++];
for(int i=h[t];i!=-1;i=ne[i]){
int j=e[i];
d[j]--;//遍历完一条边删除一条边，即终点的入度-1
if(d[j]==0) q[++tt]=j;//入度为0则加入队列等待遍历
}
}
return tt==n-1;//如果所有点最终都入度为0即为无环
}
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]++;//构建一条边就给终点入度+1
}
if(topsort()){
for(int i=0;i<n;i++) printf("%d ",q[i]);//进入队列的顺序即为图的拓扑序列
printf("\n");
}
else printf("-1\n");
return 0;
}
|