网站建设原码,做网站网站推广赚佣金,wordpress表单支付,wordpress 仿优客逸家深度优先与广度优先方法都是遍历树的一种方法#xff0c;但是网站的各个网页 之间的关系未必是树的结构#xff0c;它们可能组成一个复杂的图形结构#xff0c;即有回路。如果在前面的网站中每个网页都加一条Home的语句#xff0c;让每个网页都能回到主界面#xff0c;那么…深度优先与广度优先方法都是遍历树的一种方法但是网站的各个网页 之间的关系未必是树的结构它们可能组成一个复杂的图形结构即有回路。如果在前面的网站中每个网页都加一条Home的语句让每个网页都能回到主界面那么网站的关系就是一个有回路的图。1. 复杂的 Web网站books.htmlh3计算机/h3
ullia hrefdatabase.html数据库/a/lilia hrefprogram.html程序设计/a/lilia hrefnetwork.html计算机网络/a/li
/uldatabase.htmlh3数据库/h3
ullia hrefmysql.htmlMySQL数据库/a/li
/ul
a hrefbooks.htmlHome/aprogram.htmlh3程序设计/h3
ullia hrefpython.htmlPython程序设计/a/lilia hrefjava.htmlJava程序设计/a/li
/ul
a hrefbooks.htmlHome/anetwork.htmlh3计算机网络/h3
a hrefbooks.htmlHome/amysql.htmlh3MySQL数据库/h3
a hrefbooks.htmlHome/apython.htmlh3Python程序设计/h3
a hrefbooks.htmlHome/ajava.htmlh3Java程序设计/h3
a hrefbooks.htmlHome/a 这时深度优先与广度优先方法要做一点改进可以用一个 python 中的列表 urls 来记住已经访问过的网站如果一个网址 url 没有访问过就访问它并把 url 加到 urls 中保存起来如果 url 已经访问过就不再访问了这样就可以避免形成回路导致无限循环。2. 改进深度优先客户端程序 假定给定图 G 的初始状态是所有顶点均未曾访问过。在 G 中任选一顶点 v 为初始出发点圆点则深度优先遍历可以定义如下首先访问出发点v,并将其标记为已访问然后依次从 v 触发搜索 v 的每个邻接点 w 。若 w 未被曾访问过则以 w 为新的出发点继续进行深度优先遍历直至图中所有和原点 v 有路径相通的顶点以称为原点可达的顶点均已被访问为止。 图的深度优先遍历类似于树的前序遍历。采用的搜索方法的特点是 尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索 (Depth-First Search)。相应地用此方法遍历图就很自然地称之为图 的深度优先遍历基本实现思想访问顶点v;从v的未被访问的邻接点中选取一个顶点w从w出发进行深度 优先遍历重复上述两步直至图中所有和v有路径相通的顶点都被访问到。使用递归程序改进客户端程序 client1.py 如下# 使用递归的程序
from bs4 import BeautifulSoup
import urllib.requestdef spider(url):global urls # 使用列表存储和标记已经访问过的节点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 link in links:href link[href]url start_url / hrefspider(url)except Exception as err:print(err)start_url http://127.0.0.1:5000
urls []
spider(start_url)
print(The End)
使用栈的程序改进客户端程序 client2.py 如下# 使用栈的程序
from bs4 import BeautifulSoup
import urllib.requestclass 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) 0def spider(url):global urlsstack Stack()stack.push(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 links[i][href]url start_url / hrefstack.push(url)except Exception as err:print(err)start_url http://127.0.0.1:5000
urls []
spider(start_url)
print(The End)
这两个程序结果一样如下3. 改进广度优先客户端程序图的广度优先遍历BFS算法是一个分层搜索的过程和树的层序遍历算法类同它也需要一个队列以保持遍历过的顶点顺序以便按出队的顺序再去访问这些顶点的邻接顶点。基本实现思想1顶点v入队列。2当队列非空时则继续执行否则算法结束。3出队列取得队头顶点v访问顶点v并标记顶点v已被访问。4查找顶点v的第一个邻接顶点col。5若v的邻接顶点col未被访问过的则col入队列。6继续查找顶点v的另一个新的邻接顶点col转到步骤5。直到 顶点v的所有未被访问过的邻接点处理完。转到步骤2。广度优先遍历图是以顶点v为起始点由近至远依次访问和v有路径相通 而且路径长度为12……的顶点。为了使“先被访问顶点的邻接点”先 于“后被访问顶点的邻接点”被访问需设置队列存储访问的顶点。使用队列的程序改进客户端程序 client3.py 如下# 使用队列的程序
from bs4 import BeautifulSoup
import urllib.requestclass 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 urlsqueue Queue()queue.enter(url)while not queue.empty():url queue.fetch()if url not in urls:try: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 link[href]url start_url / hrefif url not in urls:queue.enter(url)except Exception as err:print(err)start_url http://127.0.0.1:5000
urls []
spider(start_url)
print(The End)
程序运行结果如下
