Data Structures 101: introducing graphs in JavaScript
In computer programming, data structures are used to organize data and apply algorithms (or commands) to code. Having a good understanding of data structures is essential for coding beginners and senior devs alike. In fact, questions related to data structures are some of the most common for entry-level interviews.
Today we will be looking at the graph data structure, one of the most widely-used data structures with applications across computing, mathematics, and other related fields.
Master data structures for coding interviews with hands-on practice
Learn all about graphs by studying real-world coding interview challenges
What is a graph?#
When we talk about graphs, the first thing that likely comes to mind is the conventional graphs used to model data. In computer science, the term has a completely different meaning.
In programming, a graph is a common data structure that consists of a finite set of nodes (or vertices) and edges. The edges connect the vertices to form a network. An edge can be uni-directional or bi-directional. Edges are also known as arrows in a directed graph and may contain values that show the required cost to traverse from one vertex to another.
A vertex is similar to linked list nodes. A pair (x,y) is referred to as an edge. This communicates that the x vertex connects to the y vertex.
Graph terminology#
Let’s explore some common terminologies you’ll come across when working with graphs. To be successful with graphs, it’s important to understand the key terms to develop a grasp of how the different properties interact with each other relationally. Let’s take a look.
Degree of a vertex: The total number of edges connected to a vertex. There are two types of degrees:
-
In-Degree: The total number connected to a vertex.
-
Out-Degree: The total of outgoing edges connected to a vertex.
Adjacency: Two vertices are said to be adjacent if there is an edge connecting them directly.
Parallel Edges: Two undirected edges are parallel if they have the same end vertices. Two directed edges are parallel if they have the same origin and destination.
Self Loop: This occurs when an edge starts and ends on the same vertex.
Isolated vertex: A vertex with zero degree, meaning it is not an endpoint of an edge.
There are two common types of graphs. In an undirected graph, the edges are bi-directional by default; for example, with the pair (0,1), it means there exists an edge between vertex 0 and 1 without any specific direction. You can go from vertex 0 to 1, or vice versa.
Say we wanted to calculate the maximum possible edges for an undirected graph. The maximum possible edges of a graph with n vertices will be all possible pairs of vertices. There are possible pairs of vertices, according to Combinatorics. Solving by binomial coefficients gives us , so there are maximum possible edges in an undirected graph.
In a directed graph, the edges are unidirectional; for example, with the pair (0,1), it means there exists an edge from vertex 0 towards vertex 1, and the only way to traverse is to go from 0 to 1.
This changes to the number of edges that can exist in the graph. For a directed graph with vertices, the minimum number of edges that can connect a vertex with every other vertex is . So, if you have n vertices, then the possible edges is .
Types of graph representations#
We can represent a graph in different ways when trying to solve problems in our systems. In this section, we will take a look at the two most commonly used representations: Adjacency List and Adjacency Matrix.
Adjacency Matrix#
The adjacency matrix is a two-dimensional matrix where each cell can contain a 0 or a 1. The row and column headings represent the source and destination vertices respectively. If a cell contains 1, that means there’s an edge between the corresponding vertices. Edge operations are performed in constant time, as we only need to manipulate the value in the particular cell.
Master data structures for coding interviews.#
Learn data structures and algorithms in JavaScript without scrubbing through videos or documentation. Educative’s text-based courses are easy to skim and feature live coding environments, making learning quick and efficient.
Adjacency List#
In an Adjacency List, an array of Linked Lists is used to store edges between two vertices. The size of the array is equal to the number of vertices. Each index in this array represents a specific vertex in the graph. If a new vertex is added to the graph, it is simply added to the array as well.
Adding an edge and a vertex to the Adjacency List is also a time-constant operation. Removing an edge takes time because–in the worst case–all the edges could be at a single vertex. Therefore, we would traverse all E edges to reach the last one. Removing a vertex takes time because we have to delete all its edges and then reindex the rest of the list one step back.
Use cases: Both representations are suitable for different situations. If your model frequently manipulates vertices, the adjacency list is a better choice. If you are dealing primarily with edges, the adjacency matrix is the more efficient approach.
How to implement a graph in JavaScript#
We’ve taken a look at graphs from a theoretical viewpoint. Let’s now try to implement a graph in code. After all, the best way to learn data structures is to use them with real data. The implementation below uses JavaScript and will be based on the Adjacency List representation.
As we know, the Graph class consists of two data members:
- The total number of vertices in the graph
- An array of linked lists to store adjacent vertices
class Graph{constructor(vertices){//Total number of vertices in the graphthis.vertices=vertices;//Defining an array which can hold LinkedLists equal to the number of vertices in the graphthis.list=[];//Creating a new LinkedList for each vertex/index of the listfor(i=0; i<vertices.length; i++){let temp=new LinkedList();this.list.push(temp);}}}
Here, we’ve laid down the foundation of our Graph class. The variable vertices contains an integer specifying the total number of vertices. The second component is an array, which will act as our adjacency list. We simply have to run a loop and create a linked list for each vertex. Now, we’ll add two methods to make this class functional:
printGraph(): This prints the contents of the graphaddEdge(): This connects a source with a destination
"use strict";module.exports = class Node {constructor(data) {this.data = data;this.nextElement = null;}}
addEdge (source, destination)#
Source and destination are already stored as index of our array. This function inserts a destination vertex into the adjacency linked list of the source vertex using the following line of code:
this.list[source].insertAtHead(destination)
We implementing a directed graph, so addEdge(0, 1) does not equal addEdge(1, 0).
printGraph()#
This function uses a nested loop to iterate through the adjacency list. Each linked list is being traversed.
What about an undirected graph?
So far, we have covered the implementation of a directed graph.
For an undirected graph, we we create an edge from the source to the destination and from the destination to the source. This makes it a bidirectional edge.
Graph traversal algorithms#
As we have previously mentioned, when we move through a graph, we are traversing the data. This refers to the process of visiting the vertices of a graph. Traversal processes are classified by the order that the vertices are visited. This is similar to tree traversal. Let’s get into the basic logic behind graph traversal and see how we can use algorithms to do it.
When traversing graphs, we use the concept of levels. Take a vertex as your starting point; this is the lowest level. The next level is all the adjacent vertices. A level higher would be the vertices adjacent to these nodes.
The two basic techniques for graph traversal are:
-
Breadth-First Search (BFS): The BFS algorithm grows breadth-wise. All the nodes at a certain level are traversed before moving on to the next level. This level-wise expansion ensures that for any starting vertex, you can reach all others one level at a time.
-
Depth-First Search (DFS): This algorithm is the opposite of BFS; it grows depth-wise. Starting from any node, we move to an adjacent node until we reach the farthest level. Then we move back to the starting point and pick another adjacent node. Once again, we probe to the farthest level and move back. This process continues until all nodes are visited.
Real-world uses of graphs#
Graphs are used to solve real-life problems that involve representation of the problem space as a network. Any network related application (paths, finding relationships, routing, etc.) apply the concept of graphs. Therefore, the graph data structure plays a fundamental role in several applications:
- GPS
- Neural networks
- Peer to peer networks
- Search engine crawlers
- Garbage collection
- Social networking websites
- and more
For example, a single user on Facebook can be represented as a node (vertex), while their connection with others can be represented as an edge between nodes, and each node can be a structure that contains information like the user’s id, name, location, etc.
Graphs are being used to improve the efficiency of the applications we use daily. These are a fundamental part of our day-to-day lives.
-
Facebook Graph API, for example, uses the concept of graphs, where users are considered to be the vertices and an edge runs between friends and other entities such as comments, photos, notes etc.
-
Google Maps, similarly, bases their navigation system on graphs. An intersection of two or more roads is considered to be a vertex and the road connecting two vertices is considered to be an edge. This way, they can calculate the shortest path between two vertices.
-
Most eCommerce websites like Amazon use relationships between products to show recommendations to a user. This utilizes the network-structure of graphs to make connections and suggestions about related content.
Wrap up and next steps#
Congratulations on making it to the end of this tutorial! We hope this has helped you better understand graphs. There’s still so much to learn about data structures. Here are some of the common data structures challenges you should look into to get a better sense of how to use graphs.
- Implement Breadth-First search
- Implement Depth-First search
- Find a “Mother Vertex” in a graph
- Count the number of edges in a graph
- and more
To get started learning these challenges, check out Data Structures for Coding Interviews in JavaScript, which breaks down all the data structures common to JavaScript interviews using hands-on, interactive quizzes and coding challenges. This course gets you up-to-speed on all the fundamentals of computer science in an accessible, personalized way.
Continue reading about data structures and JavaScript#
Free Resources
