Thuật toán BFS là thuật toán tìm kiếm theo chiều rộng trên đồ thị vô hướng hoặc có hướng, không trọng số. Minh họa: Visualization Cho đồ thị như hình vẽ Cho đồ thị như hình vẽ, tìm đường đi ngắn nhất từ đỉnh 0 đến đỉnh 5 Như vậy ta có file input.txt với dạng ma trận kề như sau Ta có file input.txt chứa ma trận kề như saufile input.txt danh sách kề Mô tả thuật toán: Xuất phát từ 1 đỉnh bất kỳ, đi tới tất cả các đỉnh kề của nó, lưu các đỉnh này lại. Tiếp tục đem 1 đỉnh khác (từ tập đỉnh đã được lưu) ra xét và đi cho đến khi không còn đỉnh nào có thể đi. Trong quá trình đi từ đỉnh này sang đỉnh kia, t iến hành lưu lại đỉnh cha của đỉnh kề, để khi đi ngược lại từ đỉnh kết thúc đến đỉnh xuất phát, ta có được đường đi ngắn nhất. Bước 0: Chuẩn bị dữ liệu Bước 0: Chuẩn bị dữ liệu Bước 1: Chạy thuật toán lần 1 Bước 2: Chạy thuật toán lần 2 Bước 3: Chạy thuật toán lần 3 Bước 4: Chạy thuật toán lần 4 Bước 5: Chạy thuật toán lần 5 Bước 6: Chạy thuật toán lần 6 Dừng thuật toán Kết quả: 0 -> 1 -> 5 Thứ tự duyệt BFS là 0, 1, 3, 2, 5, 4 Chạy thuật toán chính Ta xem đoạn code sau Ý nghĩa: Xuất phát từ 1 đỉnh đi tới tất cả các đỉnh kề của nó, lưu các đỉnh này lại. Tiếp tục đem 1 đỉnh khác (từ tập đỉnh đã được lưu) ra xét và đi cho đến khi không còn đỉnh nào có thể đi. Trong quá trình đi từ đỉnh này sang đỉnh kia, t iến hành lưu lại đỉnh cha của đỉnh kề, để khi đi ngược lại từ đỉnh kết thúc đến đỉnh xuất phát, ta có được đường đi ngắn nhất. Mã nguồn toàn bộ Độ phức tạp thuật toán Độ phức tạp của BFS: O(V + E) (với V là số đỉnh) Ưu điểm và ứng dụng của BFS Kỹ thuật tìm kiếm rộng là kỹ thuật vét cạn không gian trạng thái bài toán vì vậy sẽ tìm được lời giải nếu có và đường đi tìm được đi qua ít đỉnh nhất. Tìm kiếm ưu tiên chiều rộng hay tìm kiếm theo chiều rộng (tiếng Anh: Breadth-first search - BFS) là một thuật toán duyệt hoặc tìm kiếm trên một cây hoặc một đồ thị. Thuật toán khởi đầu tại gốc (hoặc chọn một đỉnh nào đó coi như gốc) và phát triển theo nguyên tắc "gần trước xa sau". Ví dụ: Bài toán đặt ra là: Cho đơn đồ thị vô hướng liên thông ~G = (V, E)~ gồm ~n~ đỉnh và ~m~ cạnh, các đỉnh được đánh số từ ~1~ tới ~n~ và các cạnh được đánh số từ ~1~ tới ~m~. Bằng thuật toán tìm kiếm theo chiều rộng, hãy đưa ra danh sách các đỉnh theo thứ tự tìm kiếm (thăm). Biết rằng: Đỉnh nào có chỉ số bé hơn sẽ được ưu tiên thăm trước. Một trong những kĩ thuật cơ bản nhất liên quan đến cây đó chính là duyệt toàn bộ cây đó. Vậy thì có những phương pháp nào để duyệt một cây? Hãy cùng nhau tìm hiểu trong bài học ngày hôm nay nhé! Nội dungĐể có thể tiếp thu bài học này một cách tốt nhất, các bạn nên có những kiến thức cơ bản về:
Trong bài học ngày hôm nay, chúng ta sẽ cùng nhau tìm hiểu về:
BFSKhái niệmThuật toán tìm kiếm theo chiều rộng (thường gọi là BFS) là một thuật toán duyệt bắt đầu từ gốc, sau đó lần lượt xét qua các node của một cây theo ưu tiên về độ sâu từ nhỏ đến lớn. Ở đây có một khái niệm mới là “độ sâu”. Độ sâu của một node được định nghĩa là số cạnh trên đường đi từ node đang xét đến node gốc. Ví dụ: Đề bàiCho một cây gồm đỉnh. Hãy in ra các đỉnh được xét lần lượt trong quá trình BFS. Coi đỉnh 1 là gốc. Input: Dòng 1: Gồm số nguyên thể hiện cho số đỉnh của cây . dòng tiếp theo: Gồm hai số nguyên thể hiện một cạnh giữa và trên cây Output: Dòng 1: Một dòng thể hiện các đỉnh được đi qua theo thứ tự trong quá trình BFS Ví dụ: Input Output 8 1 2 2 3 3 4 2 5 1 6 6 7 3 8 1 2 6 3 5 7 4 8 Cây trong đề bài chính là cây được mình dùng làm ví dụ ở phần khái niệm. Cách cài đặtTrước hết, chúng ta sẽ cần tìm cách để thể hiện một cạnh của cây. Cách được dùng phổ biến nhất là dùng danh sách kề, tức là mỗi node sẽ có một danh sách lưu lại tất cả các node kề (node có cạnh trực tiếp) với node đó. Trong C++, các bạn có thể dùng vector để lưu danh sách kề. Để biết cụ thể cách làm, hãy đọc phần code nhé. Tiếp theo sẽ là cách cái đặt thuật toán BFS . Tư tưởng của BFS đơn giản là như sau:
Code` include<bits/stdc++.h>using namespace std; const int MaxN = 1 + 1e5; int n; bool mark[MaxN]; vector<int> adj[MaxN]; void BFS(){ }
int main(){ }
`Mở rộngVừa rồi mình trình bày BFS trên cây. Tuy nhiên, ta có thể tiến hành BFS trên một đơn đồ thị tổng quát với cùng một ý tưởng như trên. Độ phức tạp của BFS là trong đó, là số cạnh, là số đỉnh của một đồ thị. DFSKhái niệmThuật toán tìm kiếm theo chiều sâu (thường gọi là DFS) là một thuật toán duyệt khởi đầu tại node gốc và đi xa nhất có thể theo một nhánh. Các bạn sẽ rõ hơn về điều này khi ta đi vào phần sau. Đề bàiCho một cây gồm đỉnh. Hãy in ra các đỉnh được xét lần lượt trong quá trình DFS. Coi đỉnh 1 là gốc. Input: Dòng 1: Gồm số nguyên thể hiện cho số đỉnh của cây . dòng tiếp theo: Gồm hai số nguyên thể hiện một cạnh giữa và trên cây Output: Dòng 1: Một dòng thể hiện các đỉnh được đi qua theo thứ tự trong quá trình DFS Ví dụ: Input Output 8 1 2 2 3 3 4 2 5 1 6 6 7 3 8 1 2 3 4 8 5 6 7 Cây trong đề bài chính là cây ở phần trước. Cách cài đặtTiến trình DFS được trình bày như sau:
Để có thể code DFS, thông thường ta sẽ dùng đệ quy. Code` include<bits/stdc++.h>using namespace std; const int MaxN = 1 + 1e5; int n; bool mark[MaxN]; vector<int> adj[MaxN]; void DFS(int u){ }
int main(){ }
`Độ phức tạp của DFS giống như BFS và là trong đó, là số cạnh, là số đỉnh của một đồ thị. Mở rộngQuan hệ cha - conTừ quá trình DFS, ta sẽ có một kiểu quan hệ mới giữa hai node trên cây đó là quan hệ “cha – con”. Một node được gọi là node cha của node khi giữa và có cạnh nối trực tiếp và được xét trước trong quá trình DFS. Lưu ý: Quan hệ cha – con là quan hệ tương đối, tức là có thể thay đổi phụ thuộc vào cách node gốc được chọn. Node láMột node được gọi là node lá khi nó không có bất cứ một con nào. Cây nhị phânMột cây được gọi là cây nhị phân khi mỗi node cha có nhiều nhất hai node con và một node chỉ có duy nhất một node cha. Ví dụ: Kết luận
Tải xuốngTài liệuNhằm phục vụ mục đích học tập Offline của cộng đồng, Kteam hỗ trợ tính năng lưu trữ nội dung bài học BFS và DFS dưới dạng file PDF trong link bên dưới. Ngoài ra, bạn cũng có thể tìm thấy các tài liệu được đóng góp từ cộng đồng ở mục TÀI LIỆU trên thư viện Howkteam.com Đừng quên like và share để ủng hộ Kteam và tác giả nhé! Thảo luậnNếu bạn có bất kỳ khó khăn hay thắc mắc gì về khóa học, đừng ngần ngại đặt câu hỏi trong phần bên dưới hoặc trong mục HỎI & ĐÁP trên thư viện Howkteam.com để nhận được sự hỗ trợ từ cộng đồng. |