Graph Theory

In this section we will look into graph theory and mainly things that you need to know in order to recognise and solve such problems, both at interviews and at work.

As with other sections in this course it won’t be possible to go into details about various algorithms and techniques. One reason is that to do that we would need to write a book, not a single lesson. Our focus are the practice tasks. Another reason is that nowadays there are plenty of free resources on this and other topics that one can use to learn. We provide some links in the lessons and there are many more.

Unlike some other categories of algorithms it may not be immediately obvious that a task requires some sort of graph representation. This may be especially true for someone with little experience in solving such problems. Let’s first look at some entities that can be represented with graphs.

What things do graphs represent?

Some very natural examples are the transportation networks of cities or countries. Even the flights performed in the whole world could form a graph where airports are the nodes and flights are the connecting edges.

Another very popular situation is when there is a grid of some sort and the cells in it can be represented as nodes while the edges exist between cells that share a side. As an example take a spreadsheet application in which one needs to compute values in cells that are based on the values in other cells.

Various relationships between people could be described as graphs, too. Think about social networks and how people in them can be nodes in a graph and the relationships between them as edges.