How Graph Traversal Powers Web Crawlers: From BFS to Internet Indexing

Discrete mathematics comprises mathematical logic, set theory, graph theory, and modern algebra. This article focuses on the relationship between graph theory and web crawlers.

Graph theory originated with Leonhard Euler in 1736 when he proved that it is impossible to walk each of the seven bridges of Königsberg exactly once and return to the starting point, marking the birth of graph theory.

In graph theory, a graph consists of nodes and arcs connecting them. If we treat Chinese cities as nodes and national highways as arcs, the country's road network becomes a graph. The most important graph algorithms are traversal algorithms, which determine how to visit all nodes via arcs.

Using BFS (Breadth‑First Search), we start from a city (e.g., Beijing) and visit all directly connected cities, then their neighbors, and continue until every city has been visited. DFS (Depth‑First Search) follows a single path as far as possible before backtracking, also guaranteeing full coverage.

Both methods require recording visited cities to avoid repeats or omissions.

The Internet can be viewed as a massive graph where each webpage is a node and hyperlinks are arcs. By applying graph traversal algorithms, a program can automatically visit every page and store its content. Such a program is called a web crawler (or robot).

The first web crawler was created in 1993 by MIT student Matthew Gray, named “WWW Wanderer.” Modern crawlers follow the same principle but are far more complex.

To crawl an entire website, a crawler downloads the homepage, extracts all hyperlinks, and recursively visits linked pages, using a hash table to track which pages have already been downloaded.

Given the enormous size of the Internet—e.g., Yahoo claimed to index 20 billion pages—downloading every page would take centuries on a single machine. Therefore, commercial crawlers operate on thousands of servers connected by high‑speed networks.