BFS

1. Giới thiệu về thuật toán Tìm kiếm theo Chiều Rộng

Thuật toán Tìm kiếm theo Chiều Rộng (Breadth First Search): viết tắt là BFS, là một thuật toán được sử dụng để tìm kiếm trong cây hoặc đồ thị. Thuật toán BFS bắt đầu từ nút khởi đầu, mở rộng theo từng tầng, trước tiên duyệt các nút gần nút khởi đầu nhất, sau đó duyệt các nút xa nút khởi đầu hơn. Tiếp tục quá trình này cho đến khi hoàn thành toàn bộ quá trình tìm kiếm.

Vì thứ tự các nút được duyệt tuân theo nguyên tắc “trước vào trước ra”, nên thuật toán Tìm kiếm theo Chiều Rộng có thể được thực hiện bằng cách sử dụng “hàng đợi”.

2. Các bước của thuật toán Tìm kiếm theo Chiều Rộng

Tiếp theo, chúng ta sẽ lấy một đồ thị vô hướng làm ví dụ để giới thiệu các bước của thuật toán Tìm kiếm theo Chiều Rộng.

Đưa nút khởi đầu $u$ vào hàng đợi và đánh dấu là đã duyệt.
Lấy một nút từ hàng đợi, duyệt nút đó và đưa tất cả các nút kề chưa được duyệt $v$ vào hàng đợi.
Đánh dấu nút $v$ đã duyệt để tránh việc duyệt lại.
Lặp lại bước 2-3 cho đến khi hàng đợi trống hoặc tìm thấy nút mục tiêu.

3. Sử dụng hàng đợi để thực hiện tìm kiếm theo chiều rộng

3.1 Các bước của thuật toán tìm kiếm theo chiều rộng sử dụng hàng đợi

Định nghĩa biến $g r a p h$ để lưu trữ đồ thị vô hướng dưới dạng mảng lồng nhau, $v i s i t e d$ để đánh dấu các nút đã được duyệt, $q u e u e$ để lưu trữ các nút trong hàng đợi, $u$ là nút bắt đầu, định nghĩa phương thức def bfs(graph, u): để thực hiện tìm kiếm theo chiều rộng sử dụng hàng đợi.
Đầu tiên, đánh dấu nút bắt đầu $u$ là đã được duyệt và thêm nó vào hàng đợi, tức là visited.add(u) và queue.append(u).
Lấy nút đầu hàng đợi $u$ . Duyệt qua nút $u$ và thực hiện các thao tác liên quan (tuỳ thuộc vào yêu cầu cụ thể của bài toán).
Duyệt qua tất cả các nút kề chưa được duyệt $v$ của nút $u$ (nút $v$ không có trong $v i s i t e d$ ).
Đánh dấu nút $v$ là đã được duyệt và thêm nó vào hàng đợi, tức là visited.add(v) và queue.append(v).
Lặp lại các bước 3-5 cho đến khi hàng đợi $q u e u e$ rỗng.

3.2 Code triển khai tìm kiếm theo chiều rộng sử dụng hàng đợi

import collections
 
class Solution:
    def bfs(self, graph, u):
        visited = set()                     # Sử dụng visited để đánh dấu các nút đã duyệt
        queue = collections.deque([])       # Sử dụng queue để lưu trữ các nút tạm thời
        
        visited.add(u)                      # Đánh dấu nút bắt đầu u là đã duyệt
        queue.append(u)                     # Thêm nút bắt đầu u vào hàng đợi
        
        while queue:                        # Hàng đợi không rỗng
            u = queue.popleft()             # Lấy nút đầu hàng đợi u
            print(u)                        # Duyệt nút u
            for v in graph[u]:              # Duyệt qua tất cả các nút kề chưa được duyệt v của nút u
                if v not in visited:        # Nút v chưa được duyệt
                    visited.add(v)          # Đánh dấu nút v là đã duyệt
                    queue.append(v)         # Thêm nút v vào hàng đợi
                
 
graph = {
    "0": ["1", "2"],
    "1": ["0", "2", "3"],
    "2": ["0", "1", "3", "4"],
    "3": ["1", "2", "4", "5"],
    "4": ["2", "3"],
    "5": ["3", "6"],
    "6": []
}
 
# Thực hiện tìm kiếm theo chiều rộng sử dụng hàng đợi
Solution().bfs(graph, "0")

4. Ứng dụng của thuật toán Tìm kiếm theo Chiều Rộng

4.1 Sao chép đồ thị

4.1.1 Liên kết đến bài toán

133. Clone Graph

4.1.2 Ý tưởng

Mô tả: Cho một đồ thị vô hướng được biểu diễn dưới dạng danh sách kề (mảng 2 chiều) với $a d j L i s t [i]$ là danh sách kề của nút có giá trị $i + 1$ , $a d j L i s t [i] [j]$ là nút kề với nút có giá trị $i + 1$ .

Yêu cầu: Trả về một bản sao sâu của đồ thị đó.

Giải thích:

Đồ thị có tối đa $100$ nút.
Mỗi giá trị nút $N o d e . v a l$ là duy nhất, $1 \leq N o d e . v a l \leq 100$ .
Đồ thị vô hướng là một đồ thị đơn giản, điều này có nghĩa là không có cạnh trùng lặp và không có đỉnh tự vòng.
Vì đồ thị là vô hướng, nếu nút $p$ là hàng xóm của nút $q$ , thì nút $q$ cũng phải là hàng xóm của nút $p$ .
Đồ thị là đồ thị liên thông, bạn có thể truy cập tất cả các nút từ nút đã cho.

Ví dụ:

Ví dụ 1:

Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]
Explanation:
Có 4 nút trong đồ thị.
Nút 1 có giá trị là 1, có 2 hàng xóm: nút 2 và 4.
Nút 2 có giá trị là 2, có 2 hàng xóm: nút 1 và 3.
Nút 3 có giá trị là 3, có 2 hàng xóm: nút 2 và 4.
Nút 4 có giá trị là 4, có 2 hàng xóm: nút 1 và 3.

Ví dụ 2:

Input: adjList = [[2],[1]]
Output: [[2],[1]]

4.1.3 Ý tưởng giải quyết

Ý tưởng 1: Tìm kiếm theo Chiều Rộng

Sử dụng bảng băm $v i s i t e d$ để lưu trữ các nút đã được duyệt trong đồ thị gốc và đồ thị sao chép, với cặp khóa-giá trị là “nút đã được duyệt trong đồ thị gốc: nút tương ứng trong đồ thị sao chép”. Sử dụng hàng đợi $q u e u e$ để lưu trữ các nút.
Dựa trên nút bắt đầu $n o d e$ , tạo một nút mới và thêm nó vào bảng băm $v i s i t e d$ , tức là visited[node] = Node(node.val, []). Sau đó, đưa nút bắt đầu vào hàng đợi, tức là queue.append(node).
Lấy nút đầu hàng đợi $n o d e_{u}$ . Duyệt qua nút $n o d e_{u}$ và thực hiện các thao tác liên quan (tùy thuộc vào yêu cầu cụ thể của bài toán).
Duyệt qua tất cả các nút kề chưa được duyệt $n o d e_{v}$ của nút $n o d e_{u}$ (nút $n o d e_{v}$ không có trong $v i s i t e d$ ).
Tạo một nút mới dựa trên nút $n o d e_{v}$ và thêm nó vào bảng băm $v i s i t e d$ , tức là visited[node_v] = Node(node_v.val, []).
Sau đó, đưa nút $n o d e_{v}$ vào hàng đợi $q u e u e$ , tức là queue.append(node_v).
Lặp lại các bước 3-6 cho đến khi hàng đợi $q u e u e$ rỗng.
Kết thúc tìm kiếm theo chiều rộng, trả về nút sao chép của nút bắt đầu (tức là $v i s i t e d [n o d e]$ ).

Ý tưởng 1: Code

class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        if not node:
            return node
        
        visited = dict()
        queue = collections.deque()
 
        visited[node] = Node(node.val, [])
        queue.append(node)
 
        while queue:
            node_u = queue.popleft()
            for node_v in node_u.neighbors:
                if node_v not in visited:
                    visited[node_v] = Node(node_v.val, [])
                    queue.append(node_v)
                visited[node_u].neighbors.append(visited[node_v])
        
        return visited[node]

Ý tưởng 1: Phân tích độ phức tạp

Độ phức tạp thời gian: $O (n)$ . Trong đó $n$ là số lượng nút trong đồ thị.
Độ phức tạp không gian: $O (n)$ .

4.2 Tìm diện tích lớn nhất của đảo

4.2.1 Liên kết đề bài

695. Max Area of Island

4.2.2 Đề bài

Mô tả: Cho một mảng hai chiều chứa các phần tử chỉ gồm 0 và 1, trong đó 1 đại diện cho đảo và 0 đại diện cho nước. Diện tích của một đảo chính là số lượng khối 1 kề cạnh theo chiều ngang hoặc chiều dọc.

Yêu cầu: Tính diện tích lớn nhất của đảo.

Giải thích:

$m$ là số hàng của mảng.
$n$ là số cột của mảng.
$1 \leq m, n \leq 50$ .
$g r i d [i] [j]$ có giá trị 0 hoặc 1.

Ví dụ:

Ví dụ 1:

Input: grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
Output: 6
Explanation: Đáp án không phải là 11, vì một đảo chỉ có thể chứa các khối 1 kề cạnh theo chiều ngang hoặc chiều dọc.

Ví dụ 2:

Input: grid = [[0,0,0,0,0,0,0,0]]
Output: 0

4.2.3 Ý tưởng giải quyết

Ý tưởng 1: Duyệt theo chiều rộng

Sử dụng biến $an s$ để lưu diện tích lớn nhất của đảo.
Duyệt qua từng phần tử trong mảng hai chiều, với mỗi phần tử có giá trị là 1:
1. Đặt giá trị của phần tử đó thành 0. Sử dụng hàng đợi $q u e u e$ để lưu vị trí của phần tử đó. Sử dụng biến $t e m p an s$ để lưu diện tích hiện tại của đảo.
2. Lấy ra vị trí $(i, j)$ đầu tiên trong hàng đợi. Duyệt qua các vị trí lân cận trên, dưới, trái, phải của vị trí đó. Đặt giá trị của các vị trí lân cận thành 0 (để tránh duyệt lại). Thêm các vị trí lân cận vào hàng đợi. Tăng giá trị của $t e m p an s$ lên 1.
3. Lặp lại bước trên cho đến khi hàng đợi $q u e u e$ trống.
4. Cập nhật diện tích lớn nhất của đảo, tức là $an s = max (an s, t e m p an s)$ .
Trả về giá trị của $an s$ là kết quả.

Ý tưởng 1: Code

import collections
 
class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        directs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        rows, cols = len(grid), len(grid[0])
        ans = 0
        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == 1:
                    grid[i][j] = 0
                    temp_ans = 1
                    queue = collections.deque([(i, j)])
                    while queue:
                        i, j = queue.popleft()
                        for direct in directs:
                            new_i = i + direct[0]
                            new_j = j + direct[1]
                            if new_i < 0 or new_i >= rows or new_j < 0 or new_j >= cols or grid[new_i][new_j] == 0:
                                continue
                            grid[new_i][new_j] = 0
                            queue.append((new_i, new_j))
                            temp_ans += 1
 
                    ans = max(ans, temp_ans)
        return ans

Ý tưởng 1: Phân tích độ phức tạp

Độ phức tạp thời gian: $O (n \times m)$ , trong đó $m$ và $n$ lần lượt là số hàng và số cột của mảng.
Độ phức tạp không gian: $O (n \times m)$ .

Hung Nguyen 🧠🌳

Explorer

BFS

1. Giới thiệu về thuật toán Tìm kiếm theo Chiều Rộng

2. Các bước của thuật toán Tìm kiếm theo Chiều Rộng

3. Sử dụng hàng đợi để thực hiện tìm kiếm theo chiều rộng

3.1 Các bước của thuật toán tìm kiếm theo chiều rộng sử dụng hàng đợi

3.2 Code triển khai tìm kiếm theo chiều rộng sử dụng hàng đợi

4. Ứng dụng của thuật toán Tìm kiếm theo Chiều Rộng

4.1 Sao chép đồ thị

4.1.1 Liên kết đến bài toán

4.1.2 Ý tưởng

4.1.3 Ý tưởng giải quyết

Ý tưởng 1: Tìm kiếm theo Chiều Rộng

Ý tưởng 1: Code

Ý tưởng 1: Phân tích độ phức tạp

4.2 Tìm diện tích lớn nhất của đảo

4.2.1 Liên kết đề bài

4.2.2 Đề bài

4.2.3 Ý tưởng giải quyết

Ý tưởng 1: Duyệt theo chiều rộng

Ý tưởng 1: Code

Ý tưởng 1: Phân tích độ phức tạp

Graph View

Table of Contents

Backlinks