Get a gist of graph data structure here...

This blog is for developers who want to get the gist of a concept and not beat around the bush. We will understand graph data structure in this post. Let's start.

What are Graphs?

Graphs are non-linear data structures with 2 components namely edges and nodes.

A node is: -

1. a basic unit of graph,
2. also known as vertex or vertices, and
3. can be labeled or unlabeled.

An edge is:-

1. a connection between two nodes,
2. also known as arcs, and
3. can be labeled or unlabeled.

Types of graph: -

1. Null graph: It has no edges,
2. Trival graph: It has only one node,
3. Cyclic graph: It contains at least one cycle,
4. Cycle graph: All nodes are connected to make one cycle,
5. Directed graph: Its edges have direction,
6. Undirected graph: Its edges do not have any direction,
7. Weighted graph: Some value is assigned to each edge,
8. Connected graph: We can visit any other node from one node (it does not have to be a unique edge),
9. Unconnected graph: At least one node is disconnected from a node,
10. Regular graph: Every vertex has the same number of neighbours,
11. Complete graph: Every node is connected to another node by a unique edge,
12. Directed acyclic graph: A directed graph with no cycles,
13. Bipartite graph: Its nodes can be divided into 2 sets such that no edges exist among the sets.

How do we store graphs?

There are 2 ways:

1. Adjacent matrix, and
2. Adjacent list

The adjacent matrix is a 2-D matrix representing graph data structure. The rows and columns represent nodes and the value in the matrix represents the edges.

In the above image, 4 nodes are connected by the edges. Node A is connected to all the nodes and thus the value is added as 1 in the cells where A (either row or column) intersects with rows or columns of other nodes. Node B is only connected to Node A resulting in a value 1 in the cell where node B intersects with node A and other cells have a value 0.

The time complexity to add or delete an edge for the adjacent matrix is O(1). It can be used when: -

1. the graph has the maximum possible edges,
2. there is no memory constraint, and
3. the graph has a complex structure.

The adjacent list is storing the graph with the help of multiple linked lists or arrays. The rows represent the node (check the image below), and the values present in the rows represent neighbour.

In the above image, there are 5 nodes. Node A is connected to node B and node D which is why the first array has those values. Similarly, node B is connected to node A, node C, node D, and node E and so the second array has those nodes in the second array.

The time complexity for retrieving or deleting an edge is O(n) and the time complexity for adding an edge is O(1). The adjacent list can be used when: -

1. the node has fewer edges,
2. there are memory constraints, and
3. the graph is less complex.

Fig: Visual comparison between adjacent list and adjacent matrix.

Use cases for the graphs

One popular example of graph data structure is: in a field of football each player can be considered a node and their interactions represent edges.

Graphs are used in similar scenarios as previous example, such as: -

1. in social networks where everyone is a node,
2. in computer networks where PCs and routers are the nodes,
3. in the transportation network, and so on...

Comments

[Chris Mitchell]

@vidhithakur thanks for the article, it was a great overview of the graph data structure. Want to point out that I think there a typo where you list the two ways to store graphs. You have adjacent matrix twice.

Thanks again

[vidhi-thakur]

Hi Chris, thank you for your feedback.