This is the summary version of the article published in the Algorithmically Speaking newsletter which is only dedicated to exploring some of the most beautiful algorithmic problems and solutions in the history of Computer Science.

You can read the complete version by clicking on this link.

---

Hello there!

Today we will be diving into one of the most common ways of representing data and modeling problems (and solutions) in Computer Science. We will be talking about Graphs.

This will be the first of a series of posts introducing graph theory in a very visual way.

It will consist of some basic definitions of graph theory that will lay the basis for us to be able to explore more complex topics in future posts. The idea is to present the definitions along with visual representations, to help in the process of learning new concepts.

At the end of the post, you will find some algorithmic challenges so you can try and apply some of the topics that I will explain today. Feel free to skip to that part if you think you already have the necessary skills to solve them.

Let’s begin!

---

Nodes, Edges, and Paths

A graph consists of nodes and edges. We could see the nodes as the fundamental entities of graphs, and edges represent the relationships between nodes.

One good thing about graphs is that, even if they represent an abstract mathematical definition, we can visually display them using the most simple drawings of circles and lines.

For example, here’s a hand-drawn image of a graph with 5 nodes and 7 edges that we will we use to help us understand some basic definitions:

A path leads from node a to node b through the edges of the graph. The length of a path is the number of edges in it.

For example, the highlighted (red) path between the two green nodes in the following image is of length 3:

Note: The highlighted path is just one of the possible paths between the two green nodes. Try to identify every possible path between them.

A path is a cycle if the first and last node is the same. On the other hand, a path is called simple if each node appears at most once in the path.

For example, the highlighted path in the previous image corresponds to a simple path, while the one in the following image is considered a cycle:

Connectivity

A graph is connected if there is a path between any two nodes. For example, our initial graph is connected:

Try it yourself: take any pair of nodes in the previous graph and check that, indeed, there is a path between them.

On the other hand, the following graph is not connected because there is no path between the highlighted nodes:

In fact, there is no path between any node located in the right-bottom corner and any node located in the left-top corner.

The sets of connected nodes in a graph are called connected components. Here are the connected components (nodes with the same color) of the previous graph:

We can clearly see that this graph has two connected components.

A tree is a connected graph that consists of n nodes and n−1 edges. There is a unique path between any two nodes of a tree. You can also think of a tree as a connected graph that doesn’t contain any cycles.

For example, the following graph is a tree:

Try it yourself: take any pair of nodes in the previous graph and check that, indeed, there is a unique path between them.

Direction and Weights

A graph is directed if the edges can be traversed in one direction only. For example, the following graph is directed:

Notice how in the following image there is a path (more than one actually) between the green node and the blue node, but the opposite is not true. You cannot find any path starting in the blue node and ending in the green one:

As we can see, the fact the graph is directed affects the concept of connectivity, which is called strong connectivity when we are referring to directed graphs. We will learn more about this in future posts of the series.

In a weighted graph, each edge is assigned a weight. The weights are often interpreted as edge lengths.

The following graph is weighted:

The length of a path in a weighted graph is the sum of the edge weights on the path. For example, in the following graph, the length of the highlighted path between the green nodes is 13 (8 + 5):

In future posts, we will explore algorithms related to connectivity, we will dig deeper into the importance of weights and will learn some definitions that only make sense when we are talking about directed graphs.

Conclusions

I hope I was able to ignite your passion for Graph theory by driving you through some of the basic definitions that will allow us to build the foundations for learning more complex concepts and applications of graphs.

Some takeaways:

• A graph consists of nodes, and edges which represent relations between the nodes. A path is a sequence of nodes connected by edges. If the path starts and ends on the same node, it is called a cycle.

• A graph is connected if there is a path between any pair of nodes. Otherwise, it is called not connected. The sets of connected nodes are called the connected components of the graph. A tree is a graph that is connected and doesn’t contain cycles.

• Edges in a graph can have direction and weight. The weight of a path is the sum of the weights of the edges that belong to the path.

And if you think this post can be helpful for someone, share it with them. Nothing will make me happier!

See you next week!

---

👋 Hello, I'm Alberto, Software Developer at doWhile, Competitive Programmer, Teacher, and Fitness Enthusiast.

🧡 If you liked this article, consider sharing it.

🔗 All links | Twitter | LinkedIn