- Thuật toán DFS/BFS:
Intro:
Chắc hẳn các cậu đều đã nghe qua bài toán: "7 cây cầu" của Euler. Đây là một bài toán nổi tiếng về lý thuyết đồ thị. Đồ thị là một tập các đối tượng có quan hệ với nhau theo một cách nào đó. Chẳng hạn như trong khoa học máy tính, đồ thị được sử dụng để mô hình hóa một mạng truyền thông, kiến trúc của các máy tính song song,... Bài toán tối ưu đường đi giao hàng trong các công ty thương mại lớn như Shopee, Tiki,... cũng có thể biểu diễn dưới dạng đồ thị.
Chính vì vậy, việc nắm vững các thuật toán liên quan đến đồ thị là điều hết sức quan trọng đối với mỗi lập trình viên.
Hôm nay, Mely xin giới thiệu đến các cậu 2 thuật toán duyệt đồ thị cơ bản đó là: DFS và BFS.

https://www.canva.com/design/DAFxVXaUxsY/3isgr9EJtLaHh1Iae6vzrA/edit

(Thêm vào caption ở ảnh trên)
* Tô màu các đỉnh trong video:
Đỉnh có viền xanh: Đỉnh đang được gọi đệ quy
Đỉnh có nền xanh: Đỉnh đang xét
Đỉnh có viền vàng: Đỉnh đã thăm
Ví dụ đồ thị như trong video. Giả sử đỉnh bắt đầu là đỉnh 0. Khi đó: Một cách duyệt DFS có thể là:
- Xét đỉnh 1 kề với đỉnh 0, do đỉnh 1 chưa được tới thăm nên di chuyển đến đỉnh 1.
- Tương tự, di chuyển đến đỉnh 2 rồi đến đỉnh 3.
- Từ đỉnh 3, ta có đường đi nối đến đỉnh 1, tuy nhiên đỉnh 1 đã được thăm rồi, nên ta quay lại đỉnh 2, sau đó quay lại đỉnh 1, đỉnh 0.
- Từ đỉnh 0 ta tiếp tục tới thăm đỉnh 4.
- Đỉnh 4 có đường nối đến đỉnh 3, vì đỉnh 3 đã được thăm trước đó nên ta quay lại đỉnh 0.
- Từ đỉnh 0 đến thăm đỉnh 5.
Lúc này, tất cả các điểm đều đã được duyệt qua. Thuật toán kết thúc.

----------
Breadth-first search (BFS):
Table of contents:
1. BFS là gì?
- Thuật toán duyệt đồ thị ưu tiên chiều rộng (Breath-first search) là một trong những thuật toán tìm kiếm cơ bản và cần thiết trên đồ thị. Trong mỗi lần thực hiện, thuật toán ưu tiên duyệt những đỉnh gần đỉnh đang xét trước. Đường đi thu được từ thuật toán BFS tới bất kỳ đỉnh nào là đường đi ngắn nhất tới đỉnh đó, tức là đường đi chứa số cạnh nhỏ nhất trên đồ thị không có trọng số.
- Thuật toán được áp dụng để giải nhiều bài toán khác nhau như tìm tất cả các đỉnh có thể duyệt được từ một đỉnh cho trước, kiểm tra tính liên thông của đồ thị, tìm (trong đồ thị không có trọng số) đường đi ngắn nhất từ một đỉnh tới tất cả các đỉnh khác, xác định xem đồ thị có phải là đồ thị hai phía (bipartite graph) hay không, tìm đường kính (diameter) của đồ thị vô hướng...
- Giống như0 thuật toán DFS, BFS có thể áp dụng cho cả đồ thị có hướng và đồ thị vô hướng.
2. BFS hoạt động thế nào? Các bước ra sao?
Cho trước một đồ thị không có trọng số và đỉnh nguồn s.
Ta định nghĩa level(i) là cấp của đỉnh i, nghĩa là độ dài đường đi ngắn nhất từ đỉnh nguồn s đến đỉnh i.
Thuật toán có thể được hiểu như một ngọn lửa lan rộng trên đồ thị: Ban đầu, ngọn lửa bốc cháy tại đỉnh nguồn s. Ở mỗi bước, ngọn lửa lan rộng từ đỉnh này sang các tất cả đỉnh khác liền kề với nó.
Trong mỗi lần lặp của thuật toán, “vòng lửa” lại lan rộng theo chiều rộng. Các đỉnh có chung một level sẽ được ưu tiên duyệt trước, sau đó mới duyệt đến các đỉnh ở level cao hơn. (xem hình)
Ta cần một cấu trúc dữ liệu queue (hàng đợi) để chứa danh sách những đỉnh đang “chờ” thăm. Tại mỗi bước, ta thăm một đỉnh đầu hàng đợi, loại nó ra khỏi danh sách và cho những đỉnh kề với nó chưa được thăm xếp hàng vào cuối hàng đợi. Thuật toán sẽ kết thúc khi hàng đợi rỗng và lúc đó, tất cả các đỉnh của đồ thị đã được duyệt.
Một cách cụ thể hơn,
Ta cần một hàng đợi queue để lưu trữ các đỉnh cần được thăm và một mảng boolean visited[]  cho biết mỗi đỉnh đã được thăm hay chưa.
Ban đầu, ta thêm  s  vào queue và đặt  visited[s] = true , và đối với tất cả các đỉnh i khác s, ta đặt  visited[i] = false . Thực hiện lặp lại các bước sau cho đến khi queue rỗng:
• Lấy ra phần tử đầu tiên của hàng đợi, gọi là u
• Duyệt lần lượt tất cả các đỉnh liền kề với u, gọi chung là v
• Đối với mỗi đỉnh v, kiểm tra xem v đã được thăm trước đó chưa (visited[v] = true hay là false)
• Nếu  v chưa được thăm trước đó (visited[v] = false), ta đánh dấu đỉnh đó là đã thăm (visted[v] = true) và thêm v vào cuối queue.
Vòng lặp kết thúc khi queue trống. Mảng visited[] với tất cả các giá trị true cho ta biết tất cả các đỉnh đã được thăm.
Tuy nhiên, với thông tin này ta chỉ mới biết được từ một đỉnh s thì ta có thể đi đến thăm được một đỉnh nào đó trong đồ thị mà chưa biết độ dài đường đi ngắn nhất của giữa chúng và đường đi đó đi qua những điểm nào.
Để xử lí điều này, ta chỉ cần duy trì một mảng level[] (như đã đề cập ở trên) và truy vết đường đi bằng cách duy trì một mảng parent[] khác. Ta gán level[s] = 0. Vì đỉnh nguồn không có điểm nào tới được điểm đó nên ta cũng gán parent[s] = -1. Ở mỗi bước, ta nhận thấy rằng mỗi đỉnh v nếu chưa được thăm trước đó thì chỉ có thể được thăm bởi u. Vì vậy ta có level[v] = level[u] + 1 và parent[v] = u.
Sau cùng, ta có level[i] chứa độ dài ngắn nhất để từ đỉnh nguồn s, ta tới được i. Đối với đường đi, đơn giản ta chỉ cần xuất phát ngược từ đỉnh mà ta muốn xét, in ra parent của nó và lặp lại cho đến khi parent của nó = -1 (nghĩa là ta đã duyệt đến đỉnh nguồn).
Code mẫu: https://ideone.com/w30RL5
** Giải thích ví dụ trong video:
* Tô màu các đỉnh trong video:
Đỉnh có viền xanh: Đỉnh trong hàng đợi (đỉnh đang được chờ thăm)
Đỉnh có nền xanh: Đỉnh đang xét
Đỉnh có viền vàng: Đỉnh đã thăm
* Giải thích thuật toán:
Ta có đồ thị vô hướng như trong video và đỉnh nguồn là đỉnh 0. Gọi hàng đợi là q.
Khi đó, thuật toán BFS sẽ được thực hiện như sau:
- Đánh dấu đỉnh 0 đã thăm, đặt đỉnh 0 vào hàng đợi. q = {0}
- Lấy ra đỉnh 0 từ đầu hàng đợi, xét đỉnh kề với đỉnh 0 là đỉnh 1: vì đỉnh 1 chưa thăm nên ta đánh dấu nó là đã thăm và đặt đỉnh 1 vào hàng đợi. q = {1}
- Lấy ra đỉnh 1 từ đầu hàng đợi, xét 3 đỉnh kề với đỉnh 1 là đỉnh 2, 3, 4:
+ Đỉnh 2 chưa thăm, đánh dấu là đã thăm và đặt đỉnh 2 vào hàng đợi.
+ Tương tự, đỉnh 3 và 4 chưa được thăm, đánh dấu 2 đỉnh là đã thăm và đặt 2 đỉnh vào hàng đợi.
+ Lúc này, q = {2, 3, 4}
- Lấy ra đỉnh 2 từ đầu hàng đợi, xét 2 đỉnh kề với đỉnh 2 là 1, 3:
+ Đỉnh 1 đã thăm nên ta bỏ qua đỉnh này.
+ Tương tự, đỉnh 3 cũng đã thăm nên ta cũng bỏ qua đỉnh này.
+ Lúc này, q = {3, 4}
- Lấy ra đỉnh 3 từ đầu hàng đợi, xét 3 đỉnh kề với đỉnh 3 là 1, 2, 5:

+ Đỉnh 1, 2 đã thăm nên ta bỏ qua 2 đỉnh này.
+ Đỉnh 5 chưa thăm, ta đánh dấu đã thăm và đặt đỉnh 5 và hàng đợi.
+ Lúc này, q = {4, 5}
- Lấy ra đỉnh 4 từ đầu hàng đợi, xét đỉnh kề với đỉnh 4 là đỉnh 1. Đỉnh 1 đã thăm nên ta bỏ qua đỉnh này. q = {5}
- Lấy ra đỉnh 5 từ đầu hàng đợi, xét 2 đỉnh kề với đỉnh 5 là đỉnh 3, 6:
+ Đỉnh 3 đã thăm nên ta bỏ qua đỉnh này
+ Đỉnh 6 chưa thăm, ta đánh dấu đã thăm và đặt đỉnh 6 và hàng đợi.
+ Lúc này, q = {6}
- Lấy ra đỉnh 6 từ đầu hàng đợi, xét đỉnh kề với đỉnh 6 là đỉnh 5. Đỉnh 5 đã thăm nên ta bỏ qua đỉnh này.
- Lúc này hàng đợi q đã rỗng, kết thúc thuật toán.
3. Đánh giá độ phức tạp
Ta gọi |V| là số lượng đỉnh và |E| là số lượng cạnh của đồ thị.
Độ phức tạp của thuật toán: Nếu ta sử dụng ma trận kề (adjacency matrix) để biểu diễn thuật toán, độ phức tạp sẽ là O(|V|^2). Tuy nhiên, khi sử dụng danh sách kề (adjacency list), thuật toán chỉ mất độ phức tạp O(|V| + |E|). Sở dĩ ta có điều này vì với danh sách kề ta có khả năng duyệt qua các đỉnh kề của mỗi đỉnh một cách hiệu quả (tối ưu về mặt thời gian).
Ta nhận thấy queue không bao giờ vượt quá |V| phần tử. Vì vậy độ phức tạp không gian sẽ là O(|V|).
4. Một số ứng dụng của BFS (optional, vắn tắt)
Dưới đây là một số bài toán có thể giải bằng BFS:
* Tìm tất cả các thành phần liên thông của đồ thị.
* Tìm đường đi ngắn nhất trong đồ thị có trọng số 0 hoặc 1 (bài toán 0-1 BFS).
* Tìm chu kỳ ngắn nhất trong đồ thị có hướng không trọng số.
* Tìm tất cả các cạnh hoặc đỉnh nằm trên bất kỳ đường đi ngắn nhất nào giữa một cặp đỉnh nhất định.
<!-- Reference documents:
https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-fall-2011/resources/lecture-13-breadth-first-search-bfs/
https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/196a95604877d326c6586e60477b59d4_MIT6_006S20_lec9.pdf (two main rfs)
https://cp-algorithms.com/graph/breadth-first-search.html (for cp)
https://www.cs.cmu.edu/afs/cs/academic/class/15210-s15/www/lectures/bfs-notes.pdf (advanced terms)
https://www.slideshare.net/ShuvongkorBarman/presentation-on-breadth-first-search-bfs (for diagram examples) -->

Nội dung cho slide bfs:
1. BFS là gì
a) Nhà phát minh
- BFS và ứng dụng của nó trong bài toán tìm các thành phần liên thông trên đồ thị được nhà kỹ sư khoa học máy tính người Đức, Konrad Zuse phát minh vào năm 1945.
- Ngoài đóng góp trên, ông cũng có thành tựu tạo ra chiếc máy tính lập trình đầu tiên trên thế giới Z3 được điều khiển bằng chương trình, bắt đầu hoạt động vào tháng 5 năm 1941.
b) BFS là gì
- Thuật toán duyệt đồ thị ưu tiên chiều rộng (Breath-first search) là một trong những thuật toán tìm kiếm cơ bản và cần thiết trên đồ thị. Trong mỗi lần thực hiện, thuật toán ưu tiên duyệt những đỉnh gần đỉnh đang xét trước mà có cạnh nối từ đỉnh đang xét đến nó. Đường đi thu được từ thuật toán BFS tới bất kỳ đỉnh nào là đường đi ngắn nhất tới đỉnh đó, tức là đường đi chứa số cạnh nhỏ nhất trên đồ thị không có trọng số.
- Thuật toán được áp dụng để giải nhiều bài toán khác nhau như tìm tất cả các đỉnh có thể duyệt được từ một đỉnh cho trước, kiểm tra tính liên thông của đồ thị, tìm (trong đồ thị không có trọng số) đường đi ngắn nhất từ một đỉnh tới tất cả các đỉnh khác, xác định xem đồ thị có phải là đồ thị hai phía (bipartite graph) hay không, tìm đường kính (diameter) của đồ thị vô hướng...
- Giống như thuật toán DFS, BFS có thể áp dụng cho cả đồ thị có hướng và đồ thị vô hướng.
2. Ví dụ về một cách duyệt:
Giải thích thông qua hình => giải thích cấp (level) của đỉnh
3. Mô tả thuật toán
- Lấy ra một ví dụ chứa cycle và giải thích tầm quan trọng của việc đánh dấu điểm đã thăm
- Làm sao để lưu trữ các đỉnh được chờ thăm? => sử dụng cấu trúc dữ liệu
+ Khi ta duyệt một đỉnh, ta không lập tức duyệt tiếp các lân cận của nó luôn mà cần phải xét hết tất cả các đỉnh cùng level với nó trước.
=> cấu trúc này phải đảm bảo rằng các đỉnh của cùng 1 level phải được xét trước khi duyệt tới các level sau.
=> điều này dẫn tới việc ta liên tưởng đến cấu trúc dữ liệu hàng đợi sử dụng phương pháp FIFO (first in first out).

Cho một đồ thị vô hướng và một đỉnh nguồn s cho trước.
BFS sẽ tuân theo 3 quy tắc đơn giản sau:
Quy tắc 1: Từ đỉnh đang xét, đi thăm đỉnh chưa thăm liền kề. Đánh dấu nó là đã thăm. In ra đỉnh đó và thêm nó vào hàng đợi.
Quy tắc 2: Nếu không tìm thấy đỉnh thỏa mãn, loại bỏ đỉnh đó khỏi hàng đợi.
Quy tắc 3 : Lặp lại Quy tắc 1 và Quy tắc 2 cho đến khi hàng đợi trống.

Lúc này, toàn bộ đồ thị đã được duyệt qua, thuật toán kết thúc.
Tuy nhiên, với thông tin này ta chỉ mới biết được từ một đỉnh s thì ta có thể đi đến thăm được một đỉnh nào đó trong đồ thị mà chưa biết độ dài đường đi ngắn nhất của giữa chúng và đường đi đó đi qua những điểm nào.
Để xử lí điều này, ta chỉ cần duy trì một mảng level[] (như đã đề cập ở trên) và truy vết đường đi bằng cách duy trì một mảng parent[] khác. Ta gán level[s] = 0. Vì đỉnh nguồn không có điểm nào tới được điểm đó nên ta cũng gán parent[s] = -1. Ở mỗi bước, ta nhận thấy rằng mỗi đỉnh v nếu chưa được thăm trước đó thì chỉ có thể được thăm bởi u. Vì vậy ta có level[v] = level[u] + 1 và parent[v] = u.
Sau cùng, ta có level[i] chứa độ dài ngắn nhất để từ đỉnh nguồn s, ta tới được i. Đối với đường đi, đơn giản ta chỉ cần xuất phát ngược từ đỉnh mà ta muốn xét, in ra parent của nó và lặp lại cho đến khi parent của nó = -1 (nghĩa là ta đã duyệt đến đỉnh nguồn).

=> Ví dụ về thuật toán trên một đồ thị cụ thể

Tìm tất cả các thành phần liên thông của đồ thị.
Tìm tất cả các cạnh hoặc đỉnh nằm trên bất kỳ đường đi ngắn nhất nào giữa một cặp đỉnh nhất định.