离散数学 是当代数学的一个重要分支，也是计算机科学的数学基础。它包括数 理逻辑、集合论、图论和近世代数四个分支。数理逻辑基于布尔运算，我们已经 介绍过了。这里我们介绍图论和互联网自动下载工具网络爬虫 (Web Crawlers) 之间的关系。顺便提一句，我们用 Google Trends 来搜索一下“离散数学”这 个词，可以发现不少有趣的现象。比如，武汉、哈尔滨、合肥和长沙市对这一数 学题目最有兴趣的城市。]

我们 上回 谈到了如何建立搜索引擎的索引，那么如何自动下载互联网所有的网页 呢，它要用到图论中的遍历（Traverse) 算法。

图论的起源可追溯到大数学家 欧拉 （Leonhard Euler）。1736 年欧拉来到德国 的哥尼斯堡（Konigsberg，大哲学家康德的故乡，现在是俄罗斯的加里宁格勒）， 发现当地市民们有一项消遣活动，就是试图将下图中的 每座桥恰好走过一遍并 回到原出发点，从来没有人成功过。欧拉证明了这件事是不可能的，并写了一篇 论文，一般认为这是图论的开始。

图 论中所讨论的的图由一些节点和连接这些节点的弧组成。如果我们把中国的 城市当成节点，连接城市的国道当成弧，那么全国的公路干线网就是图论中所说 的图。关 于图的算法有很多，但最重要的是图的遍历算法，也就是如何通过弧 访问图的各个节点。以中国公路网为例，我们从北京出发，看一看北京和哪些城 市直接相连，比 如说和天津、济南、石家庄、南京、沈阳、大同直接相连。我 们可以依次访问这些城市，然后我们看看都有哪些城市和这些已经访问过的城市 相连，比如说北戴河、 秦皇岛与天津相连，青岛、烟台和济南相连，太原、郑 州和石家庄相连等等，我们再一次访问北戴河这些城市，直到中国所有的城市都访问过一遍为止。这种图的遍 历算法称为“广度优先算法”（BFS)，因为它先 要尽可能广地访问每个节点所直接连接的其他节点。另外还有一种策略是从北京 出发，随便找到下一个要访问的 城市，比如是济南，然后从济南出发到下一个 城市，比如说南京，再访问从南京出发的城市，一直走到头。然后再往回找，看 看中间是否有尚未访问的城市。这种方 法叫“深度优先算法”（DFS)，因为它 是一条路走到黑。这两种方法都可以保证访问到全部的城市。当然，不论采用哪 种方法，我们都应该用一个小本本，记录 已经访问过的城市，以防同一个城市 访问多次或者漏掉哪个城市。