1、3.2.1 复杂的复杂的Web网站网站深度优先与广度优先方法都是遍历树的一种方法，但是网站的各个网页之间的关系未必是树的结构，它们可能组成一个复杂的图形结构，即有回路。如果在前面的网站中每个网页都加一条Home的语句，让每个网页都能回到主界面，那么网站的关系就是一个有回路的图(1)books.htm计算机数据库程序设计计算机网络(2)database.htm数据库MySQL数据库Home(3)program.htm程序设计Python程序设计Java程序设计Home(4)network.htm计算机网络Home(5)mysql.htmMySQL数据库Home(6)python.htmPytho
2、n程序设计Home(7)java.htmJava程序设计Home 3.2.2 改进深度优先客户端程序改进深度优先客户端程序假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点)，则深度优先遍历可定义如下：首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。图的深度优先遍历类似于树的前序遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-First Search)。相
3、应地，用此方法遍历图就很自然地称之为图的深度优先遍历，基本实现思想：（1）访问顶点v；（2）从v的未被访问的邻接点中选取一个顶点w，从w出发进行深度优先遍历；（3）重复上述两步，直至图中所有和v有路径相通的顶点都被访问到。1、使用递归的程序：、使用递归的程序：from bs4 import BeautifulSoupimport urllib.request def spider(url):global urls if url not in urls:urls.append(url)try:data=urllib.request.urlopen(url)data=data.read()data
4、=data.decode()soup=BeautifulSoup(data,lxml)print(soup.find(h3).text)links=soup.select(a)for link in links:href=linkhref url=start_url+/+href spider(url)except Exception as err:print(err)start_url=http:/127.0.0.1:5000urls=spider(start_url)print(The End)2、使用栈的程序、使用栈的程序from bs4 import BeautifulSoupimpo
5、rt urllib.request class Stack:def _init_(self):self.st=def pop(self):return self.st.pop()def push(self,obj):self.st.append(obj)def empty(self):return len(self.st)=0 def spider(url):global urls stack=Stack()stack.push(url)while not stack.empty():url=stack.pop()if url not in urls:urls.append(url)try:d
6、ata=urllib.request.urlopen(url)data=data.read()data=data.decode()soup=BeautifulSoup(data,lxml)print(soup.find(h3).text)links=soup.select(a)for i in range(len(links)-1,-1,-1):href=linksihref url=start_url+/+href stack.push(url)except Exception as err:print(err)start_url=http:/127.0.0.1:5000urls=spide
7、r(start_url)print(The End)这两个程序的结果都一样：计算机数据库MySQL数据库计算机程序设计Python程序设计Java程序设计计算机网络The End 3.2.2 改进深度优先客户端程序改进深度优先客户端程序3.2.2 改进深度优先客户端程序改进深度优先客户端程序假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点)，则深度优先遍历可定义如下：首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已
8、被访问为止。图的深度优先遍历类似于树的前序遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-First Search)。相应地，用此方法遍历图就很自然地称之为图的深度优先遍历，基本实现思想：（1）访问顶点v；（2）从v的未被访问的邻接点中选取一个顶点w，从w出发进行深度优先遍历；（3）重复上述两步，直至图中所有和v有路径相通的顶点都被访问到。1、使用递归的程序：、使用递归的程序：from bs4 import BeautifulSoupimport urllib.request def spider(url):global urls if url
9、 not in urls: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)for link in links:href=linkhref url=start_url+/+href spider(url)except Exception as err:print(err)start_url=http:/127.0.0.1:500
10、0urls=spider(start_url)print(The End)2、使用栈的程序、使用栈的程序from bs4 import BeautifulSoupimport urllib.request class Stack:def _init_(self):self.st=def pop(self):return self.st.pop()def push(self,obj):self.st.append(obj)def empty(self):return len(self.st)=0 def spider(url):global urls stack=Stack()stack.pus
11、h(url)while not stack.empty():url=stack.pop()if url not in urls: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)for i in range(len(links)-1,-1,-1):href=linksihref url=start_url+/+href stac
12、k.push(url)except Exception as err:print(err)start_url=http:/127.0.0.1:5000urls=spider(start_url)print(The End)这两个程序的结果都一样：计算机数据库MySQL数据库计算机程序设计Python程序设计Java程序设计计算机网络The End 3.2.3改进广度优先客户端程序改进广度优先客户端程序3.2.3改进广度优先客户端程序改进广度优先客户端程序图的广度优先遍历BFS算法是一个分层搜索的过程，和树的层序遍历算法类同，它也需要一个队列以保持遍历过的顶点顺序，以便按出队的顺序再去访问这些顶
13、点的邻接顶点。基本实现思想：（1）顶点v入队列。（2）当队列非空时则继续执行，否则算法结束。（3）出队列取得队头顶点v；访问顶点v并标记顶点v已被访问。（4）查找顶点v的第一个邻接顶点col。（5）若v的邻接顶点col未被访问过的，则col入队列。（6）继续查找顶点v的另一个新的邻接顶点col，转到步骤（5）。直到顶点v的所有未被访问过的邻接点处理完。转到步骤（2）。广度优先遍历图是以顶点v为起始点，由近至远，依次访问和v有路径相通而且路径长度为1，2，的顶点。为了使“先被访问顶点的邻接点”先于“后被访问顶点的邻接点”被访问，需设置队列存储访问的顶点。from bs4 import Beaut
14、ifulSoupimport urllib.request class Queue:def _init_(self):self.st=def fetch(self):return self.st.pop(0)def enter(self,obj):self.st.append(obj)def empty(self):return len(self.st)=0def spider(url):global urls queue=Queue()queue.enter(url)while not queue.empty():url=queue.fetch()if url not in urls:try
15、:urls.append(url)data=urllib.request.urlopen(url)data=data.read()data=data.decode()soup=BeautifulSoup(data,lxml)print(soup.find(h3).text)links=soup.select(a)for link in links:href=linkhref url=start_url+/+href queue.enter(url)except Exception as err:print(err)start_url=http:/127.0.0.1:5000urls=spider(start_url)print(The End)程序结果：计算机数据库程序设计计算机网络MySQL数据库计算机Python程序设计Java程序设计The End
