Introduction to Graph Algorithms

Learn the concepts of graph theory and graph algorithms by studying the Königsberg bridge problem.

We'll cover the following

This course is about algorithms on graphs, which are data structures that represent a set of nodes interconnected by edges. An example of a graph is shown below:

g a a b b a--b c c a--c d d a--d b--c
A graph with four nodes and four edges.

Although graphs are an abstract concept of mathematics and theoretical computer science, they can be used to model various problems from real-life applications. Some examples are:

  • routing of IP packages on the internet.
  • finding the fastest connection in public transportation systems.
  • detecting deadlocks in operating system processes.

As such, graph algorithms can be a powerful and versatile tool in every software developer’s toolbox.

A bit of history

The study of graph theory perhaps originated with the so-called Königsberg bridge problem. It is a neat example of modeling a real-life puzzle using graphs.

The historical Prussian city of Königsberg (today Kalinigrad) consisted of four landmasses separated by rivers and connected by a total of seven bridges. In the early 18th century, mathematician Leonard Euler studied whether there was any way to devise a walk through the city that crosses each of the bridges exactly once. Today, hiss analysis of this problem is today seen as one of the founding moments of graph theory.

Euler modeled the city as a graph with each section of the city being represented by a node and each bridge between two sections represented by an edge. This graph is illustrated below.

g a North Königsberg b Eastern island a--b c Western island a--c a--c b--c d South Königsberg b--d c--d c--d
The seven bridges of historical Königsberg, modeled as a graph.

One example walk that starts in north Königsberg is marked in blue below. The walk crosses six bridges and ends on the eastern island. The seventh bridge between the southern city and the western island can’t be crossed anymore.

g a North Königsberg b Eastern island a->b c Western island a->c b->c c->a d South Königsberg c->d c->d d->b
A walk from north Königsberg to the eastern island.

Euler “solved” the Königsberg bridge problem by showing that a solution could not exist. He reasoned that any walk through the city that crosses all bridges would have to leave every section of the city the same number of times that it is entered. The only exceptions are the two sections of the city where the walk starts and ends. But this still leaves us with at least two intermediate sections of the city that need to be entered the same number of times that they are exited.

These two intermediate sections must therefore be connected to an even number of bridges. However, each of the four city sections is connected to an odd number of bridges! Therefore, there can be no walk through the city that crosses each bridge exactly once.

An algorithm for Eulerian trails

In graph-theoretic terms, the Königsberg bridge problem looks for a walk along the edges of the graph that traverses each edge exactly once. Such a walk was later coined an Eulerian trail, in honor of Leonard Euler.

Euler showed that a Eulerian trail can only exist when two nodes in the graph are connected to an odd number of edges. He also claimed that an Eulerian trail could always be found in graphs that satisfy this condition, although he did not provide a proof or an algorithm for computing such a trail. In the late 19th century, mathematicians Carl Hierholzer and Pierre-Henry Fleury were the first to independently discover and publish a proof of this statement in the form of an algorithm for finding Eulerian trails.

Fleury’s algorithm

Let’s check out Fleury’s algorithm as the first example of a graph algorithm. Before we start, we should construct a graph that actually contains a Eulerian trail. We’ll take the Königsberg graph from above, but move one of the bridges between south Königsberg and the western island to directly connect north and south Königsberg.

g a North Königsberg b Eastern island a--b c Western island a--c a--c d South Königsberg a--d b--c b--d c--d
Modified Königsberg bridges graph with one bridge moved.

The resulting graph now has only two nodes with an odd number of edges, which makes it possible to construct an Eulerian trail from south Königsberg to the eastern island. Fleury’s algorithm describes how to achieve this:

  1. Start from a node with an odd number of edges.
  2. Select the next edge from the current node and choose an edge that will disconnect its endpoints once removed.
  3. Travel along the selected edge and remove it from the graph.

Let’s run the algorithm on the Königsberg bridges graph:

Implementing Fleury’s algorithm

Conceptually, Fleury’s algorithm seems relatively simple. It can be described in a short paragraph of text, and it was not very challenging to apply it on our small example graph. Implementing it in a programming language like C++ comes with its own set of challenges though.

So far, our perspective on graphs has been that they are drawings made up of circles and lines. Our first task will be to transfer this graphical representation into something a machine can work with, using efficient data structures like vector from the C++ standard library.

When looking at the image of the four-node Königsberg graph, it was easy for us to ascertain at a glance whether removing an edge would disconnect the graph. But neither a computer program nor a human can see the whole graph at once the graph has hundreds of millions of nodes. We’ll need strategies to traverse graphs and check whether removing certain edges would split them into separate components, which will also require efficient graph algorithms.

Next steps

During the rest of the course, you’ll learn:

  • the fundamental concepts of graph theory.
  • how graphs can be represented in code using adequate data structures.
  • algorithms for traversing graphs efficiently.
  • how to implement optimization algorithms that solve for the shortest path, network flow, and other problems.

We use the C++ programming language in this course, but the code examples should also be readily transferable to other programming languages like Java or Python. After finishing the course, you will be well equipped to implement graph algorithms like Fleury’s algorithm for finding Eulerian trails.