# Các kỹ thuật xử lý trên graph


## Kỹ thuật biểu diễn

### Ma trận kề

Sử dụng một mảng boolean 2 chiều: $connect[i][j]$. $connect[i][j]$ sẽ mang giá trị $true$ nếu có cạnh nối hai đỉnh $i$ và $j$.

* (+) Hiệu quả khi số đỉnh ít, số cạnh lớn.
* (+) Hiệu quả khi cần truy vấn nhanh liệu có cạnh nối giữa hai đỉnh.
* (-) Không hiệu quả khi số đỉnh lớn (do không gian bộ nhớ là $O(n^2)$)

### Danh sách kề (vector kề)

Sử dụng một mảng các tập hợp (hoặc một mảng các vector), gọi là $neighbor$. $neighbor[i]$ là một tập hợp, hoặc một mảng, chỉ chứa gồm toàn các đỉnh có chung cạnh với $i$.

* (+) Hiệu quả khi có số đỉnh lớn, số cạnh thưa. ($m$ - số cạnh, $n$ - số đỉnh, và $m \approx n$).
* (+) Hiệu quả trong các thuật toán tìm kiếm: DFS, BFS, Floyd, Dijkstra's, ...
* (-) Không hiệu quả khi cần truy vấn nhanh sự kết nối giữa hai đỉnh (so với cách trên)

Vector kề là cách dùng trong phần lớn các bài tập trên graph.

Code mẫu: https://leetcode.com/problems/is-graph-bipartite/submissions/1024823712/

## Các loại đồ thị

### Đồ thị một chiều

Mỗi cạnh sẽ chỉ cần lưu ở một vector kề (chỉ lưu đỉnh đích ở vector kề của đỉnh xuất phát).

### Đồ thị hai chiều

Mỗi cạnh sẽ đều phải lưu ở cả hai vector kề. (đơn giản là cạnh 1 chiều, duplicate, rồi đảo ngược hai đỉnh)

Sẽ thường xuyên phải sử dụng đến một số mảng đánh dấu khi duyệt (`passed`, hoặc `traversed`).

### Đồ thị có trọng số

Ma trận kề có thể thay việc boolean để thể hiện kết nối = int để thể hiện trọng số.

Danh sách kề thì phải lưu một pair/tuple để thể hiện 1 cạnh: {đỉnh_đích, trọng_số}.

### Đồ thị Cây

Đồ thị vô hướng (hai chiều), liên thông, $N$ đỉnh, $N - 1$ cạnh.

Gốc ở đâu có thể được quy định bởi bài toán. Nếu không, ta có thể chọn một đỉnh bất kỳ làm gốc.

Thông thường vẫn là đồ thị hai chiều, nên có thể sử dụng kỹ thuật vector kề để lưu thông tin các cạnh.

Có thể sử dụng thêm các mảng `par` để đánh dấu xem với mỗi nút, nút cha ở đâu. Khi có mảng `par`, ta có thể thay mảng `traversed`, đảm bảo các thuật toán duyệt chỉ duyệt từ gốc đến lá.

### Đồ thị Lưới

Mỗi ô trên lưới vuông là một nút. Từ một ô có thể đi tới các ô chung cạnh. Ở một số trường hợp có thể quy định là có thể đi tới các ô chung đỉnh (đi chéo)

Với loại đồ thị này có thể không cần biểu diễn trong các cách kể trên, do có thể tính được dễ dàng các đỉnh tiếp theo đi tới (từ (x, y) đến (x + 1, y), (x, y + 1), ...)

## Các thuật toán

### BFS & DFS để duyệt toàn bộ các đỉnh

DFS sử dụng đệ quy hoặc stack, BFS sử dụng queue.

Sử dụng vector kề để lưu các cạnh.

Code mẫu BFS: https://leetcode.com/problems/shortest-path-visiting-all-nodes/submissions/1051365507/

### Floyd-Warshall để tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh

https://www.geeksforgeeks.org/floyd-warshall-algorithm-dp-16/

### Dijkstra để tìm đường đi ngắn nhất từ một đỉnh

https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-greedy-algo-7/?ref=lbp

# Bài tập

Có thể bám theo bộ essential của Leetcode trước:

https://leetcode.com/studyplan/graph-theory/

Danh sách các câu bị ẩn bởi premium: