Cấu trúc dữ liệu và Giải thuật Bài 47: Khám phá mạng lưới với Breadth-First Search (BFS) và Depth-First Search (DFS).

Khi duyệt một Cây nhị phân (Bài 40), dữ liệu luôn chảy theo một chiều cố định từ trên xuống dưới. Nhưng trên Đồ thị (Graph), sự tự do kết nối tạo ra những chu trình khép kín (Cycles). Nếu Ga A nối với Ga B, Ga B nối với Ga C, và Ga C lại có đường nối ngược về Ga A, thuật toán duyệt sẽ rơi vào một vòng lặp vĩnh cửu.

Để máy tính có thể "đi dạo" an toàn qua các mạng lưới chằng chịt mà không làm treo cứng toàn bộ hệ thống, nguyên tắc sinh tử đầu tiên là: Luôn phải mang theo một cuốn sổ ghi chép (Visited Set) để đánh dấu những nơi mình đã đi qua. Bằng cách kết hợp cuốn sổ này với Hàng đợi (Queue) hoặc Ngăn xếp (Stack), chúng ta có hai chiến thuật khám phá Đồ thị kinh điển: BFS và DFS.

1. Breadth-First Search (BFS) - Quét Radar Theo Chiều Rộng

BFS hoạt động giống hệt như một làn sóng radar lan tỏa, hoặc cách một chùm tín hiệu khẩn cấp phát đi từ trung tâm điều khiển trạm.

• Bắt đầu từ một đỉnh gốc (ví dụ: Ga Bến Thành), BFS sẽ quét toàn bộ các đỉnh kề trực tiếp với nó (Khoảng cách = 1). Sau khi thăm hết các đỉnh bậc 1, nó mới tiến ra vòng tròn tiếp theo để thăm các đỉnh bậc 2.
• Động cơ vật lý: BFS sử dụng Hàng đợi (Queue - FIFO) để duy trì trật tự "ai ở gần sẽ được thăm trước".

Triển khai bằng Golang:

Chúng ta tái sử dụng cấu trúc adjList từ Bài 46.

func (g *Graph) BFS(startVertex string) {
    // Cuốn sổ ghi chép (Visited Set)
    visited := make(map[string]bool)
    
    // Hàng đợi (Queue) sử dụng Slice
    queue := []string{startVertex}
    
    // Đánh dấu đỉnh đầu tiên đã được vào sổ
    visited[startVertex] = true
    
    for len(queue) > 0 {
        // Dequeue: Lấy đỉnh ở đầu hàng đợi ra xử lý
        current := queue[0]
        queue = queue[1:]
        
        fmt.Printf("Đang thăm: %s\n", current)
        
        // Quét tất cả hàng xóm của đỉnh hiện tại
        for _, neighbor := range g.adjList[current] {
            // Nếu hàng xóm chưa từng được thăm
            if !visited[neighbor] {
                visited[neighbor] = true      // Đánh dấu đã thấy
                queue = append(queue, neighbor) // Enqueue: Đưa vào cuối hàng đợi
            }
        }
    }
}

• Thời gian thực thi: $O(V + E)$ (với $V$ là số đỉnh, $E$ là số cạnh). Thuật toán chỉ lướt qua mỗi đỉnh và mỗi cạnh đúng 1 lần.
• Ứng dụng cốt lõi: Trả lời câu hỏi "Đường đi ngắn nhất từ A đến B là gì?" trên các đồ thị không có trọng số. Ví dụ: Tìm số trạm ít nhất phải đi qua để đến được đích, hoặc tìm mối liên hệ "bạn của bạn" (2nd-degree connection) trên mạng xã hội.

2. Depth-First Search (DFS) - Đào Sâu Đến Tận Cùng

Trái ngược với sự cẩn trọng lan tỏa của BFS, DFS là một chiến binh liều lĩnh. Nó hoạt động như một thuật toán giải mê cung: Chọn một con đường và cắm đầu đi sâu mãi xuống dưới cho đến khi đụng phải ngõ cụt (hoặc đỉnh đã thăm). Khi đụng tường, nó mới Backtrack (quay lui) lại ngã rẽ gần nhất để thử con đường khác.

• Động cơ vật lý: DFS sử dụng Ngăn xếp (Stack - LIFO). Trong thực tế lập trình, chúng ta hiếm khi phải tự viết cấu trúc Stack cho DFS, mà tận dụng luôn Call Stack của hệ điều hành thông qua Đệ quy (Recursion).

Triển khai bằng Golang:

func (g *Graph) DFS(startVertex string) {
    // Khởi tạo sổ ghi chép dùng chung cho toàn bộ các lần gọi đệ quy
    visited := make(map[string]bool)
    
    // Gọi hàm đệ quy phụ trợ
    g.dfsRecursive(startVertex, visited)
}

func (g *Graph) dfsRecursive(current string, visited map[string]bool) {
    // Đánh dấu đỉnh hiện tại
    visited[current] = true
    fmt.Printf("Đang thăm: %s\n", current)
    
    // Thử đi sâu vào từng hàng xóm
    for _, neighbor := range g.adjList[current] {
        if !visited[neighbor] {
            // Đệ quy: Tạm dừng việc quét các hàng xóm còn lại để đi sâu xuống nhánh này
            g.dfsRecursive(neighbor, visited)
        }
    }
}

• Thời gian thực thi: Cũng là $O(V + E)$.
• Ứng dụng cốt lõi: Trả lời câu hỏi "Có tồn tại con đường nào từ A đến B không?". DFS đặc biệt mạnh mẽ trong các bài toán Phát hiện chu trình (Cycle Detection) để tránh Deadlock trong hệ thống cơ sở dữ liệu, hoặc sắp xếp thứ tự biên dịch mã nguồn (Topological Sort - cái nào cần build trước, cái nào build sau trong kiến trúc Microservices).

3. Tổng Kết Đánh Đổi

BFS có thể tìm đường đi ngắn nhất hoàn hảo, nhưng chỉ khi tất cả các cạnh đều có chi phí bằng nhau (Đồ thị không trọng số). Trong thực tế vận hành mạng lưới viễn thông hoặc hệ thống tàu điện, đoạn đường từ Ga A đến Ga B có thể mất 3 phút, nhưng từ B đến C mất tận 10 phút. Khoảng cách vật lý là khác biệt. Để giải bài toán đường đi ngắn nhất trên đồ thị có trọng số, chúng ta phải nâng cấp BFS bằng thuật toán vĩ đại nhất của ngành tối ưu hóa mạng lưới.