# [DSA] Graphs

# 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
    

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1750257761331/dfff0d5e-8dcf-4db2-bc84-4bdfceb4c776.png align="center")

## Các loại graph

| **Loại** | **Đặc điểm** |
| --- | --- |
| Directed graph (Đồ thị có hướng) | Cạnh có hướng (A→B). |
| Undirected graph (Đồ thị vô hướng) | Cạnh không có hướng (A↔B). |
| Weighted Graph (Độ thị có trọng số) | Mỗi cạnh có một giá trị (khoảng cách, chi phí). |
| Unweighted Graph (Độ thị không có trọng số) | Các cạnh không có giá trị gắn kèm. |

## Biểu diễn Graph

### Adjacency Matrix (ma trận kề)

```jsx
// 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ề)

```jsx
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

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

# Khởi tạo các method

## addVertex

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

## addEdge

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

## removeVertex

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

    delete this.adjacencyList[vertex];
  }
```

## removeEdge

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