Introduction to data structures: Graph
Learn about the graph data structure in an intuitive way
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).
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:
- Undirected graph - If node A has a link to node B, node B automatically has a link to node A.
- Directed graph - If node A has a link to node B, node B does not automatically have a link to node A.
- Cyclic graph - A graph in which there is a cycle. For example, node A has a link to node B, node B has a link to node C and node C has a link to node A. We can go from A to B to C and to A again and form a cycle.
- Weighted graph - A graph in which the edges between the nodes have a "weight" associated with them. For example, the edge from node A to node B could have a weight of 5, but the edge from node A to node C could have a weight of 10.
The graph data structure usually provides the following operations:
- add node - used to insert a node into the graph.
- remove node - used to remove a node from the graph.
- add edge - used to add an edge between two nodes in the graph.
- remove edge - used to remove an edge between two nodes in the graph.
- find - used to find a node in the graph.
- traverse - used to traverse every node in the graph.
Let's give a few practical uses of the graph data structure:
- Search engine - Every website can have multiple websites that link to it and it can link to multiple websites. All these websites and the links between them form a graph. A search engine can use a graph data structure to rank a website according to the number of links that point to it.
- Maps application - Geographical locations (e.g. cities) are connected to other geographical locations by different means (e.g. roads). These geographical locations and the connections between them form a graph. We can use a graph data structure to find a route from one location to another. We can find the cheapest route if the graph is weighted and the weight between the nodes represents the price to travel from one location to another.
- Finite-state machine - A finite-state machine is a machine (it does not have to be a physical machine, it can be computer program) that can be in one of a finite number of states. It can move from one state to another based on some rules. The different states and the connections between them from a graph.
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.