type
status
date
slug
summary
tags
category
icon
password
Email
文章首发于：My Blog 欢迎大佬们前来逛逛
模板+解析
DFS（深度优先搜索）和BFS（广度优先搜索）是图论中两个重要的算法。
dfs
其中DFS是一种用于遍历或搜索树或图的算法，BFS则是一种用于搜索或遍历树或图的算法。两种算法都有其自身的优点和缺点，应用于不同的场景中。 DFS（深度优先搜索） 深度优先搜索是一种用于遍历或搜索树或图的算法，其基本思路是从起始节点开始，沿着一条路径一直走到底，直到无法再走下去为止，然后回溯到上一个节点，继续走到另外一个路径，重复上述过程，直到遍历完所有节点。
DFS的实现方式可以采用递归或者栈来实现。下面是一个采用递归方式实现的DFS代码示例（C++）：
bfs
BFS（广度优先搜索） 广度优先搜索是一种用于搜索或遍历树或图的算法，其基本思路是从起始节点开始，依次遍历当前节点的所有邻居节点，然后再依次遍历邻居节点的所有邻居节点，直到遍历到目标节点或者遍历完所有节点。 BFS的实现方式可以采用队列来实现。下面是一个采用队列方式实现的BFS代码示例（C++）：
总结 DFS和BFS都是图论中常用的搜索算法，其应用广泛，例如在寻路、迷宫问题、拓扑排序、连通性等问题中都有应用。两种算法的实现方式不同，DFS采用递归或者栈实现，而BFS采用队列实现。在应用场景中，需要根据实际情况选择合适的算法来解决问题。
1562. 微博转发
题目要求：有n个人，每个人都有关注的人和粉丝，如果某一个人发了一条微博，则他的粉丝们都会进行转发，而他的粉丝又会被他的粉丝的粉丝转发，求出在 L层关注者的前提下，微博转发数量的最大值。
我们可以观察到每个明星都有粉丝，则这些粉丝就是他们的孩子们，我们把这个明星看作是树的根节点，因此题目要求就是让我们求 从根节点出发在k层以内的不同的孩子节点的个数。
注意到题目输入的是 某一个人关注了这个明星。是一个从孩子节点到根节点的路径
我们可以把这个路径反过来，写成：谁的粉丝有谁。
这样我们就可以转换成一个树结构，从根节点出发在k层内的孩子的个数。
转换的关系如下所示，表示 x节点的孩子是 n1,n2...
然后利用bfs求得在k层内的最大的数量，其中对于k层的约束我们可以使用一个步数来进行表示，如果步数超过了k步，则直接退出；否则记录孩子的数量，同时进入孩子节点，重新开始bfs。
最后经过了bfs后，我们得到的一定k层以内最全的孩子的数量。
我们可以使用邻接矩阵表示他们的关系，可以使用vector容器，也可以自己实现一个链式前向星存图，不过：
vector容器耗时： 1339 ms
链式前向星：388 ms
Ac代码如下：
3502. 不同路径数
题目要求：在一个n*m的矩阵中，每走一步可以添加一个数字，最终走完k步，一共可以构成多少个不同的数字？
n和m的数据范围非常小，最大只有5，而且k也很小，因此我们随便造就完了
很明显我们使用深搜。直接暴力搜索所有的数字即可，然后存在一个set中，最后返回set的元素数量。
165. 小猫爬山
题目要求：有n个物品，每几个物品之间都可以放在一辆车上，前提是这几件物品的重量不能超过车的最大承受重量，每一辆车一美元，求得最少需要支付多少美元，才能运完这些全部的物品。
一看到这道题貌似就能看出可以用贪心来做。
即按照从大到小或者从小到大排序，然后如果超过了重量则新增一辆车。
但是！！贪心并不是最优的选择。为什么呢？
就像换硬币一样，我们贪心并不能得到最优的选择，动态规划才是最后的选择（
我忘记哪道题了，有知道的大佬可以评论区回复我以下）因此我们选择深搜，并且这道题也是非常经典的一类深搜问题。
遍历所有的物品：
- 如果当前物品可以放入这辆车，则放入这辆车，车辆总数不变，但是物品编号+1，表示开始下一个物品
- 如果当前物品不能放入这辆车，则需要新增加一辆车，而且物品编号也要+1.
- 每一个物品可以选择放入这辆车，也可以选择不放入，因此需要进行回溯
- 剪枝：如果当前车辆数量超过了答案，则一定不是最优解
- 当 最后一个物品也成功放入后，即 now-1==n ，则全部物品都放入，则记录答案。
- 作者:Yuleo
- 链接:https://www.helloylh.com/article/5455ab9d-4d6f-4c0e-b4e0-38e792439066
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。