1. 复杂的 Web网站

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>

database.html

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

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>

network.html

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

mysql.html

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

python.html

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

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 如下：

python">python"># 使用递归的程序
from bs4 import BeautifulSoup
import 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 = 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 + "/" + href
                spider(url)
        except Exception as err:
            print(err)


start_url = "http://127.0.0.1:5000"
urls = []
spider(start_url)
print("The End")

使用栈的程序

改进客户端程序 client2.py 如下：

python">python"># 使用栈的程序
from bs4 import BeautifulSoup
import 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:
                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 + "/" + href
                    stack.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 如下：

python">python"># 使用队列的程序
from bs4 import BeautifulSoup
import 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) == 0


def spider(url):
    global urls
    queue = 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 + "/" + href
                    if 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")

程序运行结果如下：