Thuật toán duyệt đồ thị BFS trong C#

Breadth-First Search (BFS) là một thuật toán duyệt đồ thị theo chiều rộng. BFS bắt đầu từ một đỉnh gốc và duyệt qua tất cả các đỉnh kề của nó trước khi chuyển sang các đỉnh kề của các đỉnh đó, sử dụng một hàng đợi (queue) để quản lý các đỉnh đang chờ được duyệt.

Dưới đây là mã nguồn C# cho thuật toán duyệt đồ thị sử dụng BFS:

using System;
using System.Collections.Generic;

class Graph
{
    private int vertices;
    private List<int>[] adjacencyList;

    // Khởi tạo đồ thị
    public Graph(int v)
    {
        vertices = v;
        adjacencyList = new List<int>[v];
        for (int i = 0; i < v; ++i)
            adjacencyList[i] = new List<int>();
    }

    // Thêm cạnh vào đồ thị
    public void AddEdge(int v, int w)
    {
        adjacencyList[v].Add(w); // Thêm w vào danh sách kề của v
    }

    // BFS sử dụng hàng đợi
    public void BFS(int start)
    {
        // Đánh dấu tất cả các đỉnh là chưa thăm
        bool[] visited = new bool[vertices];

        // Hàng đợi cho BFS
        Queue<int> queue = new Queue<int>();

        // Đánh dấu đỉnh bắt đầu là đã thăm và đưa vào hàng đợi
        visited[start] = true;
        queue.Enqueue(start);

        while (queue.Count != 0)
        {
            // Lấy đỉnh ở đầu hàng đợi ra
            int v = queue.Dequeue();
            Console.Write(v + " ");

            // Lấy tất cả các đỉnh kề của đỉnh v
            foreach (int neighbor in adjacencyList[v])
            {
                if (!visited[neighbor])
                {
                    // Nếu đỉnh kề chưa được thăm, đánh dấu nó và đưa vào hàng đợi
                    visited[neighbor] = true;
                    queue.Enqueue(neighbor);
                }
            }
        }
    }

    static void Main(string[] args)
    {
        Graph g = new Graph(4);

        g.AddEdge(0, 1);
        g.AddEdge(0, 2);
        g.AddEdge(1, 2);
        g.AddEdge(2, 0);
        g.AddEdge(2, 3);
        g.AddEdge(3, 3);

        Console.WriteLine("Duyệt đồ thị sử dụng BFS bắt đầu từ đỉnh 2:");

        g.BFS(2);
    }
}

Giải thích chi tiết:

1. Graph Class:

   • vertices: Số lượng đỉnh trong đồ thị.
   • adjacencyList: Mảng các danh sách kề, mỗi phần tử trong mảng là một danh sách các đỉnh kề với đỉnh tương ứng.

2. AddEdge Method:

   • Thêm một cạnh vào đồ thị. Đối với đồ thị có hướng, chỉ cần thêm đỉnh đích vào danh sách kề của đỉnh nguồn.

3. BFS Method:

   • Tham số:
     • start: Đỉnh bắt đầu duyệt BFS.
   • Biến:
     • visited: Mảng boolean để đánh dấu các đỉnh đã được thăm.
     • queue: Hàng đợi để quản lý các đỉnh đang chờ được duyệt.
   • Thuật toán:
     • Đánh dấu đỉnh bắt đầu là đã thăm và đưa nó vào hàng đợi.
     • Trong khi hàng đợi không rỗng:
       • Lấy đỉnh ở đầu hàng đợi ra và in nó ra.
       • Duyệt qua tất cả các đỉnh kề của đỉnh này. Nếu đỉnh kề chưa được thăm, đánh dấu nó là đã thăm và đưa vào hàng đợi.

4. Main Method:

   • Tạo đồ thị, thêm các cạnh vào đồ thị, và gọi phương thức BFS để duyệt đồ thị bắt đầu từ một đỉnh cụ thể.

Ưu điểm của BFS:

• BFS duyệt đồ thị theo chiều rộng, do đó nó đảm bảo tìm đường ngắn nhất (ít cạnh nhất) từ đỉnh gốc đến tất cả các đỉnh khác.
• BFS có thể tìm thấy tất cả các đỉnh ở khoảng cách $k$ từ đỉnh gốc trước khi tìm các đỉnh ở khoảng cách $k+1$.

Nhược điểm của BFS:

• BFS sử dụng nhiều bộ nhớ hơn DFS vì nó lưu trữ tất cả các đỉnh của mỗi mức trước khi chuyển sang mức tiếp theo.

Chương trình trên giúp bạn dễ dàng duyệt đồ thị sử dụng BFS trong C#. Bạn có thể chạy và thử nghiệm chương trình để hiểu rõ hơn về cách thức hoạt động của thuật toán này.