call(back)
Algorithms & Data StructuresmediumSign in to star problems

Wiki Page Links III

You are given getLinkedPages(uri), which fetches a wiki page and returns the URIs it links to. Return every page reachable from start by following links, including start itself, in any order.

// A -> B, A -> C, B -> D, C -> D, D -> A
crawl("A", getLinkedPages)  ->  ["A", "B", "C", "D"]

Fetch each page exactly once: the harness fails a run that fetches the same page twice, and its fetcher returns an empty list for unknown pages.

Hints

Hint 1

The visited set is the whole algorithm: add a page the moment it is discovered, fetch it once, and the cycle A -> B -> A ends by itself.

Hint 2

Return the visited set when the queue is empty.

Asked at