27｜掘地三尺：实战深度与广度优先搜索算法
郑建勋
你好，我是郑建勋。
上节课，我们看到了如何在 Go 中创建高并发模型，这节课让我们回到项目中来，为爬虫项目构建高并发的模型。
要想构建高并发模型，我们首先要做的就是将一个大任务拆解为许多可以并行的小任务。比方说在爬取一个网站时，这个网站中通常会有一连串的 URL 需要我们继续爬取。显然，如果我们把所有任务都放入到同一个协程中去处理，效率将非常低下。那么我们应该选择什么方式来拆分出可以并行的任务，又怎么保证我们不会遗漏任何信息呢？
要解决这些问题，我们需要进行爬虫任务的拆分、并设计任务调度的算法。首先让我们来看一看两种经典的爬虫算法：深度优先搜索算法（Depth-First-Search，DFS）和广度优先搜索算法（Breadth-First Search，BFS）, 他们也是图论中的经典算法。
深度优先搜索算法
深度优先搜索算法是约翰·霍普克洛夫特和罗伯特·塔扬共同发明的，他们也因此在 1986 年共同获得计算机领域的最高奖：图灵奖。
以下图中的拓扑结构为例，节点 A 标识的是爬取的初始网站，在网站 A 中，有 B、C 两个链接需要爬取，以此类推。深度优先搜索的查找顺序是： 从 A 查找到 B，紧接着查找 B 下方的 D，然后是 E。查找完之后，再是 C、F，最后是 G。可以看出，深度优先搜索的特点就是“顺藤摸瓜”，一路向下，先找最“深”的节点。
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
本文介绍了深度优先搜索算法（DFS）和广度优先搜索算法（BFS）在爬虫项目中的应用。作者首先强调了构建高并发模型的重要性，指出将大任务拆解为可以并行处理的小任务是实现高并发的关键。然后详细介绍了DFS和BFS算法的原理和应用场景。DFS以“顺藤摸瓜”的方式深入搜索，适用于查找图的最长路径和解决迷宫问题等场景。而BFS则采用逐层遍历树的节点的方式，适用于计算最短路径和实现广度优先搜索查找存活内存等场景。文章还给出了DFS和BFS算法的实现代码，并以计算机课程选修和网站爬取为例进行了详细说明。此外，文章还介绍了使用Cookie突破反爬封锁的机制。总的来说，本文通过深入浅出的方式介绍了DFS和BFS算法在爬虫项目中的应用，为读者提供了深入理解和实践应用的指导。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《Go 进阶 · 分布式爬虫实战》，新⼈⾸单¥68
《Go 进阶 · 分布式爬虫实战》，新⼈⾸单¥68
立即购买
© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
登录 后留言
全部留言(7)
- 最新
- 精选
徐海浪有个疑问，多个协程之间怎么协调等待时间？作者回复: 后面会看到用限流器来实现
2022-12-14归属地：广东
田小麦能把复杂问题简单化，也是学问。有种标题造火箭，内容提取干货很吃力2023-02-08归属地：北京6
Geek_8ed998又不标tag了，想到那写到那一段一段的2023-04-19归属地：上海12
佩奇解析正文内容中包含阳台的正则表达式，会把右侧边栏的内容也解析进去，可以调整为下面的方式 ``` const ContentRe = `<div\s+class="topic-content">(?s:.)*?</div>` func GetContent(contents []byte, url string) collect.ParseResult { re := regexp.MustCompile(ContentRe) resultStr := re.FindString(string(contents)) r2 := regexp.MustCompile("阳台") ok := r2.MatchString(resultStr) if !ok { return collect.ParseResult{ Items: []interface{}{}, } } result := collect.ParseResult{ Items: []interface{}{url}, } return result } ```2023-11-16归属地：中国香港- 徐海浪即使切换了User-Agent更换了IP，反爬虫还是可以根据其他(比如令牌)知道是同一个用户访问，这时就得用账号池了吧2022-12-14归属地：广东
抱紧我的小鲤鱼1. 递归主要会带来的效率问题，函数调用带来的额外开销（函数的入栈出栈），栈容量的限制（次数太多可能会stack overflow） 2. 使用UA池，随机选取一个？2022-12-11归属地：江苏
拾掇拾掇
1.递归会导致栈溢出，而且递归一旦没写好就是死循环了 2.那就user_agent搞多一点，然后随机取2022-12-10归属地：浙江
收起评论
