python-3.x - 如何实现广度优先和深度优先搜索网络爬虫？

Question

我正在尝试使用 Beautiful Soup 用 Python 编写一个网络爬虫，以便爬取网页上的所有链接。在获得主页上的所有链接后，我尝试实现深度优先和广度优先搜索以查找 100 个附加链接。目前，我已经抓取并获取了主页上的链接。现在我需要帮助实现我的爬虫程序的深度优先和广度优先方面。

我相信我的网络爬虫正在执行深度优先搜索。这是正确的还是我的代码没有正确执行深度优先搜索？此外，如何调整代码来创建广度优先搜索？我相信我需要一个队列并使用 pop 函数，但我不确定如何正确执行循环，因为我是 Python 新手。

我尝试过调整我的代码，但到目前为止，我所做的一切都无法获得正确的结果。

from pandas import *
import urllib.request
import re
import time
from bs4 import BeautifulSoup

#open webpage and put into soup

myURL="http://toscrape.com"
response = urllib.request.urlopen(myURL)
html = response.read()
soup = BeautifulSoup(html, "html.parser")

#get links on the main page 

websitesvisited = []
for link in soup.findAll('a'):
    websitesvisited.append(link.get('href'))

#use depth-first search to find 100 additional links

allLinks= [] 
for links in websitesvisited:
    myURL=links
    response = urllib.request.urlopen(myURL)
    html = response.read()
    soup = BeautifulSoup(html, "html.parser")
    if len(allLinks) < 101:
        for link in soup.findAll('a'):
            if link.get('href') not in allLinks:
                if link.get('href') != None:
                    if link.get('href') [0:4] == 'http':
                        allLinks.append(link.get('href'))
    time.sleep(3)

for weblinks in allLinks:
    print(weblinks)

我抓取了主页并获得了所有链接。现在，我期望使用深度优先和广度优先网络爬行获得大约 100 个额外链接。

Answer 1

你的方向非常正确。 DFS的关键是递归，这正是上面代码中缺失的元素。对于当前页面上的每个链接，在访问页面上的其余链接之前递归地探索它。使用 visited 集来跟踪哪些页面已被抓取，以避免陷入循环。

“探索的总链接数”值在 DFS 中可能没有帮助，因为您的爬虫只会删除前 100 个页面的第一个链接，然后返回而不涉及任何广度(互联网上的几乎每个页面都有链接，因此终端节点很难获得)。 “深度”(或距离)上限更有意义:这使我们能够探索远离当前页面的所有链接max_depth页面。

无论哪种方式，代码基本上是相同的，当然，如果您编码，您可以说“给我第一个 cap 链接，深度可达 max_depth 页”将其作为递归中的基本情况。另一个想法是确保您正在探索的所有链接都来自quotes.toscrape 网站。 BFS 将严格探索直接边界并展开。这可以通过队列迭代完成。

这是一个递归 DFS 草图:

import requests
from bs4 import BeautifulSoup

def get_links_recursive(base, path, visited, max_depth=3, depth=0):
    if depth < max_depth:
        try:
            soup = BeautifulSoup(requests.get(base + path).text, "html.parser")

            for link in soup.find_all("a"):
                href = link.get("href")

                if href not in visited:
                    visited.add(href)
                    print(f"at depth {depth}: {href}")

                    if href.startswith("http"):
                        get_links_recursive(href, "", visited, max_depth, depth + 1)
                    else:
                        get_links_recursive(base, href, visited, max_depth, depth + 1)
        except:
            pass


get_links_recursive("http://toscrape.com", "", set(["http://toscrape.com"]))

这是 BFS 草图:

import requests
from bs4 import BeautifulSoup
from collections import deque

visited = set(["http://toscrape.com"])
dq = deque([["http://toscrape.com", "", 0]])
max_depth = 3

while dq:
    base, path, depth = dq.popleft()
    #                         ^^^^ removing "left" makes this a DFS (stack)

    if depth < max_depth:
        try:
            soup = BeautifulSoup(requests.get(base + path).text, "html.parser")

            for link in soup.find_all("a"):
                href = link.get("href")

                if href not in visited:
                    visited.add(href)
                    print("  " * depth + f"at depth {depth}: {href}")

                    if href.startswith("http"):
                        dq.append([href, "", depth + 1])
                    else:
                        dq.append([base, href, depth + 1])
        except:
            pass

这些是非常简单的草图。错误处理和 href 修剪只是勉强处理。存在相对链接和绝对链接的混合，其中一些具有前导和/或尾部斜杠。我将把操作这些作为练习留给读者。