Implementation of graphs in JavaScript

A graph is a nonlinear data structure that represents a set of vertices (also called nodes) and the relationships (or edges) between them. Vertices represent entities or objects, while edges represent relationships or connections between vertices. Graphs can be used to model many different types of relationships, such as social networks, transportation systems, or information flows.

There are two main types of graphs: Directed graphs (also called directed graphs) and Undirected graphs. In a directed graph, edges have one direction and can only be traversed in one direction, i.e. from the starting vertex to the ending vertex. In an undirected graph, the edges have no direction and can be traversed in both directions.

JavaScript CTU implementation

Graphs can be implemented using adjacency matrices or adjacency lists. Here we will implement graphs in JavaScript using adjacency lists.

Create chart class

Here we create a blueprint of the graphics class.

class Graph {
   constructor() {
      this.adjacencyList = {};
   }
}

Add vertices

This function adds a new vertex (or node) to the graph by creating a new key in the adjacencyList object and giving an empty array as its value. The new vertex will serve as the key and the empty array will be used to store its neighbors.

addVertex(vertex) {
   if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
}

Add edge

This function adds a new edge between two vertices. It accepts two parameters: vertex1 and vertex2, and adds vertex2 to vertex1's neighbors array and vice versa. This creates a connection between the two vertices.

addEdge(vertex1, vertex2) {
   this.adjacencyList[vertex1].push(vertex2);
   this.adjacencyList[vertex2].push(vertex1);
}

Print chart

This function logs the chart to the console. It iterates over each vertex in the adjacencyList object and records the vertex and its neighbors.

print() {
   for (const [vertex, edges] of Object.entries(this.adjacencyList)) {
      console.log(`${vertex} -> ${edges.join(", ")}`);
   }
}

Example

In the following example, we define a graph and add vertices and edges to the graph. Finally print the chart.

class Graph {
   constructor() {
      this.adjacencyList = {};
   }
   addVertex(vertex) {
      if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
   }
   addEdge(vertex1, vertex2) {
      this.adjacencyList[vertex1].push(vertex2);
      this.adjacencyList[vertex2].push(vertex1);
   }
   print() {
      for (const [vertex, edges] of Object.entries(this.adjacencyList)) {
         console.log(`${vertex} -> ${edges.join(", ")}`);
      }
   }
}
const graph = new Graph();
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addVertex("D");
graph.addEdge("A", "B");
graph.addEdge("A", "C");
graph.addEdge("B", "D");
graph.addEdge("C", "D");
console.log("Graph:");
graph.print();

Output

Graph:
A -> B, C
B -> A, D
C -> A, D
D -> B, C

Delete edge

This function deletes the edge between two vertices. It takes two arguments: vertex1 and vertex2, and filters out vertex2 from vertex1's neighbor array and vice versa.

removeEdge(vertex1, vertex2) {
   this.adjacencyList[vertex1] = this.adjacencyList[vertex1].filter(
      (v) => v !== vertex2
   );
   this.adjacencyList[vertex2] = this.adjacencyList[vertex2].filter(
      (v) => v !== vertex1
   );
}

Delete vertices

This function deletes a vertex from the graph. It takes a vertex argument and first removes all edges connected to that vertex. Then, it removes the key from the adjacencyList object.

removeVertex(vertex) {
   while (this.adjacencyList[vertex].length) {
      const adjacentVertex = this.adjacencyList[vertex].pop();
      this.removeEdge(vertex, adjacentVertex);
   }
   delete this.adjacencyList[vertex];
}

Example

In the following example, we define a graph and add vertices and edges, then print the graph. We remove an edge AC from the graph and finally print the resulting graph.

class Graph {
   constructor() {
      this.adjacencyList = {};
   }
   addVertex(vertex) {
      if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
   }
   addEdge(vertex1, vertex2) {
      this.adjacencyList[vertex1].push(vertex2);
      this.adjacencyList[vertex2].push(vertex1);
   }
   removeEdge(vertex1, vertex2) {
      this.adjacencyList[vertex1] = this.adjacencyList[vertex1].filter(
         (v) => v !== vertex2
      );
      this.adjacencyList[vertex2] = this.adjacencyList[vertex2].filter(
         (v) => v !== vertex1
      );
   }
   removeVertex(vertex) {
      while (this.adjacencyList[vertex].length) {
         const adjacentVertex = this.adjacencyList[vertex].pop();
         this.removeEdge(vertex, adjacentVertex);
      }
      delete this.adjacencyList[vertex];
   }
   print() {
      for (const [vertex, edges] of Object.entries(this.adjacencyList)) {
         console.log(`${vertex} -> ${edges.join(", ")}`);
      }
   }
}
const graph = new Graph();
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addVertex("D");
graph.addEdge("A", "B");
graph.addEdge("A", "C");
graph.addEdge("B", "D");
graph.addEdge("C", "D");
console.log("Initial Graph:");
graph.print();
console.log("Graph after removal of edge AC:")
graph.removeEdge("A","C");
graph.print();

Output

Initial Graph:
A -> B, C
B -> A, D
C -> A, D
D -> B, C
Graph after removal of edge AC:
A -> B
B -> A, D
C -> D
D -> B, C

Graph traversal method

Graph traversal refers to the process of visiting all vertices (or nodes) of the graph and processing the information associated with them. Graph traversal is an important operation in graph algorithms and is used for tasks such as finding the shortest path between two nodes, detecting cycles, and finding connected components.

There are two main methods for graph traversal: Breadth First Search (BFS) and Depth First Search (DFS)

A. Breadth First Search (BFS)

It is implemented using breadthFirstSearch() function. This function implements the breadth-first search algorithm and takes the start parameter, which is the starting vertex. It uses a queue to keep track of vertices to be visited, a result array to store visited vertices, and a visit object to keep track of vertices that have already been visited. The function first adds the starting vertex to the queue and marks it as visited. Then, when the queue is not empty, it takes the first vertex from the queue, adds it to the result array, and marks it as visited. It then adds all unvisited neighbors to the queue. This process continues until all vertices have been visited and the resulting array is returned as the result of the BFS.

breadthFirstSearch(start) {
   const queue = [start];
   const result = [];
   const visited = {};
   let currentVertex;
   visited[start] = true;
   while (queue.length) {
      currentVertex = queue.shift();
      result.push(currentVertex);
         this.adjacencyList[currentVertex].forEach((neighbor) => {
            if (!visited[neighbor]) {
               visited[neighbor] = true;
               queue.push(neighbor);
            }
         });
      }
      return result;
   }
}

B. Depth first search

The depth-first search method implements the DFS algorithm by using the recursive inner function dfs that takes vertices as arguments. The function uses the visited object to keep track of the visited vertices and adds each visited vertex to the result array. The function first marks the current vertex as visited and adds it to the result array. It then iterates over all neighbors of the current vertex and recursively calls the dfs function for each unvisited neighbor. This process continues until all vertices have been visited and the resulting array is returned as the result of DFS.

depthFirstSearch(start) {
   const result = [];
   const visited = {};
   const adjacencyList = this.adjacencyList;
   (function dfs(vertex) {
      if (!vertex) return null;
      visited[vertex] = true;
      result.push(vertex);
      adjacencyList[vertex].forEach(neighbor => {
         if (!visited[neighbor]) {
            return dfs(neighbor);
         }
      });
   })(start);
   return result;
}

Example

In the following examples, we demonstrate breadth-first search (BFS) and depth-first search (DFS).

class Graph {
   constructor() {
      this.adjacencyList = {};
   }
   addVertex(vertex) {
      if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
   }
   addEdge(vertex1, vertex2) {
      this.adjacencyList[vertex1].push(vertex2);
      this.adjacencyList[vertex2].push(vertex1);
   }
   print() {
      for (const [vertex, edges] of Object.entries(this.adjacencyList)) {
         console.log(`${vertex} -> ${edges.join(", ")}`);
      }
   }
   breadthFirstSearch(start) {
      const queue = [start];
      const result = [];
      const visited = {};
      let currentVertex;
      visited[start] = true;
      while (queue.length) {
         currentVertex = queue.shift();
         result.push(currentVertex);
         this.adjacencyList[currentVertex].forEach((neighbor) => {
            if (!visited[neighbor]) {
               visited[neighbor] = true;
               queue.push(neighbor);
            }
         });
      }
      return result;
   }
   depthFirstSearch(start) {
      const result = [];
      const visited = {};
      const adjacencyList = this.adjacencyList;
      (function dfs(vertex) {
         if (!vertex) return null;
         visited[vertex] = true;
         result.push(vertex);
         adjacencyList[vertex].forEach(neighbor => {
            if (!visited[neighbor]) {
               return dfs(neighbor);
            }
         });
      })(start);
      return result;
   }
}
const graph = new Graph();
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addVertex("D");
graph.addEdge("A", "B");
graph.addEdge("A", "C");
graph.addEdge("B", "D");
graph.addEdge("C", "D");
console.log("Initial Graph:");
graph.print();
console.log("BFS: "+graph.breadthFirstSearch('A'));
console.log("DFS: "+graph.depthFirstSearch('A'));

Output

Initial Graph:
A -> B, C
B -> A, D
C -> A, D
D -> B, C
BFS: A,B,C,D
DFS: A,B,D,C

in conclusion

A graph is a useful data structure that can be used to represent relationships and connections between objects. Implementing graphs in JavaScript can be done using a variety of techniques, including using adjacency lists or adjacency matrices. The Graph class demonstrated in this answer uses an adjacency list representation, where each vertex is stored as a key in an object and its corresponding edge is stored as the value of that key in an array.

The Graph class implements methods for adding vertices and edges to a graph, printing the graph, and performing depth-first search and breadth-first search traversals.

The above is the detailed content of Implementation of graphs in JavaScript. For more information, please follow other related articles on the PHP Chinese website!