Tạo đồ thị trong Javascript

Chúng tôi sẽ tạo một lớp biểu đồ hỗ trợ trọng số và cả loại có hướng và không được định hướng. Điều này sẽ được thực hiện bằng cách sử dụng danh sách gần kề. Khi chúng ta chuyển sang các khái niệm nâng cao hơn, cả trọng số và bản chất có hướng của đồ thị sẽ có ích.

Danh sách kề là một mảng A gồm các danh sách riêng biệt. Mỗi phần tử của mảng Ai là một danh sách, chứa tất cả các đỉnh kề với đỉnh i. Chúng tôi đang xác định nó bằng cách sử dụng 2 thành viên, nút và cạnh.

Hãy thiết lập lớp đồ thị bằng cách xác định lớp của chúng ta và một số phương pháp mà chúng ta sẽ sử dụng để thêm các nút và cạnh vào đồ thị của chúng ta.

Ban đầu chúng tôi sẽ xác định các phương pháp sau -

• addNode:Thêm một nút vào biểu đồ
• addEdge:Thêm một cạnh vô hướng vào biểu đồ
• addDiirectEdge:Thêm cạnh được định hướng

Ví dụ

class Graph {
   constructor() {
      this.edges = {};
      this.nodes = [];
   }
   addNode(node) {
      this.nodes.push(node);
      this.edges[node] = [];
   }
   addEdge(node1, node2) {
      this.edges[node1].push(node2);
      this.edges[node2].push(node1);
   }
   addDirectedEdge(node1, node2) {
      this.edges[node1].push(node2);
   }
   display() {
      let graph = ""; this.nodes.forEach(node => {
         graph += node + "->" + this.edges[node].join(", ") + "\n";
      });
      console.log(graph);
   }
}

Bạn có thể kiểm tra các phương pháp này và lớp của chúng tôi bằng cách sử dụng -

Ví dụ

let g = new Graph();
g.addNode("A");
g.addNode("B");
g.addNode("C");
g.addNode("D");
g.addNode("E");
 
g.addEdge("A", "C");
g.addEdge("A", "B");
g.addDirectedEdge("A", "D");
g.addEdge("D", "E");

g.display();

Đầu ra

Điều này sẽ cung cấp đầu ra -

A->C, B, D
B->A
C->A
D->E
E->D