Skip to main content
All questions
MediumGraphs · Breadth-First Search

Web Crawler Link Traversal

Written by a community member · · 3 attempts · 0% pass

0

Implement a web crawler over a directed graph of pages represented in-memory.

You are given a starting URL and the pages of the web as two parallel lists: pages[i] is a URL and links[i] is the list of URLs that page links to. Return all URLs reachable from the starting URL using breadth-first search order, but the final answer may be in any order.

Function signature:
crawl_web(start_url: str, pages: list[str], links: list[list[str]]) -> list[str]

Rules:

  • Only follow links to URLs that appear in pages.
  • Ignore duplicate links from the same page.
  • Do not revisit pages already seen.
  • The starting URL should be included in the result if it is one of the pages; if it is not, return an empty list.
  • Treat the graph as directed.

Examples:
Input: crawl_web('a', ['a', 'b', 'c', 'd'], [['b', 'c'], ['d'], ['d'], []])
Output: ['a', 'b', 'c', 'd']

Input: crawl_web('x', ['a', 'b'], [['b'], []])
Output: []

Constraints:

  • 1 <= number of pages <= 10^5
  • Total number of links across all pages <= 10^5
  • Use an iterative approach; recursion may overflow on large graphs.