深度优先搜索（DFS）
程序员文章站
2022-06-11 15:19:46
...
什么是深度优先搜索？
从起点出发，走过的点要做标记，发现有没走过的点，就随意挑一个往前走，走不了就回退，此种路径搜索策略就称为“深度优先搜索”，简称“深搜”。
以题目为例子学习
题目一：从1点出发能否到达8？
伪代码：
bool Dfs(V) {
if( V 为终点） return true;
if( V 为旧点) return false;
将V标记为旧点;
对和V相邻的每个节点U {
if( Dfs(U) == true) return true;
}
return false;
}
c++代码（二维矩阵存图;A记为0）：
/*
深度优先搜索
图：①二维数组G存，G[i][j]表示点ij是否连通（或权值）,遍历复杂度o(n^2)
②每个点对应一个一维数组，存出去的边，遍历复杂度o(n+e)
*/
#include<iostream>
using namespace std;
int G[10][10]={0};//图
int mark[10]={0};//标记是否走过
void init()//初始化图（邻接表）;初始化标记
{
G[1][2]=1; G[2][1]=1;
G[1][3]=1; G[3][1]=1;
G[2][4]=1; G[4][2]=1;
G[3][4]=1; G[4][3]=1;
G[3][5]=1; G[5][3]=1;
G[3][7]=1; G[7][3]=1;
G[4][8]=1; G[8][4]=1;
G[4][5]=1; G[5][4]=1;
G[5][6]=1; G[6][5]=1;
G[6][8]=1; G[8][6]=1;
G[7][0]=1; G[0][7]=1;
G[7][9]=1; G[9][7]=1;
}
bool fun(int x)
{
if(x==8)
return true;
if(mark[x]==1)
return false;
mark[x]=1;
for(int i=0;i<10; i++)
{
if(G[x][i]==1)
if(fun(i))
return true;
}
return false;
}
int main()
{
init();
if(fun(1))
cout<<"Y";
else
cout<<"N";
return 0;
}题目二：输出从1到8的最短路径
伪代码：
bool Dfs(V) {
int bestPath[MAX_LEN];
int minSteps = INFINITE; //最优路径步数
int path[MAX_LEN]; //MAX_LEN取节点总数即可
int depth;
void Dfs(V) {
if( V为终点）{
path[depth] = V;
if( depth < minSteps ) {
minSteps = depth;
拷贝path到bestPath;
}
return;
}
if( V 为旧点) return;
if( depth >= minSteps ) return ; //最优性剪枝
将V标记为旧点;
path[depth]=V;
++depth;
对和V相邻的每个节点U { Dfs(U);}
--depth;
将V恢复为新点
}
我的c++代码（用一维向量数组描述图）：
/*
深度优先搜索
图：①二维数组G存，G[i][j]表示点ij是否连通（或权值）,遍历复杂度o(n^2)
②每个点对应一个一维数组，存出去的边，遍历复杂度o(n+e)
*/
#include<iostream>
#include<vector>
using namespace std;
vector<int> G[10];//存图
/*
vector<type> name;//声明
name.push_back(); //末尾加值
name.insert(); //最前面加值
name.size(); //返回长度，用于循环
name.pop_back(); //删除最后一个元素
name.erase(); //删除指定位置元素
name.clear(); //清空
*/
int mark[10];//标记是否走过
int answer_len=20;
int answer[10];
int arr_len=0;
int arr[10];
void init()//初始化图（邻接表）;初始化标记
{
for(int i=0 ;i<10;i++)
mark[i]=0;
G[0].push_back(7);
G[1].push_back(2); G[1].push_back(3);
G[2].push_back(1); G[2].push_back(4);
G[3].push_back(1); G[3].push_back(4); G[3].push_back(5); G[3].push_back(7);
G[4].push_back(2); G[4].push_back(3); G[4].push_back(5); G[4].push_back(8);
G[5].push_back(3); G[5].push_back(4); G[5].push_back(6); G[5].push_back(8);
G[6].push_back(5); G[6].push_back(8);
G[7].push_back(0); G[7].push_back(3); G[7].push_back(9);
G[8].push_back(4); G[8].push_back(6);
G[9].push_back(7);
}
void dfs(int x)
{
if(x==8)//到达终点
{
if(arr_len<answer_len)
{
answer_len=arr_len;
for(int i=0 ;i<answer_len; i++)
answer[i]=arr[i];
}
}
if(mark[x]==1)//走过
return;
if(arr_len>=answer_len)//剪枝
return;
mark[x]=1;//标记为走过
arr[arr_len++]=x;//存入临时数组
for(int i=0; i<(int)G[x].size(); i++)
dfs(G[x][i]);
mark[x]=0;//撤销到上一个原始状态
arr_len--;
}
int main()
{
init();
dfs(1);
cout<<"最短路径为：";
for(int i=0; i<answer_len; i++)
cout<<answer[i]<<"-";
cout<<8;
return 0;
}若只输出最短路径的长度，用广搜更快一些
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
using namespace std;
vector<int> G[10];//存图
struct step
{
int p;
int steps;
step(int pp, int s):p(pp),steps(s){}
};
queue<step> q;
void init()//初始化图（邻接表）;初始化标记
{
G[0].push_back(7);
G[1].push_back(2); G[1].push_back(3);
G[2].push_back(1); G[2].push_back(4);
G[3].push_back(1); G[3].push_back(4); G[3].push_back(5); G[3].push_back(7);
G[4].push_back(2); G[4].push_back(3); G[4].push_back(5); G[4].push_back(8);
G[5].push_back(3); G[5].push_back(4); G[5].push_back(6); G[5].push_back(8);
G[6].push_back(5); G[6].push_back(8);
G[7].push_back(0); G[7].push_back(3); G[7].push_back(9);
G[8].push_back(4); G[8].push_back(6);
G[9].push_back(7);
}
int main()
{
init();
step x(1,1);
q.push(x);
while(!q.empty())
{
x=q.front();
q.pop();
if(x.p==8)
{
cout<<x.steps;
return 0;
}
else
{
for(int i=0; i<(int)G[x.p].size(); i++)
q.push(step(G[x.p][i],x.steps+1));
}
}
return 0;
} 题目三：深度优先遍历所有点
我的c++代码：
#include<iostream>
#include<vector>
using namespace std;
vector<int> G[10];//存图
int mark[10];//标记是否走过
int answer_len=20;
int answer[10];
int arr_len=0;
int arr[10];
void init()//初始化图（邻接表）;初始化标记
{
for(int i=0 ;i<10;i++)
mark[i]=0;
G[0].push_back(7);
G[1].push_back(2); G[1].push_back(3);
G[2].push_back(1); G[2].push_back(4);
G[3].push_back(1); G[3].push_back(4); G[3].push_back(5); G[3].push_back(7);
G[4].push_back(2); G[4].push_back(3); G[4].push_back(5); G[4].push_back(8);
G[5].push_back(3); G[5].push_back(4); G[5].push_back(6); G[5].push_back(8);
G[6].push_back(5); G[6].push_back(8);
G[7].push_back(0); G[7].push_back(3); G[7].push_back(9);
G[8].push_back(4); G[8].push_back(6);
G[9].push_back(7);
}
void dfs(int x)
{
if(mark[x]==1)//走过
return;
mark[x]=1;
cout<<x<<" ";
for(int i=0; i<(int)G[x].size(); i++)
dfs(G[x][i]);
}
int main()
{
init();
dfs(1);
return 0;
}小结：
深度优先搜索遍历所有点模板：
#include<iostream>
#include<vector>
using namespace std;
vector<int> G[10]; //存图,几个点长度就位多少
int mark[10]; //标记是否走过
void init() //初始化图（邻接表）;初始化标记
{}
void dfs(int x)
{
if(mark[x]==1) //走过则停止
return;
mark[x]=1; //没走过，标记为走过，然后按照他的路径继续走
for(int i=0; i<(int)G[x].size(); i++)
dfs(G[x][i]);
}
int main()
{
init();
dfs(1);
return 0;
}深度优先搜索比较最短路径/路径数量模板：
vector<int> G[10]; //存图,几个点长度就位多少
int mark[10]; //标记是否走过
void init() //初始化图（邻接表）;初始化标记
{}
void dfs(int x)
{
if(x==8) //到达终点
{
//进行所需操作
return;
}
if(mark[x]==1) //走过则停止
return;
if()//寻找最短路径用于剪枝
mark[x]=1; //没走过，标记为走过
//路径长度+1，存储节点等操作
for(int i=0; i<(int)G[x].size(); i++)
dfs(G[x][i]);
mark[x]=0; //回复原来的状态
//路径长度减一等操作
}
int main()
{
init();
dfs(1);
return 0;
}【例题1】城堡问题
我的c++代码：
#include<iostream>
using namespace std;
int room[55][55];
int mark[55][55];
int flag=0;
int size=0;
bool left(int x)//no 1
{
if(x==1||x==3||x==5||x==9||x==7||x==11||x==13||x==15)
return false;
return true;
}
bool up(int x)//no 2
{
if(x==2||x==3||x==6||x==10||x==7||x==11||x==14||x==15)
return false;
return true;
}
bool right(int x)//no 4
{
if(x==4||x==5||x==6||x==12||x==7||x==13||x==14||x==15)
return false;
return true;
}
bool down(int x)//no 8
{
if(x==8||x==9||x==10||x==12||x==11||x==13||x==14||x==15)
return false;
return true;
}
void DFS(int i, int j)
{
if(mark[i][j]!=0)//到终点
return;
mark[i][j]=flag;//标记为旧点
size++;
//递归搜索寻点ij可去的点
if(left(room[i][j])) DFS(i,j-1);
if(right(room[i][j])) DFS(i,j+1);
if(up(room[i][j])) DFS(i-1,j);
if(down(room[i][j])) DFS(i+1,j);
}
int main()
{
int m,n;
cin>>m>>n;
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
{
cin>>room[i][j];
mark[i][j]=0;
}
int biggest_room=0;
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(mark[i][j] == 0)//没走过
{
flag++;
size=0;
DFS(i,j);
}
if(size > biggest_room) biggest_room =size;
}
}
cout<<flag<<endl;
cout<<biggest_room<<endl;
return 0;
}【例题2】踩方格
c++代码：
#include<iostream>
using namespace std;
int visited[50][25];
int dfs(int i, int j, int n)
{
if(n == 0)
return 1;
visited[i][j]=1; //标记为到过
int ans=0;
if(visited[i-1][j]==0)
ans+=dfs(i-1,j,n-1);
if(visited[i+1][j]==0)
ans+=dfs(i+1,j,n-1);
if(visited[i][j-1]==0)
ans+=dfs(i,j-1,n-1);
visited[i][j]=0;//恢复标记
return ans;
}
int main()
{
for(int i=0;i <50; i++)
for(int j=0; j<25; j++)
visited[i][j]=0;
int n;
cin>>n;
cout<<dfs(25,25,n);
return 0;
}【例题3】寻路问题
Sample Input
5 6 7 1 2 2 3 2 4 3 3 3 4 2 4 1 3 4 1 4 6 2 1 3 5 2 0 5 4 3 2
Sample Output
11
我的c++代码：
#include<iostream>
#include<vector>
using namespace std;
int k, n, r;//钱，城市，路
vector<int> *L; //长度
vector<int> *T; //过路费
vector<int> *End; //可到城市
int *visited; //是旧点为1； 新点为0
int short_len=10000; //最短长度
int len=0; //长度的中间变量
int price=0; //费用
int answer=-1; //最后输出的结果
void dfs(int x)
{
if(x==n) //到达终点
{
if(len<short_len && price<=k)
{
short_len = len;
answer= short_len;
return;
}
}
if(visited[x]!=0) //旧点
return;
if(price>k) //剪枝1
return;
if(len>=short_len) //剪枝2
return;
visited[x]=1; //新点的循环
for(int i=0 ;i<(int)End[x].size(); i++)
{
price+=T[x][i];
len+=L[x][i];
dfs(End[x][i]);
price-=T[x][i];
len-=L[x][i];
}
visited[x]=0;
}
int main()
{
cin>>k>>n>>r;
visited = new int[n+1];
for(int i=1; i<=n; i++)
visited[i]=0;
L=new vector<int>[n+1];
T=new vector<int>[n+1];
End=new vector<int>[n+1];
for(int i=1; i<=r; i++)
{
int s, e, l ,t;
cin>>s>>e>>l>>t;
End[s].push_back(e);//通过End可以找到城市s可以到哪些城市
L[s].push_back(l);//先用End找e 与End相同位置的 L存储两城市之间距离
T[s].push_back(t);//先用End找e 与End相同位置的 T存储两城市之间过路费
short_len+=l;
}
dfs(1);
cout<<answer;
//测试
//int x;
//cin>>x;
//for(int i=0 ;i<(int)End[x].size(); i++)
//{
// cout<<"终点："<<End[x][i]<<" 距离:"<<L[x][i]<<" 过路费："<<T[x][i]<<endl;
//}
return 0;
}
【例题4】生日蛋糕（POJ1190）
描述
7月17日是Mr.W的生日，ACM-THU为此要制作一个体积为Nπ的M层生日蛋糕，每层都是一个圆柱体。
设从下往上数第i(1 <= i <= M)层蛋糕是半径为Ri, 高度为Hi的圆柱。当i < M时，要求Ri > Ri+1且Hi > Hi+1。
由于要在蛋糕上抹奶油，为尽可能节约经费，我们希望蛋糕外表面（最下一层的下底面除外）的面积Q最小。
令Q = Sπ
请编程对给出的N和M，找出蛋糕的制作方案（适当的Ri和Hi的值），使S最小。
（除Q外，以上所有数据皆为正整数）
输入
有两行，第一行为N（N <= 10000），表示待制作的蛋糕的体积为Nπ；第二行为M(M <= 20)，表示蛋糕的层数为M。
输出
仅一行，是一个正整数S（若无解则S = 0）。
样例输入
100
2
样例输出
68
我的c++代码：
#include<iostream>
#include<cmath>
using namespace std;
int V, M;//体积， 层数
int area=0;
int min_area=100000000;
int minv[30]; //由上到下，上面i层的最小体积
int maxv(int m,int r, int h)
{
int v=0;
for(int i=0; i<m; i++)
v+=(h-i)*(r-i)*(r-i);
return v;
}
void fun(int v, int m, int maxr, int maxh)//用m层凑出体积v，最大半径为maxr， 最大高度maxh
{
if(m==0)//最后一层
{
if(v!=0) return;
else if(area<min_area) min_area =area;
return;
}
//剪枝
if(v<minv[m]) return;
if(v>maxv(m,maxr,maxh)) return;
if(area>=min_area) return;
//剪枝
for(int r=maxr; r>=m; r--)
{
if(m==M) area=r*r;
for(int h=maxh; h>=m; h--)
{
area+=2*h*r;
fun(v-h*r*r,m-1,r-1,h-1);
area-=2*h*r;
}
}
}
int main()
{
cin>>V>>M;
minv[0] = 0;
for(int i=1; i<=M; i++)//每一层最小半径和最小高度都为i
minv[i] = minv[i-1]+i*i*i;
int maxh = (V-minv[M-1])/(M*M)+1; //底层最大高度
int maxr = (int)(sqrt((double)((V-minv[M-1])/M))) + 1; //底层最大半径
fun(V,M,maxr,maxh);
if(min_area == 100000000)
cout<<0;
else
cout<<min_area;
return 0;
}至此，相信大家都对深度优先搜索有了更加深刻的了解，如果还有疑问，一定要耐下心来把这些代码再搞一遍，我这样走过来感觉收获很大。
上一篇： php简单 模板技术
下一篇： ajax仿google搜索下拉提示