Tạo Graph trong JavaScript

Chúng ta sẽ tạo một class Graph hỗ trợ trọng số và cả hai loại directed/undirected. Sẽ triển khai bằng danh sách kề (adjacency list). Khi chuyển sang khái niệm nâng cao, cả trọng số và bản chất directed của đồ thị sẽ hữu ích.

Danh sách kề là một mảng A 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 ta định nghĩa nó bằng 2 thành viên: nodes và edges.

Hãy thiết lập class Graph bằng cách định nghĩa class và một số phương thức để thêm nút và cạnh vào đồ thị.

Ban đầu sẽ định nghĩa các phương thức sau:

• addNode: Thêm nút vào đồ thị
• addEdge: Thêm cạnh vô hướng vào đồ thị
• addDirectedEdge: Thêm cạnh có 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 thức và class này bằng cách sau:

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();

Kết quả

Điều này sẽ cho ra kết quả:

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