Đồ thị và BFS

Xe giao hàng đi từ kho qua các điểm nối nhau bằng đường. Từ kho tới điểm D phải qua ít nhất mấy điểm? Dữ liệu dạng "điểm nối với điểm" là đồ thị, và câu hỏi "ít bước nhất" được giải bằng BFS, dùng đúng Queue của chương 2.

Khái niệm

🕸️ Đồ thị (graph): tập các đỉnh (vertex) nối với nhau bằng cạnh (edge), ở bài này đỉnh là điểm giao hàng, cạnh là con đường.

🌊 BFS (breadth-first search, tìm theo chiều rộng): đi từ điểm xuất phát, thăm hết các điểm cách 1 bước, rồi tới các điểm cách 2 bước, cứ thế ra xa dần.

Đồ thị thường lưu bằng danh sách kề: mỗi đỉnh giữ list các đỉnh nối trực tiếp với nó. Trong C#, đó là Dictionary<string, List<string>>. Cây ở hai bài trước là một loại đồ thị không có vòng (đường đi quay lại đỉnh cũ).

Ví dụ

var roads = new Dictionary<string, List<string>>();
AddRoad("Kho", "A");
AddRoad("Kho", "B");
AddRoad("A", "C");
AddRoad("B", "C");
AddRoad("C", "D");

Dictionary<string, int> steps = Bfs("Kho");
foreach (var item in steps)
{
    Console.WriteLine($"{item.Key}: {item.Value}");
}

void AddRoad(string from, string to)
{
    if (!roads.ContainsKey(from))
    {
        roads[from] = new List<string>();
    }
    if (!roads.ContainsKey(to))
    {
        roads[to] = new List<string>();
    }
    roads[from].Add(to);
    roads[to].Add(from);
}

Dictionary<string, int> Bfs(string start)
{
    var distance = new Dictionary<string, int>();
    var queue = new Queue<string>();
    distance[start] = 0;
    queue.Enqueue(start);
    while (queue.Count > 0)
    {
        string current = queue.Dequeue();
        foreach (string next in roads[current])
        {
            if (!distance.ContainsKey(next))
            {
                distance[next] = distance[current] + 1;
                queue.Enqueue(next);
            }
        }
    }
    return distance;
}

• Đường đi được hai chiều, nên AddRoad thêm vào list của cả hai đầu.
• distance vừa ghi số bước, vừa đánh dấu điểm đã thăm để không thăm lại.
• Queue đảm bảo điểm gần được xử lý hết trước điểm xa, nên số bước ghi lần đầu cho mỗi điểm là ít nhất.
• Mỗi điểm vào queue một lần, mỗi con đường được xét từ hai đầu: O(số đỉnh + số cạnh).

Mô phỏng chạy cùng code trên một đồ thị khác, 6 điểm, để phần Thử ngay vẫn tự đoán được.

var roads = new Dictionary<string, List<string>>();
AddRoad("Kho", "A");
AddRoad("Kho", "B");
AddRoad("A", "C");
AddRoad("B", "D");
AddRoad("C", "E");
AddRoad("D", "E");

Dictionary<string, int> steps = Bfs("Kho");
foreach (var item in steps)
{
    Console.WriteLine($"{item.Key}: {item.Value}");
}

void AddRoad(string from, string to)
{
    if (!roads.ContainsKey(from))
    {
        roads[from] = new List<string>();
    }
    if (!roads.ContainsKey(to))
    {
        roads[to] = new List<string>();
    }
    roads[from].Add(to);
    roads[to].Add(from);
}

Dictionary<string, int> Bfs(string start)
{
    var distance = new Dictionary<string, int>();
    var queue = new Queue<string>();
    distance[start] = 0;
    queue.Enqueue(start);
    while (queue.Count > 0)
    {
        string current = queue.Dequeue();
        foreach (string next in roads[current])
        {
            if (!distance.ContainsKey(next))
            {
                distance[next] = distance[current] + 1;
                queue.Enqueue(next);
            }
        }
    }
    return distance;
}

Thử ngay

Chạy ví dụ, rồi thêm Console.WriteLine("Thăm " + current); ngay dưới dòng string current = queue.Dequeue(); và chạy lại.

Đoán trước khi chạy: D cách kho mấy bước? Các điểm được thăm theo thứ tự nào?

Thăm Kho
Thăm A
Thăm B
Thăm C
Thăm D
Kho: 0
A: 1
B: 1
C: 2
D: 3

Lỗi hay gặp

Không đánh dấu điểm đã thăm. Đường đi hai chiều và có vòng, nên từ một điểm luôn quay lại được điểm cũ. Không đánh dấu thì BFS đi vòng mãi, queue không bao giờ rỗng.

// SAI — không kiểm tra đã thăm, chạy mãi không dừng
foreach (string next in roads[current])
{
    queue.Enqueue(next);
}

// ĐÚNG — chỉ thêm điểm chưa có trong distance
foreach (string next in roads[current])
{
    if (!distance.ContainsKey(next))
    {
        distance[next] = distance[current] + 1;
        queue.Enqueue(next);
    }
}

Tóm tắt

• Đồ thị gồm đỉnh và cạnh, lưu bằng danh sách kề Dictionary<string, List<string>>.
• BFS dùng queue, thăm theo từng lớp khoảng cách.
• BFS cho số bước ít nhất khi mọi cạnh dài như nhau.
• Luôn đánh dấu đỉnh đã thăm.