Graphs #2: Different Types of Graphs with Practical Examples

As we saw in the previous article, there are various problems in our daily lives that can be solved using graph algorithms. However, different problems may require different approaches.

There are many types and implementations of graphs. In this article, we will take a look at the most important ones.

Where do we use them?

We can use graphs to model, for example:

• Relationships between participants in a social network.
• Flight routes between airports.
• Connections between routers (like those that form the internet).
• Relationships between books/articles (bibliographic reference).
• Relationships between infected individuals in an epidemic (patient A infected patients B, C, D...).

This is the second article in this series on graphs. If you haven’t read the first one, where I introduce the topic in a more introductory manner, I recommend taking a look by clicking here.

Types of Graphs

Before we go crazy implementing a bunch of random code, we need to be very clear in our minds about what is problem we want to solve. This way, we can define which type of graph and the most suitable algorithm should be used for each situation.

Graph problems permeate computer science, and the algorithms to work with them are fundamental to the field. Hundreds of interesting computational problems are addressed using graphs. [1]

As mentioned before, there are various types of graphs. Here, we will discuss the most commonly used ones, alright? So, without further ado, here they are:

Directed Graph

Although the literature usually starts by presenting undirected graphs, I will dare to do it differently. For didactic purposes, I will present the directed ones first. Because I think it’s simpler to understand the logic of undirected graphs afterward, okay?

Let’s think about the routes we take in our daily lives: to home, school, work, etc. Normally, our outbound path is different from our return path. If our journey is on foot or by bicycle, it might even be the same. But by car or bus, the scenario changes because not all the streets we pass through are two-way.

Imagine if the Google Maps algorithm didn’t take into account the direction of the streets when calculating a route... That’s why it’s essential, in this case, to indicate in which direction one can travel between one intersection and another.

You might be wondering: but what if one of these streets is two-way? In that case, you need to consider the segment that can also be traveled in the opposite direction by adding an edge in the opposite direction as shown in the following image.

Everything clear so far? I hope so! Let’s continue...

Undirected Graph

Now let’s think about how we still want to calculate routes, but this time I want to go on foot because, after all, vitamin D and exercise are very beneficial. ☀️

Does it still make sense to consider the direction of the streets to find the best route? Any guesses...?

Let’s look at another case. Remember the example I gave in the previous article, where LinkedIn can calculate the "distance" between us and another member of the network?

Think about it... Does it make sense to model directed relationships between LinkedIn members to calculate the distance between two people in the network?

Well, it really doesn’t make any sense for these relationships to have a direction. In other words, it doesn’t matter if we calculate the distance starting from Gates to reach me or from me to reach him. The result should be the same, right? Let’s move on!

Weighted Graph

Being able to map routes that take us from one place to another is already pretty cool. But you’ll agree with me that being able to also provide the distance and time for the route makes the task even more interesting.

To do this, we need to add some attributes to the edges of our graphs, or weights (hence the name weighted). By adding the distances between each segment, it helps us calculate an average time (it's easy to figure out the average speed at which humans walk).

To calculate the time for a car trip, other variables need to be considered, such as the maximum speed of the roads, adding a new level of complexity. This brings another implication: the shortest path in terms of distance is not always the fastest path to travel. But this is a topic for another post, where we’ll cover some graph algorithms, okay?

Summary

So that’s it, folks, I hope this article has clarified the following points:

1. The type of graph we use depends on the problem we want to solve;
2. There are other types of graphs, the most common being: directed, undirected, and weighted;
3. Both directed and undirected graphs can be weighted; this also depends on the problem;
4. We can have more than one parameter in weighted graphs (distance, maximum speed on the segment, current traffic level, etc.).

I will cover the specific implementation of each type in a future post. However, I’d like to point out that the content covered in the previous article is already sufficient for implementing any of these types of graphs.

Thank you so much for sticking with me through this exploration of graph types! Your time and interest mean a lot, and I hope you’ve found this article both informative and engaging.

If you enjoyed this content and want to stay updated with my latest articles, I invite you to subscribe to my blog. It’s free, and you’ll be notified every time I publish something new.

If you have any questions, thoughts, or even suggestions for future topics, feel free to share them in the comments. I’m always eager to hear from you and continue the conversation. Until next time! 🙂

References

[1] CORMEN, Thomas H. et al. Introduction to algorithms. 3rd ed. MIT press, 2009.

[2] PENTON, Ron. Data structures for game programmers. Premier, 2003.