Web Crawler
Medium · Graphs · Explanation and code example
Breadth-first search
How it works
bfs provides an alternative traversal that explores URLs level by level, visiting all URLs at distance 1 before distance 2, and so on. This approach uses a queue instead of recursion and naturally discovers URLs in order of their distance from the starting URL.
Steps
- Create a helper function to extract the hostname from a URL.
- Extract the starting hostname, initialize a queue with the start URL, and create a
visitedset containing the start URL. - While the queue is not empty, dequeue a URL.
- For each URL returned by
htmlParser.getUrls(), check if it has the same hostname and has not been visited. - If valid, add the URL to both the queue and the
visitedset. - Return the
visitedset containing all crawled URLs after the queue is exhausted.
Complexity
- Time complexity:
O(m × l) - Space complexity:
O(n × l)
Where
mis the number of edges in the graph,lis the maximum length of a URL (urls[i].length), andnis the total number of URLs (urls.length).
Things to watch for
Incorrect Hostname Extraction
Extracting the hostname incorrectly is a frequent mistake. URLs follow the format http://hostname/path, so the hostname is the third element when splitting by /. Off-by-one errors or not accounting for URLs without paths can cause the crawler to include or exclude wrong domains.
Not Marking URLs as Visited Before Adding to Queue
In BFS, you must mark a URL as visited when adding it to the queue, not when processing it. If you wait until dequeuing, multiple threads or iterations might add the same URL to the queue multiple times, leading to redundant work and potentially infinite loops.
Visiting URLs Outside the Starting Hostname
The crawler must only visit URLs with the same hostname as the starting URL. Failing to filter URLs by hostname before crawling will cause the solution to explore unrelated domains, violating the problem constraints and potentially causing timeouts or incorrect results.
Python code example
from typing import List
import collections
class Solution:
def crawl(self, startUrl: str, htmlParser: 'HtmlParser') -> List[str]:
def get_hostname(url):
# split url by slashes
# for instance, "http://example.org/foo/bar" will be split into
# "http:", "", "example.org", "foo", "bar"
# the hostname is the 2-nd (0-indexed) element
return url.split('/')[2]
start_hostname = get_hostname(startUrl)
q = collections.deque([startUrl])
visited = set([startUrl])
while q:
url = q.popleft()
for next_url in htmlParser.getUrls(url):
if get_hostname(next_url) == start_hostname and next_url not in visited:
q.append(next_url)
visited.add(next_url)
return visited
C++ code example
class Solution {
public:
vector<string> crawl(string startUrl, HtmlParser htmlParser) {
function<string(string)> getHostname = [](string url) -> string {
// find the next slash in the url after "http://"
// that is after the 7-th position inclusively
// if there is no such slash, pos will be equal to url.size()
int pos = min(url.size(), url.find('/', 7));
// return the substring that starts after "http://" and ends
// before the next slash or at the end of the string
return url.substr(7, pos - 7);
};
queue<string> q;
q.push(startUrl);
unordered_set<string> visited{startUrl};
string startHostname = getHostname(startUrl);
while (!q.empty()) {
string url = q.front();
q.pop();
for (string nextUrl : htmlParser.getUrls(url)) {
if (getHostname(nextUrl) == startHostname && !visited.count(nextUrl)) {
q.push(nextUrl);
visited.insert(nextUrl);
}
}
}
return vector<string>(visited.begin(), visited.end());
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.