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.