The two orders in more depth
Both are standard graph traversals applied to the web’s link graph. The difference is only in how the URL frontier hands out the next URL: breadth-first takes the oldest URL (a first-in first-out queue), depth-first takes the newest (a last-in first-out stack).
On a finished crawl with no limits, both visit the same pages. The order matters when the crawl stops early, which nearly every real crawl does, because of a page limit, a time limit or a crawl budget.
How they compare
| Breadth-first | Depth-first | |
|---|---|---|
| Fetch order | Level by level from the seed | One branch to the end, then backtrack |
| Under a page limit | Shallow pages across the site | Deep pages in a few sections |
| Crawl depth of a page | Shortest path from the seed | Depends on the branch taken first |
| Crawler traps | Contained by a depth limit | Can swallow the whole budget |
| Memory | Frontier grows wide | Frontier stays narrow |
Breadth-first has a useful property for crawl depth: the first time it reaches a page is along a shortest path, so the depth it records is the true minimum. Depth-first can find a page late and deep even when it is one click from the homepage.
Example: a 10-page limit
Take a docs site whose homepage links to five sections, each with fifty pages that link to each other in sequence.
- Breadth-first: the homepage, the five section indexes, then the first few pages of the first sections. A broad sample of the site.
- Depth-first: the homepage, the first section index, then nine consecutive pages from that one section. Four sections are never seen.
Common pitfalls
- Assuming strict order in a parallel crawler. With many workers fetching at once, pages finish out of order, so traversal is only approximately breadth-first.
- Using depth-first for coverage. It suits exploring a single deep chain, such as pagination, not sampling a whole site.
- Relying on order instead of limits. Breadth-first still needs a max depth and a page limit on sites with large menus.
How SarvCrawl handles it
Crawl pages are processed from a priority job queue, ordered by priority and then by creation time. Because links found earlier are queued earlier, a crawl behaves roughly breadth-first, though it does not guarantee strict level-by-level order. max_depth and limit bound how far and how much it goes, and the crawl tree in the console places each page under the page that first linked to it.
Frequently asked questions
Which is better for web crawling, BFS or DFS?
Breadth-first, in most cases. It reaches the shallow, well-linked pages first and copes better with crawler traps. Depth-first suits narrow tasks such as following one paginated list.
Do search engines crawl breadth-first?
Not strictly. They start from something close to breadth-first and reorder the frontier by signals such as page importance and how often it changes.
Does crawl order change the result?
Only if the crawl stops before the frontier empties. With a page or time limit, order decides which pages make it in.
What is best-first crawling?
A crawl that orders the frontier by a score, such as relevance to a topic, rather than by depth. Focused crawlers use it to reach on-topic pages sooner.