爬虫的广度优先和深度优先算法

广度优先算法介绍

整个的广度优先爬虫过程就是从一系列的种子节点开始，把这些网页中的”子节点”(也就是超链接)提取出来，放入队列中依次进行抓取。被处理过的链接需要放入一张表(通常称为Visited表)中。每次新处理一个链接之前，需要查看这个链接是否已经存在于Visited表中。如果存在，证明链接已经处理过，跳过，不做处理，否则进行下一步处理。

初始的URL地址是爬虫系统中提供的种子URL(一般在系统的配置文件中指定)。当解析这些种子URL所表示的网页时，会产生新的URL(比如从页面中的<a href= ”

http://www.admin.com

“中提取出

http://www.admin.com

这个链接)。然后，进行以下工作：

把解析出的链接和Visited表中的链接进行比较，若Visited表中不存在此链接，表示其未被访问过。
把链接放入TODO表中。
处理完毕后，再次从TODO表中取得一条链接，直接放入Visited表中。
针对这个链接所表示的网页，继续上述过程。如此循环往复。

广度优先遍历是爬虫中使用最广泛的一种爬虫策略，之所以使用广度优先搜索策略，主要原因有三点：

重要的网页往往离种子比较近，例如我们打开新闻网站的时候往往是最热门的新闻，随着不断的深入冲浪，所看到的网页的重要性越来越低。
万维网的实际深度最多能达到17层，但到达某个网页总存在一条很短的路径。而广度优先遍历会以最快的速度到达这个网页。
广度优先有利于多爬虫的合作抓取，多爬虫合作通常先抓取站内链接，抓取的封闭性很强。

爬虫深度优先搜索

深度优先搜索是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML文件) 。在一个HTML文件中，当一个超链被选择后，被链接的HTML文件将执行深度优先搜索，即在搜索其余的超链结果之前必须先完整地搜索单独的一条链。深度优先搜索沿着HTML文件上的超链走到不能再深入为止，然后返回到某一个HTML文件，再继续选择该HTML文件中的其他超链。当不再有其他超链可选择时，说明搜索已经结束。优点是能遍历一个Web 站点或深层嵌套的文档集合；缺点是因为Web结构相当深,，有可能造成一旦进去，再也出不来的情况发生。

  1 #encoding=utf-8
  2 from bs4 import BeautifulSoup
  3 import socket
  4 import urllib2
  5 import re
  6 import zlib
  7  
  8  class MyCrawler:
  9      def __init__(self,seeds):
 10          #初始化当前抓取的深度
 11          self.current_deepth = 1
 12          #使用种子初始化url队列
 13          self.linkQuence=linkQuence()
 14          if isinstance(seeds,str):
 15              self.linkQuence.addUnvisitedUrl(seeds)
 16          if isinstance(seeds,list):
 17              for i in seeds:
 18                  self.linkQuence.addUnvisitedUrl(i)
 19          print "Add the seeds url \"%s\" to the unvisited url list"%str(self.linkQuence.unVisited)
 20      #抓取过程主函数
 21      def crawling(self,seeds,crawl_deepth):
 22          #循环条件：抓取深度不超过crawl_deepth
 23          while self.current_deepth <= crawl_deepth:
 24              #循环条件：待抓取的链接不空
 25              while not self.linkQuence.unVisitedUrlsEnmpy():
 26                  #队头url出队列
 27                  visitUrl=self.linkQuence.unVisitedUrlDeQuence()
 28                  print "Pop out one url \"%s\" from unvisited url list"%visitUrl
 29                  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 in links:
 40                  self.linkQuence.addUnvisitedUrl(link)
 41              print "%d unvisited links:"%len(self.linkQuence.getUnvisitedUrl())
 42              self.current_deepth += 1
 43              
 44      #获取源码中得超链接
 45      def getHyperLinks(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":re.compile('^http|^/')})
 51              for i in a:
 52                  if i["href"].find("http://")!=-1:
 53                      links.append(i["href"]) 
 54          return links
 55      
 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 is None:   
 68                  coding= response.headers.getparam("charset")   
 69         　　#如果获取的网站编码为None 
 70              if coding is None:   
 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          except Exception,e:
 78              print str(e)
 79              return [str(e),None]
 80          
 81  class linkQuence:
 82      def __init__(self):
 83          #已访问的url集合
 84          self.visted=[]
 85          #待访问的url集合
 86          self.unVisited=[]
 87      #获取访问过的url队列
 88      def getVisitedUrl(self):
 89          return self.visted
 90      #获取未访问的url队列
 91      def getUnvisitedUrl(self):
 92          return self.unVisited
 93      #添加到访问过得url队列中
 94      def addVisitedUrl(self,url):
 95          self.visted.append(url)
 96      #移除访问过得url
 97      def removeVisitedUrl(self,url):
 98          self.visted.remove(url)
 99      #未访问过得url出队列
100      def unVisitedUrlDeQuence(self):
101          try:
102              return self.unVisited.pop()
103          except:
104              return None
105      #保证每个url只被访问一次
106      def addUnvisitedUrl(self,url):
107          if url!="" and url not in self.visted and url not in self.unVisited:
108              self.unVisited.insert(0,url)
109      #获得已访问的url数目
110      def getVisitedUrlCount(self):
111          return len(self.visted)
112      #获得未访问的url数目
113      def getUnvistedUrlCount(self):
114          return len(self.unVisited)
115      #判断未访问的url队列是否为空
116      def unVisitedUrlsEnmpy(self):
117          return len(self.unVisited)==0
118      
119  def main(seeds,crawl_deepth):
120      craw=MyCrawler(seeds)
121      craw.crawling(seeds,crawl_deepth)
122      
123  if __name__=="__main__":
124      main(["http://www.baidu.com", "http://www.google.com.hk", "http://www.sina.com.cn"],10)

转载于:https://www.cnblogs.com/wangshuyi/p/6734523.html

你可能也喜欢