Adjacency list and matrix in JavaScript
In this article at OpenGenus, I will talk about two common ways of representing a graph, the adjacency list and matrix.
Table of contents:
- Graphs
- Adjacency list
- Adjacency matrix
- Conclusion
1. Graphs
Graphs are non-linear data structures where a node can have zero or more adjacent (neighbor) elements.
A node is also called vertex (or vertices for plural) and the connection between the nodes are called edges.
Graphs can be:
disconnected: When not all nodes are connected.
connected: When all nodes have at least one connection.
complete: When all nodes are connected to all other nodes.
2. Adjacency list
This list is a data structure to represent connections between nodes in a graph, it is one of the ways to represent a graph.
With this, we can store graph data where each node in the graph is associated with a list (array) of its adjacent (neighboring) nodes. It is implemented using an object or a map.
nodeA => [nodeB, nodeC, NodeF, nodeZ, etc...]
In the example above, we can see nodeA and its associated connections.
Let's look at how we can implement an adjacency list using a class.
- Creating a new list (map)
class Graph {
constructor() {
this.list = new Map()
}
}
const graph = new Graph() // {}
Everytime we create a new graph, the constructor will create a map ({}). This map will be our adjacency list. Now, let's add different methods in this class.
- Adding nodes
addNode(node) {
if (!this.list.has(node)) {
this.list.set(node, [])
}
}
graph.addNode(5) // {5 => []}
graph.addNode(3) // {5 => [], 3 => []}
graph.addNode(9) // {5 => [], 3 => [], 9 => []}
If this node doesn't exists yet, then we add this new node inside the list with an empty array value (where the associated nodes will be stored).
- Adding connections
addConnection(node1, node2) {
/* If both nodes exists (for example, in a disconnected graph where not all nodes are connected, where there might be nodes on their own), then we can add a connection from node1 to node2 for example */
if (this.list.has(node1) && this.list.has(node2)) {
this.list.get(node1).push(node2)
} else {
// If node1 exists, then we add node2 inside the node1 array
if (this.list.has(node1) && !this.list.has(node2)) {
// Get the array of node1 and add node2 into it
this.list.get(node1).push(node2)
} else {
// If node1 doesn't exists,
// then we add it to the list and will point to an array containing node2
this.list.set(node1, [node2])
return
}
// If node2 exists, then we add node1 inside the node2 array
if (this.list.has(node2) && !this.list.has(node1)) {
// Get the array of node2 and add node1 into it
this.list.get(node2).push(node1)
} else {
// If node2 doesn't exists,
// then we add it to the list and will point to an array containing node1
this.list.set(node2, [node1])
return
}
}
}
I left comments in the above example to easily understand what each line or block it does. And here is the same example without the comments:
addConnection(node1, node2) {
if (this.list.has(node1) && this.list.has(node2)) {
this.list.get(node1).push(node2)
} else {
if (this.list.has(node1) && !this.list.has(node2)) {
this.list.get(node1).push(node2)
} else {
this.list.set(node1, [node2])
return
}
if (this.list.has(node2) && !this.list.has(node1)) {
this.list.get(node2).push(node1)
} else {
this.list.set(node2, [node1])
return
}
}
}
graph.addConnection(5, 3) // {5 => [3], 3 => [], 9 => []}
graph.addConnection(1, 9) // {5 => [3], 3 => [], 9 => [], 1 => [9]}
graph.addConnection(5, 9) // {5 => [3, 9], 3 => [], 9 => [], 1 => [9]}
- Deleting nodes
deleteNode(node) {
if (this.list.has(node)) {
this.list.delete(node)
for (let [n, connections] of this.list) {
const index = connections.indexOf(node)
if (connections.includes(node)) {
connections.splice(index, 1)
}
}
}
}
// Before: {5 => [3, 9], 3 => [], 9 => [], 1 => [9]}
graph.deleteNode(9)
// After: {5 => [3], 3 => [], 1 => []}
If the node exists in the graph which we want to delete, then we simply call the delete method on the list (which deletes the node). Then we can loop through each node in the list and if the node is found in the array of the associated nodes, then with the splice method we can delete the node as well from the array. You can see, the node number 5 is no longer associated to node number 9, and node n umber 9 is deleted as well.
- Deleting connections
deleteConnection(node1, node2) {
if (this.list.has(node1) && this.list.has(node2)) {
const node1Array = this.list.get(node1)
const node2Array = this.list.get(node2)
const indexOfNode1 = node2Array.indexOf(node1)
const indexOfNode2 = node1Array.indexOf(node2)
if (node1Array.includes(node2)) {
node1Array.splice(indexOfNode2, 1)
}
if (node2Array.includes(node1)) {
node2Array.splice(indexOfNode1, 1)
}
}
}
graph.addConnection(5, 1)
graph.addConnection(1, 5) // { 5 => [ 3, 1 ], 3 => [], 1 => [ 5 ] }
graph.deleteConnection(5, 1) // { 5 => [ 3 ], 3 => [], 1 => [] }
To delete the connection between two nodes, first we check if the two nodes exist in the graph (if not then there's nothing to delete). Then we get each of the node's associated nodes (the array) and check if node1 is in the node2 array and vice versa. If they are inside the array, then they will get deleted with the splice method.
- Checking if two nodes are connected
checkConnection(node1, node2) {
if (this.list.has(node1) && this.list.has(node2)) {
const node1Array = this.list.get(node1)
const node2Array = this.list.get(node2)
if (node1Array.includes(node2) && node2Array.includes(node1)) {
console.log('true')
return
}
console.log('false')
}
}
graph.addConnection(3, 5) // { 5 => [ 3 ], 3 => [5], 1 => [] }
graph.checkConnection(5, 3) // true
graph.checkConnection(5, 1) // false
This example shows if two nodes are connected with each other, checks if the connections are bi-directional (node1 <=> node2). These graphs are called undirected. If they are connected, then we log true to the console and return, otherwise it will log false to the console. Note that if we omit the return keyword, then false would be logged to the console as well no matter if the nodes are connected or not.
We could have another statement to check if two nodes are connected but with one direction (node1 => node2). These graphs are called directed or di-graph. So either node1 is connected to node2, or node2 is connected to node1.
Then the code would look something like this:
checkConnection(node1, node2) {
if (this.list.has(node1) && this.list.has(node2)) {
const node1Array = this.list.get(node1)
const node2Array = this.list.get(node2)
if (node1Array.includes(node2)) {
console.log('true')
return
}
if (node2Array.includes(node1)) {
console.log('true')
return
}
console.log('false')
}
}
- Printing list
printList() {
for (let [node, connections] of this.list) {
console.log(node + "->" + connections)
}
}
graph.printList() // 5 -> 3
3 -> 5
1 ->
To print the list, we need to loop through each node and just print out (log) their associated nodes.
3. Adjacency matrix
Another way of representing a graph is using a two-dimensional array. Where the nodes are connected, we add 1, if they are not then we add 0 or -.
- Creating a new matrix
class Graph {
constructor(numOfNodes) {
this.numOfNodes = numOfNodes;
this.matrix = []
for (let i = 0; i < numOfNodes; i++) {
this.matrix[i] = [];
for (let j = 0; j < numOfNodes; j++) {
this.matrix[i][j] = 0;
}
}
}
const graph = new Graph(5)
/*
numOfNodes: 5,
matrix: [
[ 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0 ]
]
*/
To create a new matrix we need to pass in a number (number of nodes).
Then, with a for loop we create the two-dimensional array. In this example, we passed in the number 5, so we created 5 arrays with 5 elements.
- Adding connections
addConnections(node1, node2) {
if (node1 >= 0 && node1 < this.numOfNodes && node2 >= 0 && node2 < this.numOfNodes) {
this.matrix[node1][node2] = 1
}
}
graph.addConnections(1, 3)
graph.addConnections(0, 2)
graph.addConnections(3, 1)
/*
[ 0, 0, 1, 0, 0 ],
[ 0, 0, 0, 1, 0 ],
[ 0, 0, 0, 0, 0 ],
[ 0, 1, 0, 0, 0 ],
[ 0, 0, 0, 0, 0 ]
*/
Since we already created the nodes (the arrays), we only need to add connections. We check if the two nodes we want to connect are greater or equal than 0 and if they are smaller than the number of nodes. If yes, then we add number 1 in their intersection.
- Deleting connections
deleteConnections(node1, node2) {
if (node1 >= 0 && node1 < this.numOfNodes && node2 >= 0 && node2 < this.numOfNodes) {
this.matrix[node1][node2] = 0
}
}
graph.deleteConnections(0, 2)
/*
[ 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 1, 0 ],
[ 0, 0, 0, 0, 0 ],
[ 0, 1, 0, 0, 0 ],
[ 0, 0, 0, 0, 0 ]
*/
This method is very similar to the addingConnections method, the only thing we need to change here is to replace number 1 with the number 0.
- Deleting nodes
deleteNode(node) {
if (node >= 0 && node < this.numOfNodes) {
this.matrix.splice(node, 1);
this.numOfNodes--;
for (let i = 0; i < this.numOfNodes; i++) {
this.matrix[i].splice(node, 1)
}
}
}
graph.deleteNode(2)
/*
numOfNodes: 4,
matrix: [
[ 0, 0, 0, 0 ],
[ 0, 0, 1, 0 ],
[ 0, 1, 0, 0 ],
[ 0, 0, 0, 0 ]
]
*/
If we want to delete nodes, then we can do that with the splice method and we also need to decrement the number of nodes by one. Also, we need to delete one element from each array.
- Checking if two nodes are connected
checkConnection(node1, node2) {
if (this.matrix[node1][node2] === 1) {
console.log('true')
return
}
console.log('false')
}
graph.checkConnection(2, 1) // true
graph.checkConnection(2, 0) // false
This is one example of checking if two nodes are connected.
Of course, we could check if they are connected bi-directionally:
checkConnection(node1, node2) {
if (this.matrix[node1][node2] === 1) {
console.log('true')
return
}
if (this.matrix[node2][node1] === 1) {
console.log('true')
return
}
console.log('false')
}
- Printing the matrix
printMatrix() {
for (let i = 0; i < this.numOfNodes; i++) {
const row = this.matrix[i].join(' ')
console.log(row)
}
}
graph.printMatrix()
/*
0 0 0 0 0
0 0 0 1 0
0 1 0 0 0
0 0 0 0 0
*/
Here, we just print out each node (each array) in one separate line.
4. Conclusion
Now you know how to implement an adjacency list and matrix to store graph data. You see, my examples were simple and the methods are not complex at all. If you have to work with graphs or graph related data, then it's up to you how you want to represent the graph, using a list or a two-dimensional array.
Here you can check out the full example:
List: https://github.com/virag-ky/OpenGenus/blob/main/data-structures/graphs/adjacencyList.js
Matrix: https://github.com/virag-ky/OpenGenus/blob/main/data-structures/graphs/adjacencyMatrix.js