深度優(yōu)先和廣度優(yōu)先

準(zhǔn)備數(shù)據(jù)結(jié)構(gòu)

在進(jìn)行廣度優(yōu)先和深度優(yōu)先查找前，先定義一個(gè)數(shù)據(jù)結(jié)構(gòu)。這里我用二叉樹(shù)，每個(gè)節(jié)點(diǎn)的定義如下：

class Node(object):
    def __init__(self, item, left=None, right=None):
        self.item = item
        self.left = left
        self.right = right

    def __str__(self):
        return '%s' % self.item

生成二叉樹(shù)

下面的代碼從命令行接收參數(shù)，遞歸的生成一個(gè)指定深度的滿二叉樹(shù)。

counter = 0

def create_tree(deep):
    if deep < 0:
        return None
    global counter
    counter += 1
    root = Node(counter, deep)
    root.left = create_tree(deep-1)
    root.right = create_tree(deep-1)
    return root

if __name__ == '__main__':
    import sys
    s = sys.argv[1]
    n = s.isdigit() and int(s)  # 不是數(shù)字就是False，F(xiàn)alse就是0
    r = create_tree(n)
    print(r, r.left, r.right)

示例盡量簡(jiǎn)單，這里就用了全局變量。

深度優(yōu)先

深度優(yōu)先可以用遞歸的方法來(lái)實(shí)現(xiàn)。上面創(chuàng)建的時(shí)候也是使用遞歸來(lái)創(chuàng)建的，所以創(chuàng)建節(jié)點(diǎn)的順序也是深度優(yōu)先。
所以這里再寫(xiě)一個(gè)遞歸函數(shù)，遍歷每個(gè)節(jié)點(diǎn)并且打印出來(lái)：

def print_tree(root):
    if root is None:
        return
    print(root)
    print_tree(root.left)
    print_tree(root.right)

if __name__ == '__main__':
    import sys
    s = sys.argv[1]
    n = s.isdigit() and int(s)  # 不是數(shù)字就是False，F(xiàn)alse就是0
    r = create_tree(n)
    print_tree(r)

這里節(jié)點(diǎn)是按創(chuàng)建的順序輸出的，因?yàn)閯?chuàng)建的時(shí)候也是這樣的一個(gè)遞歸的邏輯。

前序遍歷
這個(gè)是二叉樹(shù)的概念，上面的例子就是前序遍歷。
前序遍歷：根結(jié)點(diǎn) ---> 左子樹(shù) ---> 右子樹(shù)
有前序遍歷，就還有中序和后序

中序遍歷
中序遍歷：左子樹(shù)---> 根結(jié)點(diǎn) ---> 右子樹(shù)

def print_tree(root):
    if root is None:
        return
    print_tree(root.left)
    print(root)  # 根節(jié)點(diǎn)這句移到中間
    print_tree(root.right)

后序遍歷
后序遍歷：左子樹(shù) ---> 右子樹(shù) ---> 根結(jié)點(diǎn)

def print_tree(root):
    if root is None:
        return
    print_tree(root.left)
    print_tree(root.right)
    print(root)

廣度優(yōu)先

實(shí)現(xiàn)廣度優(yōu)先，只需要操作列表就可以了。遍歷列表里的每一個(gè)元素，輸出該元素并把子元素添加到一個(gè)新的列表里，給下一次遍歷來(lái)操作：

def print_tree(l):
    work = [l]
    while len(work) > 0:
        items, work = work, []  # 復(fù)制一份用于遍歷，并把自己清空，接收下一次要遍歷的元素
        for i in items:
            if i is None:
                continue
            print(i)
            work.append(i.left)
            work.append(i.right)

層次遍歷
相對(duì)于二叉樹(shù)的前序遍歷，這個(gè)遍歷的方法叫層次遍歷。

爬蟲(chóng)示例

網(wǎng)頁(yè)爬蟲(chóng)的核心是解決圖的遍歷。對(duì)于網(wǎng)絡(luò)爬蟲(chóng)，一般使用的就是廣度優(yōu)先的遍歷。
下面的示例，從命令行接收url，把這個(gè)url下的所有鏈接打印出來(lái)。然后繼續(xù)對(duì)這些鏈接發(fā)起請(qǐng)求，打印鏈接，一直循環(huán)下去：

import requests
from bs4 import BeautifulSoup
from urllib.parse import urljoin

def extract(url):
    """向給定的url發(fā)起GET請(qǐng)求，
    解析HTML，返回其中存在的鏈接
    """
    try:
        response = requests.get(url, timeout=0.1)  # 注意這里設(shè)置了超時(shí)時(shí)間
    except Exception:
        return False
    if not response.ok:
        return False
    global deep
    print("DEEP:", deep, url)
    soup = BeautifulSoup(response.text, features='html.parser')
    targets = soup.find_all('a')
    links = []
    for i in targets:
        links.append(urljoin(url, i.attrs.get('href')))
    return links

def breadth_first(urls):
    seen = {}  # 記錄去重的字典
    global deep
    while len(urls) > 0:
        deep += 1
        items, urls = urls, []
        for i in items:
            if not seen.get(i):
                seen.setdefault(i, True)
                links = extract(i)
                if links:
                    urls.extend(links)  # 向列表尾部添加多個(gè)元素

deep = 0

if __name__ == '__main__':
    import sys
    breadth_first(sys.argv[1:])  # http://lab.scrapyd.cn/ 這個(gè)站點(diǎn)用來(lái)做實(shí)驗(yàn)不錯(cuò)

部分執(zhí)行結(jié)果：

$ python 5crawl.py http://lab.scrapyd.cn/
DEEP: 1 http://lab.scrapyd.cn/
DEEP: 2 http://lab.scrapyd.cn/archives/57.html
DEEP: 2 http://lab.scrapyd.cn/tag/%E8%89%BA%E6%9C%AF/
DEEP: 2 http://lab.scrapyd.cn/tag/%E5%90%8D%E7%94%BB/
DEEP: 2 http://lab.scrapyd.cn/archives/55.html
DEEP: 2 http://lab.scrapyd.cn/archives/29.html
DEEP: 2 http://lab.scrapyd.cn/tag/%E6%9C%A8%E5%BF%83/
DEEP: 2 http://lab.scrapyd.cn/archives/28.html
DEEP: 2 http://lab.scrapyd.cn/tag/%E6%B3%B0%E6%88%88%E5%B0%94/
DEEP: 2 http://lab.scrapyd.cn/tag/%E7%94%9F%E6%B4%BB/
DEEP: 2 http://lab.scrapyd.cn/archives/27.html
DEEP: 2 http://lab.scrapyd.cn/tag/%E6%99%BA%E6%85%A7/
DEEP: 2 http://lab.scrapyd.cn/page/1/
DEEP: 2 http://lab.scrapyd.cn/page/2/
DEEP: 2 http://lab.scrapyd.cn/page/3/
DEEP: 2 http://lab.scrapyd.cn/page/4/
DEEP: 2 http://lab.scrapyd.cn/page/6/
DEEP: 2 http://lab.scrapyd.cn/tag/%E4%BA%BA%E7%94%9F/
DEEP: 2 http://lab.scrapyd.cn/tag/%E5%8A%B1%E5%BF%97/
DEEP: 2 http://lab.scrapyd.cn/tag/%E7%88%B1%E6%83%85/
DEEP: 2 http://lab.scrapyd.cn/tag/%E7%8E%8B%E5%B0%94%E5%BE%B7/
DEEP: 2 http://lab.scrapyd.cn/tag/%E7%BB%9D%E4%B8%96%E5%A5%BD%E8%AF%8D/
DEEP: 2 http://lab.scrapyd.cn/tag/%E8%AF%8D/
DEEP: 2 http://lab.scrapyd.cn
DEEP: 2 http://www.scrapyd.cn
DEEP: 3 http://lab.scrapyd.cn/archives/26.html
DEEP: 3 http://lab.scrapyd.cn/archives/25.html
DEEP: 3 http://lab.scrapyd.cn/archives/24.html
DEEP: 3 http://lab.scrapyd.cn/archives/23.html
DEEP: 3 http://lab.scrapyd.cn/archives/22.html
DEEP: 3 http://lab.scrapyd.cn/page/5/

理論上這個(gè)程序會(huì)把所有可達(dá)的網(wǎng)頁(yè)都訪問(wèn)到，或者內(nèi)存耗盡。
現(xiàn)在的內(nèi)存也沒(méi)那么塊能耗盡。然后互聯(lián)網(wǎng)也是無(wú)限延伸的，基本上就是沒(méi)完沒(méi)了了。
不過(guò)實(shí)際上，遇到某個(gè)下載的鏈接就會(huì)卡住了。這個(gè)不是這篇的重點(diǎn)，就不深究了。