Cracking the coding interview--Q12.5

January 31, 2013
作者:Hawstein
出处:http://hawstein.com/posts/12.5.html
声明:本文采用以下协议进行授权: 自由转载-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0 ,转载请注明作者及出处。

题目

原文:

If you were designing a web crawler, how would you avoid getting into infinite loops?

译文:

如果让你设计一个网络爬虫,你怎么避免陷入无限循环?

解答

看完这题,建议用python写个爬虫,对此就能理解的多一些,而且还可以做出好玩的东西。

话说爬虫为什么会陷入循环呢?答案很简单,当我们重新去解析一个已经解析过的网页时, 就会陷入无限循环。这意味着我们会重新访问那个网页的所有链接, 然后不久后又会访问到这个网页。最简单的例子就是,网页A包含了网页B的链接, 而网页B又包含了网页A的链接,那它们之间就会形成一个闭环。

那么我们怎样防止访问已经访问过的页面呢,答案也很简单,设置一个标志即可。 整个互联网就是一个图结构,我们通常使用DFS(深度优先搜索)和BFS(广度优先搜索) 进行遍历。所以,像遍历一个简单的图一样,将访问过的结点标记一下即可。

全书题解目录:

Cracking the coding interview–问题与解答

全书的C++代码托管在Github上:

https://github.com/Hawstein/cracking-the-coding-interview