Bài tập duyệt đồ thị theo chiều sâu năm 2024
Một vấn đề rất quan trọng trong Lý thuyết đồ thị là bài toán duyệt tất cả các đỉnh có thể đến được từ một đỉnh xuất phát nào đó, không duyệt lặp lại cũng như không bỏ sót đỉnh nào cả. Vì vậy, ta phải xây dựng được những phép duyệt các đỉnh của đồ thị theo một hệ thống nhất định, những phép duyệt đó gọi là các thuật toán tìm kiếm trên đồ thị. Show Có hai giải thuật tìm kiếm trên đồ thị cơ bản: Tìm kiếm theo chiều sâu (Depth First Search - DFS) và Tìm kiếm theo chiều rộng (Breadth First Search - BFS). Hai giải thuật này có độ phức tạp thuật toán như nhau, nhưng sẽ có những ứng dụng khác nhau và cách cài đặt cũng khác nhau. Xét bài toán sau: Cho đơn đồ thị vô hướng gồm nn đỉnh, mm cạnh, danh sách các cạnh được nhập vào theo dạng (u,v)(u, v) với uu và vv là các đỉnh thuộc đồ thị (1≤u≠v≤n)(1 \le u \ne v \le n). Hãy đưa ra một đường đi từ đỉnh ss tới đỉnh ff cho trước. Dưới đây ta sẽ cài đặt hai giải thuật DFS\text{DFS} và BFS\text{BFS} để giải quyết bài toán này. Các cài đặt đều sử dụng danh sách kề, nếu như đề bài thay đổi thành đa đồ thị hay đồ thị có hướng thì chỉ cần sửa đổi một chút trong quá trình nhập dữ liệu. II. Giải thuật tìm kiếm theo chiều sâu (Depth First Search)Tư tưởng thuật toán:
f←p1=parf←p2=parp1←...←sf \leftarrow p_1=par_f \leftarrow p_2=par_{p_1} \leftarrow ... \leftarrow s Cài đặt:
Giả sử với Input là: n=8,m=7,s=1,f=5n = 8, m = 7, s = 1, f = 5 và danh sách các cạnh là {(1,2),(1,3),(2,3),(2,4),(3,5),(4,6),(7,8)}\{(1, 2), (1, 3), (2, 3), (2, 4), (3, 5), (4, 6), (7, 8)\}, giải thuật sẽ cho ra kết quả là:
Hình vẽ dưới đây cho ta minh họa về quá trình duyệt DFS\text{DFS}: Nhận xét:
III. Giải thuật tìm kiếm theo chiều rộng (Breadth First Search)Tư tưởng thuật toán:
Thứ tự thăm các đỉnh bằng BFS
Cài đặt:
Nhận xét:
Ví dụ: Giải cứu công chúa: IV. Một số bài toán điển hình của hai giải thuật DFS và BFS1. Đếm thành phần liên thôngĐề bài: Cho đơn đồ thị vô hướng G(V,E)G(V, E) gồm nn đỉnh, mm cạnh (m,n≤105)(m, n \le 10^5). Yêu cầu: Hãy xác định xem đồ thị có bao nhiêu thành phần liên thông? Input:
Output:
Ví dụ: Ý tưởng:
Cài đặt:
2. Tìm đường đi ngắn nhấtĐề bài: Một mê cung được biểu diễn dưới dạng ma trận AA gồm mm hàng, nn cột, các hàng được đánh số từ 11 từ trên xuống, các cột được đánh số từ 11 từ trái sang, ô nằm trên giao của hàng i,i, cột jj có chứa số nguyên ai,ja_{i, j} thể hiện một căn phòng của mê cung. Nếu ai,j=1a_{i, j} = 1 thì phòng đó bị khóa, ngược lại thì phòng đó có thể đi qua. Bạn bị nhốt trong căn phòng ở vị trí (x,y)(x, y) của mê cung, mỗi lần bạn chỉ có thể thử đi vào một trong bốn căn phòng bên trái, bên phải, bên trên và bên dưới. Nếu căn phòng đó bị khóa, bạn không thể đi vào được. Nếu như theo một cách nào đó mà bạn tới được một căn phòng không bị khóa nằm trên biên của mê cung, thì khi đó bạn sẽ thoát khỏi mê cung. Yêu cầu: Tìm số bước đi ngắn nhất để thoát khỏi mê cung (chỉ cần đếm số bước đi để tới được một phòng không khóa bất kỳ trên biên của mê cung)? |