第 9 章 图论和网络爬虫

图论中的遍历算法

图论中的图由一些节点和连接这些节点的弧组成。顺着弧把所有的节点都走一遍，记录访问过的节点，同时避免多次访问或漏掉某个节点，该方法叫做遍历。

常见遍历算法：

• 广度优先（BFS-尽可能广得访问每一个节点所直接连接的其他节点）。

• 深度优先（DFS-从头一路走到黑）。

简单来说，BFS就是先搜索每个节点直接相连的其他节点，DFS就是顺着一个节点的相连的节点走到底，再返回上一层继续相同操作。

网络爬虫

有了超链接，我们可以利用遍历算法，自动地访问每一个网页，并把它们存起来。完成该功能的程序即网络爬虫。

图论定理

如果一个图能够从一个顶点出发，每条边不重复地遍历一遍回到这个顶点，那么每个顶点的度必须为偶数。（若想回到顶点，则有多少出去的边，就要有多少进入的边）。

构建网络爬虫的工程要点

1. 采用BFS还是DFS？即如何在有限的时间里最多地爬下最重要的网页。

对于某个网站来说，首页最重要，其次是首页的链接，链接越深越相对不重要。所以，在下载某一个互联网的具体内容时，BFS优先于DFS。

但是，在网路通信的握手成本上，DFS优先于BFS。“握手”就是指下载服务器网站和网站服务器建立通信的过程。如果握手的次数太多，下载的效率就降低。对于某个网站，一般是由特定的一台或几台服务器专门下载。这些服务器下载完一个网站，再去下载另一个网站，而不是先下载一部分，再来回折腾。

所以，同时存在DFS、BFS。有一个调度系统来存储那些已经发现但尚未下载的网页URL，且按优先级排列，因此，在爬虫中，BFS的成分多一点。

2. 页面的分析和URL的提取

• 以 HTML 语言书写的网页，解析起来比较简单。

• 以脚本 JS 等书写网页，解析起来较为困难，需要做浏览器的内核工程师来做。

3. 记录哪些网页URL已经下载过——URL表（哈希表）

为了防止一个网页被多次下载，需要在一个哈希表中记录哪些网页已经下载过。判断一个网页的URL是否在表中，平均只需要一次（或者略多的）查找。

如果同时有上千台服务器一起下载网页，维护一张统一的哈希表就比较麻烦。首先，哈希表会大到一台服务器存储不下，其次由于每个下载服务器在开始下载前和完成下载后都需要访问和维护这张表，以免不同的服务器重复工作，存储这张哈希表的服务器的通信就成为了整个爬虫系统的瓶颈。

好的方法一般采用两个技术：首先明确每台服务器的分工，也就是在调度时一看到某个URL就知道要交给哪台服务器去下载，这样就避免了很多服务器对同一个URL做出是否要下载的判断。然后，在明确分工的基础上，可以批量判断URL是否下载，比如每次向哈希表发送一大批询问，或者每次更新一大批哈希表的内容，以减少通信的次数。

小结

很多数学方法就是这样，看上去没什么实际用途，但随着事件的推移会一下子排上大用场。