干了这么多年爬虫回头复盘发现帮我解决最难问题的不是某个框架也不是更快的抓取方式而是本科时期觉得“没什么用”的图论。当时老师说计算机科学里到处都是图我以为是套话直到被几个百万级页面的爬虫项目反复按在地上摩擦才真正明白这句话的重量。你看互联网最朴素的结构就是页面和链接一个页面指向另一个页面这不就是有向图里的节点和边吗这篇博文不打算堆概念我想做的是把图论和网络爬虫真正揉在一起讲——从URL队列怎么调度、重复链接怎么去重、到网页权重怎么计算、站点依赖怎么排序每一块背后都藏着一个图论模型。适合两类人看一是刚入行、想弄懂爬虫底层原理的开发者二是已经写了很久爬虫、想用更扎实的理论来优化自己的抓取策略的老手。读完你会发现很多你已经在用的“经验”和“技巧”其实在图论里早有严谨的数学解释。1. 一张网就是一张图爬虫眼中的互联网结构1.1 节点和边把网页变成数学模型任何一个网站哪怕只是一个人维护的博客从爬虫视角看都是一张有向图。每个HTML页面是一个节点页面里每一条指向其他页面的超链接就是一条带方向的边。比如你的首页链接到了“关于我”页面那就能画一个从“首页”节点指向“关于我”节点的箭头。方向很重要因为A链到B不代表B一定会链回A这和现实里的朋友关系不太一样更像微博的关注关系。为什么要做这个抽象因为算法不是靠直觉运行的它需要结构清晰、规则明确的输入。一旦把网页抽象成节点和边整个爬虫流程就变成了“图的遍历问题”接下来的队列调度、去重策略、权重排序都能用现成的图论算法来处理。没有这一步抽象你脑子里装的全是HTML标签、CSS选择器和杂乱的URL很难建立一个全局的工程框架。1.2 从URL到图的“草稿”种子集与边扩展爬虫刚开始运行时你手上可能只有几个入口URL这些就是图的“种子节点”。在数学上整个爬虫过程就是在做这样一件事给定一个初始节点集合不断沿着边链接找到新节点新页面再把新节点上的边解析出来继续扩展直到满足停止条件比如抓够多少页面、跑完整个站点、或者达到层数限制。这个“边扩展”的核心操作其实特别简单——下载一个HTML解析出所有a href提取出URL列表过滤掉外部域名、静态资源、重复地址剩下的就加入待抓取队列。从图论角度看每处理完一个节点你就得到它的所有出边每条出边对应一个新节点或者已经被访问过的节点。如果节点已经访问过说明图中存在“回边”这是后续要用DFS、环检测处理的信号。我刚开始写爬虫时没有这么清晰的图模型写的代码就是“while 队列不为空取URL、下载、解析、塞新URL”。功能上没问题但一旦遇到网站结构复杂、链接相互缠绕的情况逻辑就会乱成一锅粥。后来习惯先画一张小图把入口页面、栏目页、详情页的链接关系标出来再动手写代码整个人的思路立马清爽了。这就是图论给你的第一层价值帮你建立清晰的全局视角。2. 抓取的顺序问题BFS和DFS的工程选择2.1 这两种遍历到底在干什么图的遍历有两种最经典的方式广度优先搜索BFS和深度优先搜索DFS。BFS的思路是一层一层地从起点向外扩展先把起点的所有邻居全抓完再抓邻居的邻居。DFS正好相反从起点出发沿着一条链一直走下去走到头了再回头探索其他分支典型的“不撞南墙不回头”。数据结构上BFS用队列FIFO谁先入队谁先出队DFS用栈LIFO最后入队的先出队。如果你写递归DFS就更自然了因为递归本身就是栈式调用。下面用Python把两个框架搭出来方便你直观感受# BFS用队列实现 def bfs_traverse(start_url, get_links): visited set() queue [start_url] visited.add(start_url) while queue: url queue.pop(0) # 先进先出 print(抓取:, url) for link in get_links(url): if link not in visited: visited.add(link) queue.append(link) # DFS用栈实现 def dfs_traverse(start_url, get_links): visited set() stack [start_url] visited.add(start_url) while stack: url stack.pop() # 后进先出 print(抓取:, url) for link in get_links(url): if link not in visited: visited.add(link) stack.append(link)这两个函数结构几乎一样唯一区别就是列表的弹出位置。但工程上差异极大BFS会先抓完离起点近的页面DFS则会一条路深入到网站最深层的内容页。如果你不理解这个差异爬虫可能分分钟把站点搞崩。2.2 真实爬虫为什么更偏爱带权的BFS实际写爬虫90%的场景我会选择BFS或者更准确地说是带优先级的BFS。原因也很直白正常站点的URL结构往往是“首页 - 栏目页 - 列表页 - 详情页”这种逐层深入的树。用BFS抓取你能在一开始就拿到质量最高的入口页面同时能较快地摸清整个站点的结构方便及时调整策略。DFS的风险在于它可能很快扎进某个无穷深的分支——比如一个带日历控件的页面日期可以无限翻页DFS会一头扎进去出不来浪费大量抓取配额。带权BFS才是工程上的完全体。所谓“权”就是给每个URL附加一个优先级数值队列按照优先级而不是入队先后来取节点。Python自带的heapq可以轻松实现优先队列。举个场景A网站首页链接了100个栏目页每个栏目页下面又有上千条列表页如果你不设优先级队列里可能混着几千个列表页URL。这时候你可以把栏目页的优先级设高让它比普通列表页先被调度页面就更早被收集全。如果用的是Scrapy框架可以直接用Request的priority参数数字越大越先被调度class MySpider(scrapy.Spider): name example_spider def parse(self, response): # 栏目页优先级设为10 for cat_url in response.css(a.category::attr(href)).getall(): yield scrapy.Request(urlcat_url, callbackself.parse_category, priority10) # 普通页面优先级默认0 for detail_url in response.css(a.detail::attr(href)).getall(): yield scrapy.Request(urldetail_url, callbackself.parse_detail, priority0)图论里的BFS给你一个最基础的遍历框架加上了“权”这个概念后它就拥有了极大灵活性你可以用页面深度、网页权重、内容类型、域名来源等任意指标来决定“下一个抓谁”。我自己做过一次对比实验同一个千万级页面站点普通BFS需要80小时能抓完所有详情页加上按PageRank权重排序的优先级后顶级内容页在30小时内全部覆盖整体效率提升非常明显。3. 重复URL怎么破从邻接表到布隆过滤器3.1 “已访问集合”存储的数学本质图遍历里有一个必备动作记录哪些节点已经访问过。如果不做记录哪怕站点只有两个互相链接的页面爬虫都会在这两个URL之间打转永远抓不到新内容。放在图上说就是遍历过程中需要维护一个“已访问顶点集合”每当有新节点出现先查这个集合再决定是否入队。最直观的实现是用哈希集合如Python的set、Redis的Set来存所有已抓取的URL。集合的查找时间复杂度是O(1)非常快。但问题是内存。一个URL平均长度按100字节算一千万个URL就是1GB左右这还没算Python对象本身的开销。放到C里也许还好但Python中一个字符串对象远不止100字节一千万个URL的内存占用可能飙到3GB以上。如果只是做个小项目放内存里没啥问题。可一旦你盯上的是整个站点甚至全网就需要从数学上看这个集合的结构了。图论中的一个核心思想是边的数量可能极其庞大如何用最少的空间来表示“哪些节点被访问过”答案就是“用模糊的精确换空间”——布隆过滤器就是这么干的。3.2 布隆过滤器原理与代码实现布隆过滤器Bloom Filter是一种基于位数组和多个哈希函数的概率性数据结构。它的原理可以用一句很“图论”的话概括用多个哈希映射把一个节点的状态“投影”到一个二进制向量上。插入时计算元素的k个哈希值把位数组中对应位置置为1查询时同样计算k个哈希值如果所有位都是1就认为元素可能存在。这里面有数学上的美妙之处通过调整位数组长度m和哈希函数个数k可以在极小误判率下把空间压缩到集合的几十分之一。误判率公式是P ≈ (1 - e^(-k*n/m))^k其中n是插入元素数。比如你有1000万个URL想控制误判率在1%只需要大概这个公式反推出需要的m约为一个很短的范围实际算下来只需要12MB左右的空间。而用真正的set存储内存轻松超过2GB。下面是一个最精简的布隆过滤器实现方便你理解核心逻辑import math import mmh3 # 非内置库可pip install mmh3 class BloomFilter: def __init__(self, expected_items, false_positive_rate0.01): # 根据公式计算位数组长度 self.m int(-(expected_items * math.log(false_positive_rate)) / (math.log(2) ** 2)) # 计算最佳哈希函数个数 self.k int((self.m / expected_items) * math.log(2)) self.bit_array bytearray(self.m // 8 1) def _hash(self, item, seed): # 用不同的种子生成不同的哈希 return mmh3.hash(item, seed) % self.m def add(self, item): for i in range(self.k): pos self._hash(item, i) self.bit_array[pos // 8] | (1 (pos % 8)) def contains(self, item): for i in range(self.k): pos self._hash(item, i) if not (self.bit_array[pos // 8] (1 (pos % 8))): return False return True # “可能存在”工程上你可以直接用Scrapy自带的RFPDupeFilter或者用Redis的BloomFilter插件比如pybloom_live来做分布式去重。图论给的启发是你不需要绝对精确的“访问过”判断只需要一个足够可信的判断代价是牺牲极低概率的重复抓取。这在场景中完全可以接受——最多浪费一个请求不会影响最终的覆盖正确性。3.3 去处“不可能”的精确判断判重与归档分离实际爬虫我建议采用“两级判重”策略。第一级用布隆过滤器做快速判断能过滤掉99%以上的重复URL如果真的有误判第二级用Redis里的短存Set或数据库UNIQUE索引做兜底保证数据不重复入库。这样做既获得布的省内存优势又不牺牲数据精确性。有一个坑布隆过滤器不支持删除。如果你会有大量URL失效需要定期重建过滤器否则误判率会随时间上涨。遇到过一哥们把多轮任务都挂在同一个BloomFilter实例上跑了一个月后新链接全被判成已访问就是这个原因。4. 有向图的“流量分布”PageRank与调度优先级4.1 链接就是投票邻接矩阵与迭代收敛图论的另一个和爬虫强相关的经典算法是PageRank。最早用来给搜索引擎排序但做爬虫调度一样用得上你需要在一次大规模抓取中优先抓哪些页面。核心思想是“链接即投票”——一个被大量页面链接的页面应当被认为是重要的被重要页面链接的页面重要程度也会传递。数学上整个站点对应一个有向图的邻接矩阵MM[i][j]表示节点j是否有一条指向节点i的边或占比。每个页面把当前的“重要值”按出边数量均分给下游页面然后不断迭代直到每个页面的重要值收敛到一个稳定值。这个迭代过程就是一个马尔可夫链的平稳分布当随机游走者随着链接不断跳转落在某个页面上的概率就是这个页面的PageRank。公式长这样PR(A) (1-d)/N d * Σ(PR(Ti) / C(Ti))其中d是阻尼系数一般取0.85Ti是所有指向A的页面C(Ti)是页面Ti的出链数量。之所以要加(1-d)是考虑到用户不可能一直沿着链接跳转有一定概率会直接输入新网址从数学上保证迭代矩阵不可约、最终收敛。4.2 在爬虫里怎么真实用上PageRank很多人觉得PageRank是搜索引擎时代的东西爬虫里用不到。其实恰恰相反只要涉及“大规模非匀速抓取”它就非常有用。举一个我经历过的例子一个资讯站点大概有500万篇文章首页和栏目页只占1%但它们的PageRank占了全站总权重的60%以上。如果平铺直叙地按BFS抓首页虽然会先抓但栏目页之外的列表页权重没有区分详细信息页要排很久。如果都抓一遍当然都拿到但假如网站有反爬、每天只允许抓10万页你就必须在这10万里尽量选重要的。最简单的接入方式在上一轮抓取结束后用所有URL和链接关系离线算一轮PageRank得到每个URL的权重值存进Redis。下一轮抓取时把权重值映射成ScrapyRequest的priority。Scrapy调度器是有优先级的队列会优先调度数值大的请求。我实测下来同样的10万抓取配额按PageRank优先抓到的页面在“重要度总和”上是普通BFS的2.5倍以上。小站点不用配这玩意但是几百万页以上时价值极大。提供一段简化代码说明怎么把权重转成优先级import redis r redis.Redis() def get_page_priority(url): # 从redis里读取预先计算好的PageRank值 pr r.zscore(pagerank_score, url) if pr is None: return 0 # 把PR值映射到0~100的优先级 return int(pr * 100) # 在爬虫请求里使用 for url in url_list: priority get_page_priority(url) yield scrapy.Request(urlurl, callbackself.parse_detail, prioritypriority)4.3 避坑悬空节点和采权泄露图论里有个专门描述“没有出链的节点”的词叫悬空节点在PageRank计算中它会“吃掉”整个网络的重要值而不吐出来导致迭代不收敛。工程上有几种处理办法一是把所有悬空节点统一视作对每个页面都出链二是在每个页面随机跳转的概率里把悬空节点包含进去。写代码时记得在算PR前把站点内所有HTML页面都提取成节点包括那些没有外链的图片页、下载页。我见过有人只抓了内容页丢掉了导航链结果算出的PR全部集中在几个入口页调度权重基本失效。5. 链接构成的依赖关系拓扑排序与抓取顺序优化5.1 把站点抽象成有向无环图除了页面平铺的遍历很多站点本身还有很强的层级依赖关系。比如一个电商网站必须先抓取“商品分类页”才能拿到该分类下的“品牌列表页”必须抓“品牌列表页”才能拿到“商品详情页”的URL而详情页里可能又包含“评价列表页”。这种情况下页面之间存在先后顺序而不是可以任意乱序抓取的。数学上站点内部导航往往构成一个有向无环图DAG。处理DAG上节点访问顺序的经典工具就是拓扑排序——找到这样一个线性顺序对于任意一条有向边U - V在这个顺序中U都排在V之前。这样你就能保证在抓详情页之前列表页已经被解析过了。5.2 用拓扑排序实现分层抓取实际工程中我不太可能把每个站点的所有页面依赖画得那么完整。但可以近似实现在首次“结构探测”阶段解析首页得到所有栏目页URL再解析部分栏目页得到列表页URL再解析列表页样本得到详情页URL。然后把这些URL按“层级”分类每一层作为一批按批次抓取下一批次只从上一批已抓到的内容中解析新URL。这不是严格意义的全量拓扑排序更像“按依赖层分级”。但当站点的导航关系比较规整时这种分层抓取能显著减少无效请求。比如你先抓完所有栏目页再统一抓列表页最后抓详情页可以极大降低详情页还没生成完就抓取的重复情况。更严谨的做法是你自己构建一个任务依赖图然后跑一套拓扑排序输出每层的节点列表。这里有一段简化的拓扑排序示例可以用来排URL任务from collections import deque def topo_sort(dep_graph): # dep_graph: dict, {page: [依赖此page的页面列表]} in_degree {u: 0 for u in dep_graph} for u in dep_graph: for v in dep_graph[u]: in_degree[v] in_degree.get(v, 0) 1 q deque([u for u in dep_graph if in_degree[u] 0]) order [] while q: u q.popleft() order.append(u) for v in dep_graph[u]: in_degree[v] - 1 if in_degree[v] 0: q.append(v) if len(order) ! len(dep_graph): print(图中存在环不能完成拓扑排序) return order在站点没有环的假设下这个顺序是合法的。但真实站点经常会有“A页面链到B页面B页面又链回A页面”的相互引用比如面包屑导航、侧边栏推荐。这类环并不会真正阻断爬虫因为我们的“节点访问过”记录会避免重复入队。拓扑排序真正适合的场景是那些有明确抓取链路的API接口或由配置文件驱动的采集任务。5.3 工程边界不是所有环都要消灭使用拓扑排序时要注意一个边界页面间环太多了纯拓扑排序会退化。如果你把每个HTML页面都作为节点把页面上所有超链接都作为边几乎任何一个商业化站点都会因为“分类页 - 详情页推荐位”这种结构形成海量的环拓扑排序就名存实亡了。我自己的做法是只在“URL模式层面”做层级分类根据URL规则比如/category/、/list/、/detail/而不是实际的链接关系来确定层级顺序。图论给你是思维模型不是死板工具到工程里往往要结合实际URL特征做降维。6. 图论视角下爬虫的常见难题与排查6.1 环、“蜘蛛陷阱”与无穷图爬虫最常见的故障就是陷入某种无限循环。从图论角度解释就是遍历在一个“有环但节点数无穷”的图上进行而且环上每个节点都在持续产生新的未访问节点比如动态生成的日历链接、排序参数不同的URL、sessionID。这是因为这些URL虽然文本不同但实际对应同一种资源图的节点规模被人为放大成无穷。对策也源自图论思路给遍历加上步数或深度限制相当于在无穷图上规定一个“搜索半径”。另一个是URL规范化把?page1与?page2这种可以通过参数处理归一的先归一化再入队。更实用的是对域名、目录、文件类型做白名单。我有一个专门抓新闻的老爬虫主要崩溃原因就是侧边栏“热门推荐”模块生成了无数个带时间戳的推荐列表URL后来加了深度限制为3才彻底压住。6.2 不连通子图与种子节点的选择图不连通在爬虫里太常见了。有的站点根目录下没有任何链接能指向某些古老的旧版页面只有直接输入URL才能访问某些页面只通过站内搜索入口展示没有静态导航链接。当你只从一个种子URL开始抓时永远发现不了这些孤岛。图论给的方案很直接要遍历整个图需要多个起始节点形成“种子集合”。在爬虫中这意味着不能只填首页URL。我自己做多轮抓取时会把上一轮搜集到的高价值外链、sitemap里的URL、Google Site查询中的URL全部混成种子集。有一回一个只有首页种子爬完只能覆盖站点25%的内容加了sitemap URL后直接覆盖到87%剩余那些就是典型的“不可通过链接到达”的页面。6.3 常见问题速查表现象图论原因解决建议爬虫在某个分支内疯狂抓取新URL图中存在无限节点分支设置最大深度/最大请求数规范URL参数大量重复请求数据库大量重复记录布隆过滤器误判率升高或未启用去重扩容位数组定期重建过滤器增加数据库唯一约束重要页面很晚才被抓到BFS权重未考虑页面重要性引入PageRank或人工权重调整调度优先级部分页面永远抓不到图不连通种子无法到达孤立子图增加多源头种子解析sitemap和站点地图抓取顺序混乱模块数据不完整忽略页面之间的依赖关系使用拓扑排序/分层抓取按依赖分批处理程序内存涨到崩溃已访问URL集合过大从set换成布隆过滤器或使用Redis分片去重计算PageRank迭代不收敛存在大量悬空节点对悬空节点做统一出链处理增加随机跳转概率6.4 调试技巧把爬虫画出来每当我遇到看不懂的抓取问题第一步不是打日志而是抽一小批URL把它们的链接关系可视化。可以用networkx构建图再导出成GraphML或GEXF格式扔进Gephi或者直接matplotlib画出来。可视化后哪里存在环、哪里出现了孤岛、哪类URL形成了密集子图一目了然。import networkx as nx G nx.DiGraph() # 假设edges是[(from_url, to_url), ...] G.add_edges_from(edges) print(节点数:, G.number_of_nodes()) print(边数:, G.number_of_edges()) print(弱连通分量数:, nx.number_weakly_connected_components(G)) # 找环 cycles list(nx.simple_cycles(G)) print(环数量:, len(cycles))这个“画图查图”的思路帮过我很多次。有一回一个爬虫任务彻底卡死拍脑子猜了好多原因最后画了500个URL的图发现是一个分类页面里有个指向根目录的“回到首页”链接和首页的“分类页”入口形成了一个巨大环同时该分类页本身又能无限翻页。虽然访问记录能阻止死循环但由于翻页URL是逐个生成的图的规模被无限扩大导致队列一直有元素。7. 图论不是工具箱而是思考方式图论对爬虫的价值不光是给了你BFS、DFS、拓扑排序这些现成算法更重要的是帮你建立一种抽象能力。面对一个杂乱无章的真实站点你能在5分钟内把它还原成“节点、边、有向、无环、权重、连通性”这些结构化概念然后就能自然地想到对应解法。以前的我把爬虫当成“发请求解析HTML”的重复劳动后来才意识到爬虫的很多核心难点——调度、去重、优先级、依赖、收敛性——本质上都是图的问题。我在实际项目中有一个习惯每次拿到一个新目标站先不写代码拿本子画一张图。画节点、画链接、标注哪些页面可以并行抓、哪些页面必须等前置数据。这张草图可能就是几十秒的事但它决定了后面整个抓取模型怎么设计。图论在这里不是公式更像一个思维框架它让你看到无序的背后有一种结构而结构就是可以优化的地方。最后再分享一个小技巧如果你能给爬虫里所有请求的URL设计一个稳定的“图节点ID”比如按域名路径参数排序后的哈希值你会发现去重、入库、调度全都能复用同一个编号体系整个系统会清晰很多。多从图的角度看问题少踩的坑可能比你多写一万行代码还要值。