notexOPENOverview
Notex/Systems/DFS vs BFS
09.06LESSON 06 OF 12 · 1 MIN READ

DFS vs BFS

Always free to read
SECTION VIDEODFS vs BFS

Video coming soon. Start with the reading below.

COMING SOON

You can think of the web as a directed graph where web pages serve as nodes and hyperlinks (URLs) as edges. The crawl process can be seen as traversing a directed graph from one web page to others. Two common graph traversal algorithms are DFS and BFS. However, DFS is usually not a good choice because the depth of DFS can be very deep.

BFS is commonly used by web crawlers and is implemented by a first-in-first-out (FIFO) queue. In a FIFO queue, URLs are dequeued in the order they are enqueued. However, this implementation has two problems:

  • Most links from the same web page are linked back to the same host. In Figure 9-5, all the links in wikipedia.com are internal links, making the crawler busy processing URLs from the same host (wikipedia.com). When the crawler tries to download web pages in parallel, Wikipedia servers will be flooded with requests. This is considered as “impolite”.
Design a web crawler — original diagram 114
  • Standard BFS does not take the priority of a URL into consideration. The web is large and not every page has the same level of quality and importance. Therefore, we may want to prioritize URLs according to their page ranks, web traffic, update frequency, etc.
Progress is saved on this device.
KEEP EXPLORING

One note leads to another.

Back to the library →
⌕
Search across the entire library ⌘ K