知识卡片
队列驱动逐层图遍历
广度优先搜索从根节点入队,反复取队首并把尚未发现的邻居放到队尾,因而先处理较浅层,再处理更深层。网页爬取将页面视为节点、超链接视为边;深度、范围或目标条件决定何时停止,遍历顺序本身不会保证爬完无限网络。
结构图:算法流程。
flowchart TD
A["根节点标记发现并入队"] --> B{"队列非空且未越界?"}
B -->|是| C["取队首并处理"]
C --> D["检查各邻居与停止边界"]
D --> E["未发现邻居标记并入队"]
E --> B
B -->|否| F["结束并记录范围"]
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 2 处
- · 查看原书依据
empty queue to keep track of nodes that need to be processed Add the starting point to the graph as the root node Add the root node to a queue for processing Repeat until some maxi
- · 查看原书依据
每个深度完成探索之后才进入下一深度的探索(见示例9-22)。 请记住,很可能在探索Twitter的好友关系图时会遇到超级节点。超级节点是那些具有很高出度的节点,它消耗计算机资源以及API请求以致到达访问速率上限的速度很快。至少在你初始分析时,你控制图中每个待获取用户的关注者的最大数量是可取的。因此你可以知道你面对的困难是什么,并可以断定在解决特定问题时,那些
参考来源
- 位置:《社交网站的数据挖掘与分析(原书第2版)》第5章《5.2.1 网页爬取中的广度优先搜索》(spine93;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part0082.html;u075-ch05-006)。
- 结论依据:原文在“empty queue”附近的定义、例子或代码支撑本卡核心说明:广度优先搜索从根节点入队,反复取队首并把尚未发现的邻居放到队尾,因而先处理较浅层,再处理更深层。边界按已读前提解释;示例未执行。
- 原始内容:empty queue to keep track of nodes that need to be processed Add the starting point to the graph as the root node Add the root node to a queue for processing Repeat until some maxi
- 位置:《社交网站的数据挖掘与分析(原书第2版)》第9章《9.22.3 讨论》(spine148;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part0137.html;u225-ch05-006)。
- 结论依据:好友图同样按层推进,但实际接口权限与截断限制可探索范围。
- 原始内容:每个深度完成探索之后才进入下一深度的探索(见示例9-22)。 请记住,很可能在探索Twitter的好友关系图时会遇到超级节点。超级节点是那些具有很高出度的节点,它消耗计算机资源以及API请求以致到达访问速率上限的速度很快。至少在你初始分析时,你控制图中每个待获取用户的关注者的最大数量是可取的。因此你可以知道你面对的困难是什么,并可以断定在解决特定问题时,那些