ivangeorgiev.dev

Introduction to data structures: Graph

Learn about the graph data structure in an intuitive way

November 29th, 2024 3 minute read

The graph data structure is another non-linear data structure. It's similar to the tree data structure, but we could say that it's even more non-linear. 😀
Let's learn what the graph data structure is and how it works.

How is the graph data structure different from the tree data structure?
The difference lies in the ability of the nodes to have more than one node that links to them. If you remember, every node in the tree data structure has a single node that links to it (i.e. it has a single parent). In the graph data structure, there could be multiple nodes that link to a single node.
Below is an image showing a tree data structure (on the top) and a graph data structure (on the bottom).

Tree data structure
Image taken from: https://www.drawio.com/

As can be seen, the nodes 2 and 3 have more than one node linking to them.

There are different types of graphs depending on certain properties. Let's give a few examples:

The graph data structure usually provides the following operations:

Let's give a few practical uses of the graph data structure:

How do graphs work internally?
The graph data structure can use arrays or linked lists internally. In the most general case, the graph data structure can be created using nodes that have a linked list that contains links to other nodes. The nodes have to "hold" the data as well.

In future articles we will cover some of the different algorithms that are used to search/traverse graphs.

If you enjoy my articles, please consider supporting me.