La búsqueda en anchura primero en las páginas de Wikipedia está tardando mucho tiempo. ¿Puede alguien ayudarme a analizar el tiempo de ejecución de mi código?

Estoy tratando de realizar BFS en las páginas de Wikipedia. Creo que estoy implementándolo correctamente y de la mejor manera en términos de tiempo de ejecución (manteniéndolo en un solo hilo), pero está tardando mucho tiempo en encontrar una conexión entre dos artículos. Aquí está mi implementación:

marked = set()
queue = deque()
count = 0

def get_pagina_wikipedia(wiki_link):
    url = BASE_URL + wiki_link
    time.sleep(0.1)
    req = requests.get(url)
    soup = BeautifulSoup(req.text, 'html.parser')
    return soup

def backtrace(parent, start, end):
    boolean = False
    ret = []
    while boolean == False:
        if end in parent:
            ret.append(parent[end])
            end = parent[end]
            if end == start:
                break;
    ret.reverse()
    return ret

def bfs(first_wiki_link, second_wiki_link):
    print('Buscando desde ' + first_wiki_link + ' buscando ' + second_wiki_link + '...')
    parent = {}
    queue.append(first_wiki_link)
    start_time = time.time()
    while queue:
        link = queue.pop()
        current_parent = link
        link_list = list(filter(lambda c: c.get('href') != None and c.get('href').startswith('/wiki/') and c.get('href') != '/wiki/Main_Page' and ':' not in c.get('href'), get_wikipedia_page(link).findAll('a')))
        for link in link_list:
            href = link.get('href')
            if not marked.contains(href):
                parent[href] = current_parent
                marked.add(href)
                queue.append(href)
            if href == second_wiki_link:
                ret = backtrace(parent, first_wiki_link, second_wiki_link)
                print("Conexión encontrada")
                end_time = time.time()
                print("Encontró una conexión en: " + str(end_time - start_time) + " segundos.")
                print("El camino tiene " + str(len(ret)) + " páginas")
                print(ret)
                return True

A veces tarda algunos minutos en encontrar una coincidencia. ¿Es esto esperado debido al tamaño de Wikipedia? ¿O estoy cometiendo algún error aquí y lo estoy realizando de una manera no óptima? ¿O podría ser que BeautifulSoup se esté ejecutando demasiado lento?