蓝桥备战准备记录 1

标题 浅谈深搜与广搜

众所周知，DFS和BFS都是搜索中的入门技巧，今天我就来说一遍DFS和BFS这俩玩意

首先，是我们的DFS选手，用一个形象的比喻来比喻DFS的话，那就是DFS是一个单纯的男孩，这个男孩在追求一个女孩的过程中是不到最后绝不放弃，直到被女孩拒绝后，他才会回溯，去寻找新的机会。
如图所示，这个男孩追求一个女孩失败后，会读取存档到上一个阶段，走别的路线，如果每条路线都失败了的话，这个男孩就会彻底放弃这个女孩，回到初始的位置，重新进行游戏，这就是我们的DFS小伙
接着来看看核心的代码

void dfs(int girl, int u)//girl代表女孩编号,u代表走的剧情线
{
	if (girl > /*女孩数*/) return;//你是个单身狗,游戏结束
	if (u > /*本女孩路线数*/) {//说明这个女孩不爱你，放弃她吧
		dfs(girl + 1, 0);//回溯存档到下一个女孩
		return;//删档
	}

	//下面的这个标记，是dfs非常关键的部分,要防止死循环
	vis[girl][u] = true;//本女孩的第u条剧情线走过

	for (int i = /*剧情下一点*/; i < /*剧情的分支路线*/; i -> /*下一个分支*/) {
		dfs(girl, i);//找寻下一个路线有没有出路
		vis[girl][u] = false;//记得存档
		if (/*这个路线走到最后女孩和你在一起*/) {
			cout << "恭喜你" << endl;//happy end
			return;//结束本次游戏
		}
	}
}

这就是DFS的核心思路了，走完一个地方,要在这个地方做好记号，同时存下自己的存档，防止自己下一次又走回这个路线，那就浪费时间了，在本次存档失败后，就要找到自己上一次存档，从上一次存档继续寻找有没有GOOD END，如果这些存档都没有，那就死档了，删档重来吧！！！

接着我们要来谈谈BFS了，我们的BFS选手，他和DFS选手不一样，这个选手在追求女孩的时候，不会一个一个的去追求，而是会选择同时他身边的所有女孩（牛逼吼），只有BFS找到一个真正好的女孩后，他才会放弃其他女孩。

就像这幅图一样，这个男孩会对三个女孩同时示好，接着也会同时走这三个女孩的剧情线，直到走到一个真爱路线，他才会放弃周围的其他女孩，对于这个男孩来说，他不需要存档，他可以一口气莽下去，把所有路线都走过去，直到走到GOOD END
接着来看看我们的核心代码

void bfs()
{
	queue</*剧情类型*/> lp;

	lp.push(/*先把三个女孩推入队列中*/);//同时找三个女孩示好

	while (!lp.empty()) {//只要这个队列不是空的,说明这个男孩还有机会
		/*剧情类型*/ now = lp.front();//取出队首
		lp.pop();//队首元素出队

		for (int i = /*可以走的女孩的下一个路线*/; i < /*这些女孩的全部剧情路线*/; i -> /*下一个剧情路线*/) {
			if (/*如果这个剧情路线后面还有路*/) {
				lp.push(/*这条剧情线*/);//让这条线入队
			}
			if (/*这个剧情的女孩是你的真爱*/) {
				cout << "恭喜你" << endl;
				break;//游戏结束
			}
		}
	}
}

这就是BFS的核心思路了，他会走过他附近的每一个可能，只要这个可能接下来还有希望，他就会接着走，是一个高效率的“找女朋友的方式”？（要不你来试试）

最后呢，DFS和BFS各有优缺点
DFS的优点就是,他没钱！每次只能追一个女孩,所以他每次只容纳下一个女孩的剧情线,空间复杂度为O(n),而时间复杂度就截然不同了，他会一个一个的去寻找，直到找到真爱，倘若路线多的话,他可能一辈子都找不到,所以他时间复杂度非常高.
BFS的优点就是,他有钱！他的资金能够支撑自己同时追求多个女孩，把每一个女孩的剧情线都走过，因此,BFS找真爱的路途就很短暂,他的效率非常高，所以时间复杂度非常小，而又因为他同时追求多个女孩，所以他的开销大，花钱大把大把的花，空间复杂度O(很大很大)。