Giới thiệu

Graph là một cấu trúc dữ liệu gồm:

• Các đỉnh (Vertices hoặc Nodes)
• Các cạnh (Edges): Kết nối các đỉnh

Các loại graph

Biểu diễn Graph

Adjacency Matrix (ma trận kề)

// A B C D
// 0 1 2 3
const matrix = [
  [0, 1, 1, 0], // A
  [1, 0, 0, 1], // B
  [1, 0, 0, 0], // C
  [0, 1, 0, 0], // D
];

Dựa vào ma trận trên ta thấy:

• A kết nối với B, D (do matrix[0][1]=1 và matrix[0][2]=1).
• B Kết nối với A, D.

Adjacency List (danh sách kề)

const graph = {
  A: ["B", "C"],
  B: ["A", "D"],
  C: ["A"],
  D: ["B"]
};

Ta thấy:

• A kết nối với B, C.
• B kết nối với A, D.

Khởi tạo

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

Khởi tạo các method

addVertex

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

addEdge

 addEdge(v1, v2) {
    this.adjacencyList[v1].push(v2);
    this.adjacencyList[v2].push(v1);
  }

removeVertex

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

    delete this.adjacencyList[vertex];
  }

removeEdge

 removeEdge(v1, v2) {
    this.adjacencyList[v1] = this.adjacencyList[v1]?.filter((v) => v !== v2);
    this.adjacencyList[v2] = this.adjacencyList[v2]?.filter((v) => v !== v1);
  }