Degrees of Wikipedia Here is my attempt on implementing "Degrees of Wikipedia" (much faster version can be seen at degreesofwikipedia.com.It's basically an algorithm which tries to connect two unrelated Wikipedia pages by traversing the internal wikilinks they contain. This version in order to produce faster result doesn't look for the exact match, but just for the matching substring in the url, but that can be changed by editing one line, so it's not really an issue.

import re
from collections import deque

import requests
from bs4 import BeautifulSoup


class UrlNode:
    def __init__(self, url, prev):
        self.url = url
        self.prev = prev
        self.transform_url()

    def transform_url(self):
        if self.url.startswith("/wiki"):
            self.url = "https://en.wikipedia.org" + self.url

    def get_subject(self):
        return self.url.rsplit("/", 1)[1].replace("_", " ")


def is_wiki_url(url):
    url_pattern = r"^/wiki/[a-zA-Z0-9_\,.'-]+$"
    return re.match(url_pattern, url, re.I)


def print_path(result):
    path = []
    distance = 0
    while result is not None:
        path.append(result.get_subject())
        distance += 1
        result = result.prev
    path.reverse()

    print("DISTANCE:", distance)
    print(" -&gt; ".join(path))


def crawl(start, query):
    print(" ==== WIKI CRAWLER === ")
    print("Searching for connnection between '", start, "' and '", query, "'", sep="")
    query = query.replace(" ", "_")
    start = "/wiki/" + start.replace(" ", "_")
    session = requests.session()
    visited_urls = []
    start_url = UrlNode(start, None)
    url_queue = deque()
    url_queue.append(start_url)
    while url_queue:
        url_node = url_queue.popleft()
        if url_node.url in visited_urls:
            continue
        visited_urls.append(url_node.url)
        print(url_node.url)
        req = session.get(url_node.url)
        bs = BeautifulSoup(req.text, 'html.parser')
        for link in bs.find_all('a'):
            if not link.has_attr("href"):
                continue
            if is_wiki_url(link["href"]) and link["href"] not in visited_urls:
                # print("\tFound: ", link["href"])
                new_node = UrlNode(link["href"], url_node)
                if query in new_node.url:
                    print("Total pages visited:", str(len(visited_urls)))
                    return new_node
                url_queue.append(new_node)
    return None


start = "Stack Overflow"
query = "Banana"
result = crawl(start, query)
print_path(result)


This generates result:

Total pages visited: 1054
DISTANCE: 4
Stack Overflow -&gt; Wiki -&gt; University of California -&gt; UC Santa Cruz Banana Slugs


My question is: how can I make this work faster? I welcome both algorithmic suggestions and various "hacks", e.g. requesting the mobile version of the page, which should load faster etc. Here I used breadth-first algorithm, which is very basic and I'm pretty sure better options exist.
I think you can potentially remove the impact of the network altogether by using offline Wikipedia dumps. Wikipedia itself asks to not crawl them:


  Suppose you are building a piece of software that at certain points
  displays information that came from Wikipedia. If you want your
  program to display the information in a different way than can be seen
  in the live version, you'll probably need the wikicode that is used to
  enter it, instead of the finished HTML.
  
  Also, if you want to get all the data, you'll probably want to
  transfer it in the most efficient way that's possible. The
  wikipedia.org servers need to do quite a bit of work to convert the
  wikicode into HTML. That's time consuming both for you and for the
  wikipedia.org servers, so simply spidering all pages is not the way to
  go.
  
  Please do not use a web crawler to download large numbers of articles. Aggressive crawling of the server can cause a dramatic slow-down of Wikipedia.

as far as improving HTML parsing, you can replace html.parser with a faster lxml:

bs = BeautifulSoup(req.text, 'lxml')


Note: this requires lxml package to be installed.
make visited_urls a set - this would dramatically improve the lookups 
instead of locating all links and then filtering them, you can ask BeautifulSoup to locate only "wiki" links by using a a[href^="/wiki/"] CSS selector - this would also lead to removing the "href" attribute presence check:

for link in bs.select('a[href^="/wiki/"]'):
    if link["href"] not in visited_urls:

there is also this SoupStrainer class that would allow you to parse only a part of the document - see if you can apply it to skip some irrelevant parts of the pages
I am not sure if you actually need a UrlNode class, but if you think you do, __slots__ should improve performance and memory usage:

class UrlNode:
    __slots__ = ['url', 'prev']