Introduction and History of Basic Graph Algorithms
Discover the history and foundational principles of basic graph algorithms. Learn how graphs represent relationships and explore their early uses from ancient road networks to classical graph theory development. This lesson provides a solid background to understand graph algorithm structures and their evolution.
We'll cover the following...
History of graphs
A graph is a collection of pairs—pairs of integers, pairs of people, pairs of cities, pairs of stars, pairs of countries, pairs of scientific papers, pairs of web pages, pairs of game positions, pairs of recursive subproblems, and even pairs of graphs. Mirroring is the most common method for visualizing graphs; the underlying objects being paired are usually called vertices or nodes, and the pairs themselves are called edges or arcs, but in fact, the objects and pairs can be anything at all.
One of the earliest examples of graphs is road networks and maps thereof. Roman engineers constructed a network of more than 400,000 km of public roads across Europe, western and central Asia, and northern Africa during the height of the Roman empire. Travelers on the road network would carry itineraries, which were either simple lists or more pictorial representations of the landmarks and distances along various roads. The Tabula Peutingeriana, a 13th-century scroll depicting the entire Roman cursus publicus, is widely believed to be a medieval copy of a 5th-century revision of a ...