Graph Search in JavaScript — I

4 min readMar 13, 2022

A graph is a data structure used to represent the relationship between objects. To give a real world example, we can examine how LinkedIn suggests us new connections.

I’m pretty sure if you are using LinkedIn, you have seen the numbers next to people’s names. 1st, 2nd and 3rd. They indicate how close we are to them in a graph in terms of connection.

Graphs consists of two components:

1. A finite set of vertices

2. A finite set of ordered pair of the form (u, v) called as edge. The pair of (u, v) indicates that there is an edge from vertex u to vertex v.

Types of Graph Data Structure

1- Undirected & Directed Graphs

Directed graphs don’t presume symmetry in edges established between vertices. If there is an edge from Vertex A to Vertex B, it doesn’t mean that the edge connects Vertex B to Vertex A. You can think of it like a genealogical tree.

Undirected graphs are opposite of the directed graphs, if there’s an edge from Vertex A to Vertex B, it also means the edge is connects Vertex B to Vertex A as well.

2- Weighted & Unweighted Graphs

A weighted graph is basically means that edges that carries data such as weight/value/cost. A simple example for this could be the distance between two points.

An example of weighted graphs taken from article

Before we step into creating our Graph in JavaScript, we should observe the two most common ways of representations of graphs.

Representations of Graphs

1. Adjacency Matrix

An adjacency matrix is a two dimensional array of size V x V, where V is the number of the vertices.

We assume that adj is our two dimensional array, we can query the following:

adj[u][v] === 1

The u represents the cell at row and v represents cell at column, our query indicates whether there is an edge from Vertex U to Vertex V at the graph.

Let’s start by creating the adjacency matrix at the example above in JavaScript.

const adjacencyMatrix = [
  [false, true, true, true],
  [true, false, true, false],
  [true, true, false, false],
  [true, false, false, false],
];

While it seem like a good and simple idea, there are cons and pros of using the Adjacency Matrix.

Pros:

Representation is easier
Removing an edge takes O(1)
Queries like above example can be done O(1)

Cons:

It consumes O(V²) space
Adding a vertex is O(V²)

2. Adjacency List

Adjacency list is an array of lists with the size of the number of vertices. The best approach to implement our Adjacency List could be using the hash maps. The vertices will be the keys and the value of each key will be lists of other connected vertices to key.

Creating our adjacency list in JavaScript:

class AdjacencyList {
  private adjList = new Map<string, string[]>();
  
  constructor() {}  // addVertex
  // addEdge
  // getList
}

We have declared a Map called as adjList because we want to store a key and values connected to the key. Map is a great way to do that.

addVertex(v: string) {
  this.adjList.set(v, []);
}

So we have created our method to create vertices, that way we can add edges to it by adding the vertices to the array we created in the map.

addEdge(v: string, w: string) {
  this.adjList.set(v).push(w); // we add an edge from v to w
  
  // as we want it to be undirected we add another edge from w to v
  this.adjList.set(w).push(v);
}

The first parameter indicates the source and the second one is the vertex that we want to connect with. However we are also connecting the vertices with each other as we want our graph to be undirected.

We’re simply creating our method to access list to be used later at our graph.

getList() {
  return this.adjList;
}

Final Code:

export enum GraphType {
  DIRECTED,
  UNDIRECTED,
}class AdjacencyList {
  private adjList = new Map<string, string[]>();
  private graphType: GraphType;  constructor(graphType: GraphType) {
    this.graphType = graphType;
  }  addVertex(v: string) {
    this.adjList.set(v, []);
  }  addEdge(v: string, w: string) {
    this.adjList.get(v)?.push(w);
    
    if (this.graphType === GraphType.UNDIRECTED) {
      this.adjList.get(w)?.push(v);
    }  getList() {
    return this.adjList;
  }
}

Now it’s time to create our graph:

const list = new AdjacencyList(GraphType.UNDIRECTED);
const vertices = ["S", "A", "B", "C", "D"];for (let i = 0; i < vertices.length; i++) {
  list.addVertex(vertices[i]);
}// adding edges
list.addEdge("S", "A");
list.addEdge("S", "B");
list.addEdge("C", "D");
list.addEdge("C", "B");
list.addEdge("C", "E");

That’s it for now but before we end it here, let’s compare it to Adjacency Matrix by reviewing the Pros & Cons.

Pros:

Space efficient, takes O(|V| + |E|)
Easier to add new vertices

Cons:

Queries like (u, v) not efficient and can be done O(V)

That’s it for now, at the next article we will see how we can implement our Adjacency List into Breadth First Search in JavaScript/TypeScript.

Continue reading -> Graph Search in JS: Breadth First Search — 2

References:

Graphs and its representations