Graph | Javascript | Part-7.1

Introduction article to the data structure. Graph concept with practical examples applied to the Javascript language.

Are you looking to improve your fundamental knowledge of computer science, especially data structure and algorithms? Then you’re in the right place. Let’s go through some common data structures and implement them in JavaScript.

Graph

Graphs are a data structure formed by a group of nodes and certain connections between those nodes. Unlike trees, graphs don’t have root and leaf nodes, nor a “head” or a “tail”. Different nodes are connected to each other and there’s no implicit parent-child connection between them.

Graphs are data structures often useful for:

• Social networks
• Geolocalization
• Recommendation systems

Graphs can be classified into different types according to the characteristics of the connections between nodes:

Undirected and directed graphs

We say a graph is undirected if there’s no implicit direction in the connections between nodes.

If we take the following example image, you can see that there’s no direction in the connection between node 2 and node 3. The connection goes both ways, meaning you can traverse the data structure from node 2 to node 3, and from node 3 to node 2. Undirected means the connections between nodes can be used both ways.

An undirected graph

And as you may have guessed, directed graphs are the exact opposite. Let’s reuse the previous example image, and see that here there’s an implicit direction in the connections between nodes.

In this particular graph, you could traverse from node A to node B, but you can’t go from node B to A.

A directed graph

Weighted and unweighted graphs

We say a graph is weighted if the connections between nodes have an assigned weight. In this case, the weight just means a value that is assigned to a specific connection. It’s information about the connection itself, not about the nodes.

Following this example, we can see the connection between nodes 0 and 4, has a weight of 7. And the connection between nodes 3 and 1 has a weight of 4.

A weighted graph

To understand the use of weighted graphs, imagine if you wanted to represent a map with many different locations, and give the user information about how long it might take them to go from one place to another.
A weighted graph would be perfect for this, as you could use each node to save information about the location, the connections could represent the available roads between each place, and the weights would represent the physical distance from one place to another.
And as you may have guessed once again, unweighted graphs are the ones where connections between nodes have no assigned weights. So there’s no particular information about the connections between nodes, only about the nodes themselves.

How to represent graphs

When coding graphs, there’re two main methods we can use an adjacency matrix and an adjacency list. Let’s explain how both work and see their pros and cons.

An adjacency matrix is a two-dimensional structure that represents the nodes in our graph and the connections between them.

If we use this example…

Our adjacency matrix would look like this:

You can see that the matrix is like a table, where columns and rows represent the nodes in our graph, and the value of the cells represents the connections between nodes. If the cell is 1, there’s a connection between the row and the column, and if it’s 0, there’s not.

The table could be easily replicated using a two-dimensional array:

[
    [0, 1, 1, 0]
    [1, 0, 0, 1]
    [1, 0, 0, 1]
    [0, 1, 1, 0]
]

On the other hand, an adjacency list can be thought of as a key-value pair structure where keys represent each node on our graph and the values are the connections that that particular node has.

Using the same example graph, our adjacency list could be represented with this object:

{
    A: ["B", "C"],
    B: ["A", "D"],
    C: ["A", "D"],
    D: ["B", "C"],
}

You can see that for each node we have a key, and we store all the node’s connections within an array.

So what’s the difference between adjacency matrices and lists? Well, lists tend to be more efficient when it comes to adding or removing nodes, while matrices are more efficient when querying for specific connections between nodes.

To see this, imagine we wanted to add a new node to our graph:

To represent this in a matrix, we would need to add a whole new column and a whole new row:

While to do the same in a list, adding a value to B connections and a key-value pair to represent E is enough:

{
    A: ["B", "C"],
    B: ["A", "D", "E"],
    C: ["A", "D"],
    D: ["B", "C"],
    E: ["B"],
}

Now imagine we want to verify if there’s an existing connection between node B and E. Checking that in a matrix is dead easy, as we know exactly the position in the matrix that represents that connection.
But in a list, we don’t have that information we would need to iterate all over the array that represents B connections and see what’s in there. So you can see there are pros and cons for each approach.

The adjacency matrix shows nodes in rows and columns. Intersections of the row and column interpret the relationship between nodes: 0 means not linked, 1 means linked and >1 means different weightage.

Illustration of the adjacency matrix

To query for nodes in a graph, one must search through the entire tree network with either the breadth-first-search (BFS) method or the depth-first-search (DFS) method.

Let’s see an example (Leetcode problems) of BFS in Javascript:

Leetcode Solutions | Platform for learning to code

Let’s see an example (Leetcode problems) of DFS in Javascript:

Leetcode Solutions | Platform for learning to code

Recent Articles if you guys want to checkout

AVL Tree | Javascript | Part-6.5

Trie | Javascript | Part-6.4

Heaps | Javascript | Part-6.3

In this blog, I have tried to collect & present the most important points to consider when building Javascript / Node.js applications, feel free to add, edit, comment, or ask.
I recommend you to go over the references for more details. Happy coding!