【待更新】深度优先搜索和广度优先搜索算法的应用

【待更新】深度优先搜索和广度优先搜索算法的应用

深度优先搜索

1.定义

深度优先搜索算法(英语:Depth-First-Search,DFS)是一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。

深度优先搜索是图论中的经典算法,利用深度优先搜索算法可以产生目标图的相应拓扑排序表,利用拓扑排序表可以方便的解决很多相关的图论问题,如最大路径问题等等。

2.应用

例题1

有n件物品,每件物品的重量为w[i],价值为c[i]。现在需要选出若干件物品放入一个容量为V的背包中,使得在选入背包的物品重量和不超过容量V的前提下,让背包中物品的价值之和最大,求最大价值。(1≤n≤20)

如果使用DFS算法思想来解决这道题,就需要考虑到每一个物品都可以看作一个结点,而这道题可以构成一个特殊的数(从根节点开始,每一层只有一个结点),通过递归深度遍历每一个结点,然后穷尽所有可能的排列,最后更新某一个特征值。

C++语言实现:

#include<iostream>
using namespace std;

#define maxn 30
int n,v;
int maxvalue=0;
int w[maxn], c[maxn];

/*
函数会一直递归调用下去,只要index没有到达n,如果到达n,则说明所有物品的岔路都已经穷举完了
每次新添加一个物品,都会生成新的岔路,每个岔路有两个选择,即是否将当前物品添加到背包
递归结束,会有2^n个方案,其中满足总容量<v且价值超出历史最大价值时,更新当前最大价值
*/
void dfs(int index,int sumv,int sumvalue) {
    //递归终止条件
	if(index == n) {
		if(sumv<=v&&sumvalue>maxvalue) {
			maxvalue = sumvalue;
		}
		return ;
	}
	dfs(index+1,sumv,sumvalue);
	dfs(index+1,sumv+w[index],sumvalue+c[index]);
}

/*
对上面的实现进行"剪枝"优化,即每次进行岔路选择的时候,如果添加当前物品到背包中会超出容量v
则不添加该物品
经过优化以后,所有的岔路方案都是总容量不超出v的方案
*/
void dfs2(int index,int sumv,int sumvalue) {
	if(index == n) {
		if(sumvalue>maxvalue) {
			maxvalue = sumvalue;
		}
		return ;
	}
	dfs(index+1,sumv,sumvalue);
	if(sumv+w[index]<=v)
		dfs(index+1,sumv+w[index],sumvalue+c[index]);
}
int main() {

	scanf("%d%d",&n,&v);

	for(int i =0; i<n; i++) {
		scanf("%d",&w[i]);
	}
	for(int i =0; i<n; i++) {
		scanf("%d",&c[i]);
	}
	dfs(0,0,0);
	printf("最大价值为:%d",maxvalue);
	return 0;
}

Input:

5 8
3 5 1 2 2
4 5 2 1 3

Output:

最大价值为:10

3.总结

待更新

广度优先搜索

1.定义

广度优先搜索算法(英语:Breadth-First-Search,缩写为BFS),又译作宽度优先搜索,或横向优先搜索,是一种图形搜索算法。简单的说,BFS是从根节点开始,沿着树的宽度遍历树的节点。如果所有节点均被访问,则算法中止。

2.应用

例题1

给出一个m*n的矩阵,矩阵中的元素为0或1。称位置(x,y)与其上下左右四个位置(x,y+1)、(x,y-1)、(x+1,y)、(x-1,y)是相邻的。如果矩阵中有若干个1是相邻的(不必两两相邻),那么称这些1构成了一个“块”。求给定的矩阵中“块”的个数。
0111001
0010000
0000100
0001110
1110100
1111000

例如上面的6×7的矩阵中,“块”的个数为4。

#include<iostream>
#include<queue>
using namespace std;
const int maxn = 100;
int m,n;
struct node {
	int x,y;
};

int matrix[maxn][maxn];
bool inq[maxn][maxn] = {false};
int X[4] = {0,0,1,-1};
int Y[4] = {1,-1,0,0};
bool judge(int x,int y) {
	if(x>=m||x<0||y>=n||y<0)
		return false;
	if(matrix[x][y]==0||inq[x][y]==true)
		return false;
	return true;
}

void bfs(int x,int y) {
	queue<node> Q;
	node Node;
	Node.x = x,Node.y = y;
	Q.push(Node);
	while(!Q.empty()) {
		node tmp = Q.front();
		Q.pop();
		//标记该位置相邻的位置
		for(int i =0; i<4; i++) {
			int newx = tmp.x+X[i];
			int newy = tmp.y+Y[i];
			if(judge(newx,newy)) {
				node newnode ;
				newnode.x=newx;
				newnode.y=newy;
				
				Q.push(newnode);
				inq[newx][newy] = true;
			}
		}
	}
}
int main() {
	scanf("%d%d",&m,&n);
	for(int i =0;i<m;i++){
		for(int j=0;j<n;j++){
			scanf("%d",&matrix[i][j]);
		}
	}
	int ans = 0;
	for(int i =0;i<m;i++){
		for(int j=0;j<n;j++){
			if(matrix[i][j]==1&&inq[i][j]==false){
				ans++;
				inq[i][j]=true;
				bfs(i,j);
			}
		}
	}
	printf("%d",ans);
	return 0;
}

Input:

6 7
0 1 1 1 0 0 1
0 0 1 0 0 0 0
0 0 0 0 1 0 0
0 0 0 1 1 1 0
1 1 1 0 1 0 0
1 1 1 1 0 0 0

Output:

4

例题2

给定一个n*m大小的迷宫,其中*代表不可通过的墙壁,而“.”代表平地,S表示起点,T代表终点。移动过程中,每次只能前往上下左右四个位置的平地。求从起点S到达终点T的最少步数。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;

const int maxn = 100;
struct node {
	int x,y;
	int step;
} S,T,Node;

int n,m;
char maze[maxn][maxn];
bool inq[maxn][maxn] = {false};
int X[4] = {0,0,1,-1};
int Y[4] = {1,-1,0,0};

bool test(int x,int y) {
	if(x>= n||x<0||y>= m||y<0) return false;
	if(maze[x][y] == '*') return false;
	if(inq[x][y] == true) return false;
	return true;
}

int BFS() {
	queue<node> q;
	q.push(S);
	while(!q.empty()) {
		node top = q.front();
		q.pop();
		if(top.x ==T.x&& top.y ==T.y) {
			return top.step;
		}
		for(int i=0; i<4; i++) {
			int newx = top.x +X[i];
			int newy = top.y +Y[i];
			if(test(newx,newy)) {
				Node.x = newx,Node.y = newy;
				Node.step = top.step+1;
				q.push(Node);
				inq[newx][newy] = true;
			}
		}
	}
	return -1;
}

int main() {
	scanf("%d%d",&n,&m);
	for(int i=0; i<n; i++) {
		getchar();
		for(int j=0; j<m; j++) {
			maze[i][j] = getchar();
		}
		maze[i][m+1] = ' ';
	}
	scanf("%d%d%d%d",&S.x,&S.y,&T.x,&T.y);
	S.step = 0;
	printf("%d",BFS());
	return 0;
}

Input:

5 5
.....
.*.*.
.*S*.
.***.
...T*
2 2 4 3

Output:

11

3.总结

DFS&BFS

通过对上面的例题以及代码实现,不难发现,DFS就是结合递归来实现,在写代码的时候,需要考虑如何把问题抽象成可以递归的场景,然后根据题目的要求分析出递归终止条件,以及传递公式

BFS,需要结合队列来实现,每次都是先遍历同一个层次的所有结点(抽象表示),然后根据顺序依次加入队列,每次循环的时候,判断队列是否为空,如果不为空再把队列头结点取出,然后再把这个头节点对应的所有子节点按照顺序依次加入队列,一直到所有的结点都入队列。通常需要一个辅助容器来记录结点是否入过队列。

参考资料:

本文待更新,目前只涉及到算法思想以及简单应用,后期继续补充两个算法思想在树和图中的应用