【文档说明】Python爬虫程序设计KC32.pptx，共(24)页，76.035 KB，由小橙橙上传

转载请保留链接：https://www.ichengzhen.cn/view-2417.html

以下为本文档部分文字说明：

3.2.1复杂的Web网站深度优先与广度优先方法都是遍历树的一种方法，但是网站的各个网页之间的关系未必是树的结构，它们可能组成一个复杂的图形结构，即有回路。如果在前面的网站中每个网页都加一条<ahref="books.htm">Home</

a>的语句，让每个网页都能回到主界面，那么网站的关系就是一个有回路的图(1)books.htm<h3>计算机</h3><ul><li><ahref="database.htm">数据库</a></li><li><

ahref="program.htm">程序设计</a></li><li><ahref="network.htm">计算机网络</a></li></ul>(2)database.htm<h3>数据库</h3><ul><li><ahref="my

sql.htm">MySQL数据库</a></li></ul><ahref="books.htm">Home</a>(3)program.htm<h3>程序设计</h3><ul><li><ahref="python.htm">Python程序设计</a></li><li>

<ahref="java.htm">Java程序设计</a></li></ul><ahref="books.htm">Home</a>(4)network.htm<h3>计算机网络</h3><ahref="books.

htm">Home</a>(5)mysql.htm<h3>MySQL数据库</h3><ahref="books.htm">Home</a>(6)python.htm<h3>Python程序设计</h3><ahref="books.htm">Home<

/a>(7)java.htm<h3>Java程序设计</h3><ahref="books.htm">Home</a>3.2.2改进深度优先客户端程序假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点)，则深度优先遍历可定义如下：首先访问出发点v，并将其标记为已

访问过；然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。图的深度优先遍历类似于树的前序遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优

先搜索(Depth-FirstSearch)。相应地，用此方法遍历图就很自然地称之为图的深度优先遍历，基本实现思想：（1）访问顶点v；（2）从v的未被访问的邻接点中选取一个顶点w，从w出发进行深度优先遍

历；（3）重复上述两步，直至图中所有和v有路径相通的顶点都被访问到。1、使用递归的程序：frombs4importBeautifulSoupimporturllib.requestdefspider(url):globalurlsifurlnotinurls:urls.appen

d(url)try:data=urllib.request.urlopen(url)data=data.read()data=data.decode()soup=BeautifulSoup(data,"lxml")print(soup.find("h3").text)lin

ks=soup.select("a")forlinkinlinks:href=link["href"]url=start_url+"/"+hrefspider(url)exceptExceptionaserr:print(err

)start_url="http://127.0.0.1:5000"urls=[]spider(start_url)print("TheEnd")2、使用栈的程序frombs4importBeautifulSoupimporturllib.requestclassStack:def_

_init__(self):self.st=[]defpop(self):returnself.st.pop()defpush(self,obj):self.st.append(obj)defempty(self):returnlen(self.st)==0defspid

er(url):globalurlsstack=Stack()stack.push(url)whilenotstack.empty():url=stack.pop()ifurlnotinurls:urls.append(url)try:da

ta=urllib.request.urlopen(url)data=data.read()data=data.decode()soup=BeautifulSoup(data,"lxml")print(soup.find("h3").text)links=soup.select("a

")foriinrange(len(links)-1,-1,-1):href=links[i]["href"]url=start_url+"/"+hrefstack.push(url)exceptExceptionaserr:print(err)start_url="ht

tp://127.0.0.1:5000"urls=[]spider(start_url)print("TheEnd")这两个程序的结果都一样：计算机数据库MySQL数据库计算机程序设计Python程序设计J

ava程序设计计算机网络TheEnd3.2.2改进深度优先客户端程序3.2.2改进深度优先客户端程序假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点)，则深度优先遍历可定义如下

：首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。图的深度优先遍历类似于

树的前序遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-FirstSearch)。相应地，用此方法遍历图就很自然地称之为图的深度优先遍历，基本实现思想：（1）访问顶

点v；（2）从v的未被访问的邻接点中选取一个顶点w，从w出发进行深度优先遍历；（3）重复上述两步，直至图中所有和v有路径相通的顶点都被访问到。1、使用递归的程序：frombs4importBeautifulSoupimporturllib.requestdefspider

(url):globalurlsifurlnotinurls:urls.append(url)try:data=urllib.request.urlopen(url)data=data.read()data=data.decode

()soup=BeautifulSoup(data,"lxml")print(soup.find("h3").text)links=soup.select("a")forlinkinlinks:href=link["href"]url=start_url+"/"+hr

efspider(url)exceptExceptionaserr:print(err)start_url="http://127.0.0.1:5000"urls=[]spider(start_url)print("TheEnd")2、使用栈的程序frombs4impo

rtBeautifulSoupimporturllib.requestclassStack:def__init__(self):self.st=[]defpop(self):returnself.st.pop()defpush(se

lf,obj):self.st.append(obj)defempty(self):returnlen(self.st)==0defspider(url):globalurlsstack=Stack()stack.push(url)whilenotstack.empty():url=stack.p

op()ifurlnotinurls:urls.append(url)try:data=urllib.request.urlopen(url)data=data.read()data=data.decode()s

oup=BeautifulSoup(data,"lxml")print(soup.find("h3").text)links=soup.select("a")foriinrange(len(links

)-1,-1,-1):href=links[i]["href"]url=start_url+"/"+hrefstack.push(url)exceptExceptionaserr:print(err)

start_url="http://127.0.0.1:5000"urls=[]spider(start_url)print("TheEnd")这两个程序的结果都一样：计算机数据库MySQL数据库计算机程序设计Pytho

n程序设计Java程序设计计算机网络TheEnd3.2.3改进广度优先客户端程序3.2.3改进广度优先客户端程序图的广度优先遍历BFS算法是一个分层搜索的过程，和树的层序遍历算法类同，它也需要一个队列以保持遍历过的顶点顺序，以便按出队的顺序再去访问这些顶点的邻接顶点。基本实现思想

：（1）顶点v入队列。（2）当队列非空时则继续执行，否则算法结束。（3）出队列取得队头顶点v；访问顶点v并标记顶点v已被访问。（4）查找顶点v的第一个邻接顶点col。（5）若v的邻接顶点col未被访问过的，则col入队列。（6）继续查找顶点v的另一个新的邻接顶点col，转到步骤（

5）。直到顶点v的所有未被访问过的邻接点处理完。转到步骤（2）。广度优先遍历图是以顶点v为起始点，由近至远，依次访问和v有路径相通而且路径长度为1，2，……的顶点。为了使“先被访问顶点的邻接点”先于“后被访问顶点的邻接点”被访问，需设置队列存储访问的顶点。

frombs4importBeautifulSoupimporturllib.requestclassQueue:def__init__(self):self.st=[]deffetch(self):

returnself.st.pop(0)defenter(self,obj):self.st.append(obj)defempty(self):returnlen(self.st)==0defspider(url):globalurlsqueue=Queue()queue

.enter(url)whilenotqueue.empty():url=queue.fetch()ifurlnotinurls:try:urls.append(url)data=urllib.request.urlopen(url)da

ta=data.read()data=data.decode()soup=BeautifulSoup(data,"lxml")print(soup.find("h3").text)links=soup.select("a")forlinkinlinks:href=link["href"]url=s

tart_url+"/"+hrefqueue.enter(url)exceptExceptionaserr:print(err)start_url="http://127.0.0.1:5000"urls=[

]spider(start_url)print("TheEnd")程序结果：计算机数据库程序设计计算机网络MySQL数据库计算机Python程序设计Java程序设计TheEnd