Degrees of Wikipedia
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']