3.2 网站图的爬取路径

深度优先与广度优先方法都是遍历树的一种方法，但是网站的各个网页 之间的关系未必是树的结构，它们可能组成一个复杂的图形结构，即有回路。

如果在前面的网站中每个网页都加一条Home的语句，让每个网页都能回到主界面，那么网站的关系就是一个有回路的图。

1. 复杂的 Web网站

---

1. books.html

<h3>计算机</h3>
<ul><li><a href="database.html">数据库</a></li><li><a href="program.html">程序设计</a></li><li><a href="network.html">计算机网络</a></li>
</ul>

2. database.html

<h3>数据库</h3>
<ul><li><a href="mysql.html">MySQL数据库</a></li>
</ul>
<a href="books.html">Home</a>

3. program.html

<h3>程序设计</h3>
<ul><li><a href="python.html">Python程序设计</a></li><li><a href="java.html">Java程序设计</a></li>
</ul>
<a href="books.html">Home</a>

4. network.html

<h3>计算机网络</h3>
<a href="books.html">Home</a>

5. mysql.html

<h3>MySQL数据库</h3>
<a href="books.html">Home</a>

6. python.html

<h3>Python程序设计</h3>
<a href="books.html">Home</a>

7. java.html

<h3>Java程序设计</h3>
<a href="books.html">Home</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有路径相通 而且路径长度为1，2，……的顶点。为了使“先被访问顶点的邻接点”先 于“后被访问顶点的邻接点”被访问，需设置队列存储访问的顶点。

使用队列的程序

改进客户端程序 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")

程序运行结果如下：