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
Top comments (0)