DEV Community

vidhi-thakur
vidhi-thakur

Posted on

1 1

Get a gist of graph data structure here...

hello

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.

graph visual representation

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.

adjacent matrix

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.

adjacent list
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.

comparson

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...

Do your career a big favor. Join DEV. (The website you're on right now)

It takes one minute, it's free, and is worth it for your career.

Get started

Community matters

Top comments (2)

Collapse
 
chrismitchell profile image
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

Collapse
 
vidhithakur profile image
vidhi-thakur •

Hi Chris, thank you for your feedback.

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more

đź‘‹ Kindness is contagious

Immerse yourself in a wealth of knowledge with this piece, supported by the inclusive DEV Community—every developer, no matter where they are in their journey, is invited to contribute to our collective wisdom.

A simple “thank you” goes a long way—express your gratitude below in the comments!

Gathering insights enriches our journey on DEV and fortifies our community ties. Did you find this article valuable? Taking a moment to thank the author can have a significant impact.

Okay