准备数据结构

在进行广度优先和深度优先查找前，先定义一个数据结构。这里我用二叉树，每个节点的定义如下：

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

生成二叉树

下面的代码从命令行接收参数，递归的生成一个指定深度的满二叉树。

counter = 0def 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 rootif __name__ == '__main__':    import sys    s = sys.argv[1]    n = s.isdigit() and int(s)  # 不是数字就是False，False就是0    r = create_tree(n)    print(r, r.left, r.right)

示例尽量简单，这里就用了全局变量。

深度优先

深度优先可以用递归的方法来实现。上面创建的时候也是使用递归来创建的，所以创建节点的顺序也是深度优先。

所以这里再写一个递归函数，遍历每个节点并且打印出来：

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)  # 不是数字就是False，False就是0    r = create_tree(n)    print_tree(r)

这里节点是按创建的顺序输出的，因为创建的时候也是这样的一个递归的逻辑。

前序遍历

这个是二叉树的概念，上面的例子就是前序遍历。前序遍历：根结点 ---> 左子树 ---> 右子树有前序遍历，就还有中序和后序

中序遍历

中序遍历：左子树---> 根结点 ---> 右子树

def print_tree(root):    if root is None:        return    print_tree(root.left)    print(root)  # 根节点这句移到中间    print_tree(root.right)

后序遍历

后序遍历：左子树 ---> 右子树 ---> 根结点

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

广度优先

实现广度优先，只需要操作列表就可以了。遍历列表里的每一个元素，输出该元素并把子元素添加到一个新的列表里，给下一次遍历来操作：

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

层次遍历

相对于二叉树的前序遍历，这个遍历的方法叫层次遍历。

爬虫示例

网页爬虫的核心是解决图的遍历。对于网络爬虫，一般使用的就是广度优先的遍历。

下面的示例，从命令行接收url，把这个url下的所有链接打印出来。然后继续对这些链接发起请求，打印链接，一直循环下去：

import requestsfrom bs4 import BeautifulSoupfrom urllib.parse import urljoindef extract(url):    """向给定的url发起GET请求，    解析HTML，返回其中存在的链接    """    try:        response = requests.get(url, timeout=0.1)  # 注意这里设置了超时时间    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 linksdef 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)  # 向列表尾部添加多个元素deep = 0if __name__ == '__main__':    import sys    breadth_first(sys.argv[1:])  # http://lab.scrapyd.cn/ 这个站点用来做实验不错

部分执行结果：

$ python 5crawl.py http://lab.scrapyd.cn/DEEP: 1 http://lab.scrapyd.cn/DEEP: 2 http://lab.scrapyd.cn/archives/57.htmlDEEP: 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.htmlDEEP: 2 http://lab.scrapyd.cn/archives/29.htmlDEEP: 2 http://lab.scrapyd.cn/tag/%E6%9C%A8%E5%BF%83/DEEP: 2 http://lab.scrapyd.cn/archives/28.htmlDEEP: 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.htmlDEEP: 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.cnDEEP: 2 http://www.scrapyd.cnDEEP: 3 http://lab.scrapyd.cn/archives/26.htmlDEEP: 3 http://lab.scrapyd.cn/archives/25.htmlDEEP: 3 http://lab.scrapyd.cn/archives/24.htmlDEEP: 3 http://lab.scrapyd.cn/archives/23.htmlDEEP: 3 http://lab.scrapyd.cn/archives/22.htmlDEEP: 3 http://lab.scrapyd.cn/page/5/

理论上这个程序会把所有可达的网页都访问到，或者内存耗尽。

现在的内存也没那么块能耗尽。然后互联网也是无限延伸的，基本上就是没完没了了。不过实际上，遇到某个下载的链接就会卡住了。这个不是这篇的重点，就不深究了。