深度优先搜索(DFS)

2021年6月27日 7点热度 0条评论 来源: 志远1997

什么是深度优先搜索?

    从起点出发,走过的点要做标记,发现有没走过的点,就随意挑一个往前走,走不了就回退,此种路径搜索策略就称为“深度优先搜索”,简称“深搜”。


以题目为例子学习

题目一:从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;
}

至此,相信大家都对深度优先搜索有了更加深刻的了解,如果还有疑问,一定要耐下心来把这些代码再搞一遍,我这样走过来感觉收获很大。

    原文作者:志远1997
    原文地址: https://blog.csdn.net/qq_33302004/article/details/79671880
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。