DEV Community

Cover image for Graph Representation
codebond
codebond

Posted on • Originally published at codebond.co

4 2

Graph Representation

In Introduction To Graph Data Structure, we learned

In this tutorial, we gonna see two common and recommended ways to represent a graph.

  • Adjacency matrix
  • Adjacency List

If i asked what are adjacent node of node "A"? you will find all neighbors connected to node "A" by just looking at the graph.

But the question is how the computer will understand the graph and adjacent of node "A" 🤔???

Well, bear with me, we will make sure that computer understands the graph.

Adjacency Matrix

An adjacency matrix is a 2-dimensional array of size N x N where N is the number of the node.

let 2-dimensional array be adj[ i ][ j ] .

adj[ i ][ j ] = 1 means there is edge between node "i" and "j".

adj[ i ][ j ] = 0 means there no edge between node "i" and "j".

lets understand by above example:

adj[ 0 ][ 0 ] = 0 (edge between node 0 and 0)

adj[ 0 ][ 1 ] = 1 (edge between node 0 and 1)

adj[ 0 ][ 2 ] = 0 (no edge between node 0 and 2)

adj[ 0 ][ 3 ] = 1 (edge between node 0 and 3)

adj[ 0 ][ 4 ] = 1 (edge between node 0 and 4)

adj[ 0 ][ 5 ] = 0 (no edge between node 0 and 5)

similarly for other node....

Representation of graph by Adjacency Matrix: javascript

initialize()

It creates a 2-dimensional array and sets the adjmatrix[row][coloumn] to 0 which means there is no edge between any node.

addEdge()

It creates an edge between source and destination and destination and source.

Adjacency List

In graph theory and computer science, an adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a vertex in the graph. __Wikipedia

In simple words
In Adjacency List each Node will have a list(array) of his adjacent(neighbor) nodes.

Representation of graph by Adjacency List: javascript

addNode()

It creates a new node with an empty list.

addEdge()

It creates an edge between source and destination by pushing the destination node to the list of the source.

This post first published on codebond

Postmark Image

Speedy emails, satisfied customers

Are delayed transactional emails costing you user satisfaction? Postmark delivers your emails almost instantly, keeping your customers happy and connected.

Sign up

Top comments (0)

The Most Contextual AI Development Assistant

Pieces.app image

Our centralized storage agent works on-device, unifying various developer tools to proactively capture and enrich useful materials, streamline collaboration, and solve complex problems through a contextual understanding of your unique workflow.

👥 Ideal for solo developers, teams, and cross-company projects

Learn more

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay