广度优先算法介绍
整个的广度优先爬虫过程就是从一系列的种子节点开始，把这些网页中的"子节点"(也就是超链接)提取出来，放入队列中依次进行抓取。被处理过的链接需要放 入一张表(通常称为Visited表)中。每次新处理一个链接之前，需要查看这个链接是否已经存在于Visited表中。如果存在，证明链接已经处理过， 跳过，不做处理，否则进行下一步处理。
初始的URL地址是爬虫系统中提供的种子URL(一般在系统的配置文件中指定)。当解析这些种子URL所表示的网页时，会产生新的URL(比如从页面中的
把解析出的链接和Visited表中的链接进行比较，若Visited表中不存在此链接，表示其未被访问过。
把链接放入TODO表中。
处理完毕后，再次从TODO表中取得一条链接，直接放入Visited表中。
针对这个链接所表示的网页，继续上述过程。如此循环往复。
广度优先遍历是爬虫中使用最广泛的一种爬虫策略，之所以使用广度优先搜索策略，主要原因有三点：
重要的网页往往离种子比较近，例如我们打开新闻网站的时候往往是最热门的新闻，随着不断的深入冲浪，所看到的网页的重要性越来越低。
万维网的实际深度最多能达到17层，但到达某个网页总存在一条很短的路径。而广度优先遍历会以最快的速度到达这个网页。
广度优先有利于多爬虫的合作抓取，多爬虫合作通常先抓取站内链接，抓取的封闭性很强。
爬虫深度优先搜索
深度优先搜索是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML文件) 。在一个HTML文件中，当一个超链被选择后，被链接的HTML文件将执行深度优先搜索，即在搜索其余的超链结果之前必须先完整地搜索单独的一条链。深度优先搜索沿着HTML文件上的超链走到不能再深入为止，然后返回到某一个HTML文件，再继续选择该HTML文件中的其他超链。当不再有其他超链可选择时，说明搜索已经结束。优点是能遍历一个Web 站点或深层嵌套的文档集合；缺点是因为Web结构相当深,，有可能造成一旦进去，再也出不来的情况发生。
1 #encoding=utf-8
2 from bs4 importBeautifulSoup3 importsocket4 importurllib25 importre6 importzlib7
8 classMyCrawler:9 def __init__(self,seeds):10 #初始化当前抓取的深度
11 self.current_deepth = 1
12 #使用种子初始化url队列
13 self.linkQuence=linkQuence()14 ifisinstance(seeds,str):15 self.linkQuence.addUnvisitedUrl(seeds)16 ifisinstance(seeds,list):17 for i inseeds:18 self.linkQuence.addUnvisitedUrl(i)19 print "Add the seeds url \"%s\" to the unvisited url list"%str(self.linkQuence.unVisited)20 #抓取过程主函数
21 defcrawling(self,seeds,crawl_deepth):22 #循环条件：抓取深度不超过crawl_deepth
23 while self.current_deepth <=crawl_deepth:24 #循环条件：待抓取的链接不空
25 while notself.linkQuence.unVisitedUrlsEnmpy():26 #队头url出队列
27 visitUrl=self.linkQuence.unVisitedUrlDeQuence()28 print "Pop out one url \"%s\" from unvisited url list"%visitUrl29 if visitUrl is None or visitUrl=="":30 continue
31 #获取超链接
32 links=self.getHyperLinks(visitUrl)33 print "Get %d new links"%len(links)34 #将url放入已访问的url中
35 self.linkQuence.addVisitedUrl(visitUrl)36 print "Visited url count:"+str(self.linkQuence.getVisitedUrlCount())37 print "Visited deepth:"+str(self.current_deepth)38 #未访问的url入列
39 for link inlinks:40 self.linkQuence.addUnvisitedUrl(link)41 print "%d unvisited links:"%len(self.linkQuence.getUnvisitedUrl())42 self.current_deepth += 1
43
44 #获取源码中得超链接
45 defgetHyperLinks(self,url):46 links=[]47 data=self.getPageSource(url)48 if data[0]=="200":49 soup=BeautifulSoup(data[1])50 a=soup.findAll("a",{"href":pile('^http|^/')})51 for i ina:52 if i["href"].find("http://")!=-1:53 links.append(i["href"])54 returnlinks55
56 #获取网页源码
57 def getPageSource(self,url,timeout=100,coding=None):58 try:59 socket.setdefaulttimeout(timeout)60 req =urllib2.Request(url)61 req.add_header('User-agent', 'Mozilla/4.0 (compatible; MSIE 6.0; Windows NT 5.1)')62 response =urllib2.urlopen(req)63 page = ''
64 if response.headers.get('Content-Encoding') == 'gzip':65 page = zlib.decompress(page, 16+zlib.MAX_WBITS)66
67 if coding isNone:68 coding= response.headers.getparam("charset")69 #如果获取的网站编码为None
70 if coding isNone:71 page=response.read()72 #获取网站编码并转化为utf-8
73 else:74 page=response.read()75 page=page.decode(coding).encode('utf-8')76 return ["200",page]77 exceptException,e:78 printstr(e)79 return[str(e),None]80
81 classlinkQuence:82 def __init__(self):83 #已访问的url集合
84 self.visted=[]85 #待访问的url集合
86 self.unVisited=[]87 #获取访问过的url队列
88 defgetVisitedUrl(self):89 returnself.visted90 #获取未访问的url队列
91 defgetUnvisitedUrl(self):92 returnself.unVisited93 #添加到访问过得url队列中
94 defaddVisitedUrl(self,url):95 self.visted.append(url)96 #移除访问过得url
97 defremoveVisitedUrl(self,url):98 self.visted.remove(url)99 #未访问过得url出队列
100 defunVisitedUrlDeQuence(self):101 try:102 returnself.unVisited.pop()103 except:104 returnNone105 #保证每个url只被访问一次
106 defaddUnvisitedUrl(self,url):107 if url!="" and url not in self.visted and url not inself.unVisited:108 self.unVisited.insert(0,url)109 #获得已访问的url数目
110 defgetVisitedUrlCount(self):111 returnlen(self.visted)112 #获得未访问的url数目
113 defgetUnvistedUrlCount(self):114 returnlen(self.unVisited)115 #判断未访问的url队列是否为空
116 defunVisitedUrlsEnmpy(self):117 return len(self.unVisited)==0118
119 defmain(seeds,crawl_deepth):120 craw=MyCrawler(seeds)121 craw.crawling(seeds,crawl_deepth)122
123 if __name__=="__main__":124 main(["", ".hk", ""],10)
