STDIO
Tìm kiếm gần đây
    Nội dung
    0
    0
    Chia sẻ
    Nội dung
    0
    0
    Chia sẻ

    Thuật toán Breadth First Search

    Giới thiệu, khái quát, trình bày và cung cấp code mẫu về thuật toán Breadth First Search (BFS – Tìm kiếm theo chiều sâu).
    19/09/2015 02/08/2020 6 phút đọc
    Thuật toán Breadth First Search

    Thuật toán Breadth First Search

    Thuật toán Breadth First Search (BFS - Tìm kiếm theo chiều rộng) là thuật toán xét (duyệt) hoặc tìm kiếm trên cây và đồ thị, có chiến lược tìm kiếm mù (tìm kiếm không có định hướng, không chú ý đến thông tin, giá trị được duyệt).

    Breadth First Search (BFS) cùng với Depth First Search (DFS) là 2 thuật toán cơ bản để chuẩn bị ra các thuật toán phức tạp hơn khi mới tiếp cận Trí tuệ nhân tạo.

    Ý tưởng thuật toán

    Từ một đỉnh (nút) gốc ban đầu.

    • Xác định và lần lượt duyệt các đỉnh kề xung quanh đỉnh gốc vừa xét.
      • Tiếp tục quá trình duyệt qua các đỉnh kề đỉnh vừa xét cho đến khi đạt được kết quả cần tìm hoặc duyệt qua tất cả các đỉnh.

    Thuật giải

    Một số quy ước:

    • Open: là tập hợp các đỉnh chờ được xét ở bước tiếp theo theo hàng đợi (hàng đợi: dãy các phần tử mà khi thêm phần tử vào sẽ thêm vào cuối dãy, còn khi lấy phần tử ra sẽ lấy ở phần tử đứng đầu dãy).
    • Close: là tập hợp các đỉnh đã xét, đã duyệt qua.
    • s: là đỉnh xuất phát, đỉnh gốc ban đầu trong quá trình tìm kiếm.
    • g: đỉnh đích cần tìm.
    • p: đỉnh đang xét, đang duyệt.

    Trình bày thuật giải:

    • Bước 1: Tập Open chứa đỉnh gốc s chờ được xét.
    • Bước 2: Kiểm tra tập Open có rỗng không.
      • Nếu tập Open không rỗng, lấy một đỉnh ra khỏi tập Open làm đỉnh đang xét p. Nếu p là đỉnh g cần tìm, kết thúc tìm kiếm.
      • Nếu tập Open rỗng, tiến đến bước 4.
    • Bước 3: Đưa đỉnh p vào tập Close, sau đó xác định các đỉnh kề với đỉnh p vừa xét. Nếu các đỉnh kề không thuộc tập Close, đưa chúng vào cuối tập Open. Quay lại bước 2.
    • Bước 4: Kết luận không tìm ra đỉnh đích cần tìm.

    Code mẫu thuật toán BFS

    Hiện thực thuật toán này theo ma trận kề bằng ngôn ngữ C++.

    #include <stdio.h>
    #include <queue>
    #include <conio.h>
    using namespace std;
    
    // dinh nghia lop do thi
    class Graph
    {
    private:
    	int n;
    	int **edge;
    public:
    	Graph(int size = 2);
    	~Graph();
    	bool isConnected(int, int);
    	void addEdge(int, int);
    	void breadthFirstSearch(int, int);
    };
    
    Graph::Graph(int size)
    {
    	int i, j;
    
    	// xac dinh so dinh cua do thi
    	n = size < 2 ? 2 : size;
    
    	// tao ra cac dinh trong do thi
    	edge = new int*[n];
    	for (i = 0; i < n; i++)
    		edge[i] = new int[n];
    	
    	// mac dinh giua cac dinh khong co ket noi voi nhau (= 0)
    	for (i = 0; i < n; i++)
    		for (j = 0; j < n; j++)
    			edge[i][j] = 0;
    }
    
    Graph::~Graph()
    {
    	for (int i = 0; i < n; ++i)
    		delete[] edge[i];
    	delete[] edge;
    }
    
    // kiem tra giua hai dinh co ke nhau hay khong
    bool Graph::isConnected(int x, int y)
    {
    	return edge[x - 1][y - 1] == 1;
    }
    
    // tao canh noi giua hai dinh, lam cho hai dinh ke nhau
    void Graph::addEdge(int x, int y)
    {
    	if (x < 1 || x > n || y < 1 || y > n)
    		return;
    
    	edge[x - 1][y - 1] = edge[y - 1][x - 1] = 1;
    }
    
    void Graph::breadthFirstSearch(int s, int g)
    {
    	if (s > n || s < 0 || g > n || g < 0)
    	{
    		printf("Could not traverse this graph with your request\n");
    		return;
    	}
    queue<int> open; bool *close = new bool[n]; int i; int p; // mac dinh cac dinh chua duoc duyet for (i = 0; i < n; i++) close[i] = false; // dua dinh goc s vao queue open, chuan bi duyet open.push(s); printf("With Breadth first Search , we have vertex(s):\n"); while (!open.empty()) { // lay mot dinh ra khoi open tro thanh dinh dang xet p do { if (open.empty()) break; p = open.front(); open.pop(); } while (close[p - 1] == true); // in ra dinh dang xet printf("%d ", p); // p da duyet qua close[p - 1] = true; // ket thuc duyet khi tim ra ket qua can tim if (p == g) break; // tim dinh ke voi dinh dang xet, dinh nao chua duoc duyet dua vao open for (i = 1; i <= n; i++) { if (isConnected(p, i) && !close[i - 1]) { open.push(i); } } } printf("\n"); delete[] close; }

    Ví dụ

    Cho đồ thị như hình vẽ

    Đồ thị BFS.

    Khởi tạo một đồ thị có 9 đỉnh và có cạnh nối các đỉnh kề như hình vẽ.

    void main()
    {
    	// khoi tao do thi
    	Graph g(9);
    
    	// tao canh noi giua cac dinh ke
    	g.addEdge(1, 2);
    	g.addEdge(1, 3);
    	g.addEdge(1, 4);
    	g.addEdge(2, 5);
    	g.addEdge(2, 6);
    	g.addEdge(3, 4);
    	g.addEdge(3, 5);
    	g.addEdge(3, 7);
    	g.addEdge(3, 8); 
    	g.addEdge(3, 9);
    }

    Chọn đỉnh gốc để duyệt là đỉnh 1 và cần tìm đỉnh 8, thực hiện duyệt ngay sau khi tạo cạnh nối giữa các đỉnh kề.

    void main()
    {
     	// khoi tao do thi
    	Graph g(9);
    
    	// tao canh noi giua cac dinh ke
    	g.addEdge(1, 2);
    	g.addEdge(1, 3);
    	g.addEdge(1, 4);
    	g.addEdge(2, 5);
    	g.addEdge(2, 6);
    	g.addEdge(3, 4);
    	g.addEdge(3, 5);
    	g.addEdge(3, 7);
    	g.addEdge(3, 8); 
    	g.addEdge(3, 9);
    
    	// duyet bang Breadth First Search
    	g.breadthFirstSearch(1, 8);
    }

    Bảng bên dưới thể hiện quá trình duyệt từ đỉnh 1 đến đỉnh 8.

    ĐỈNH ĐANG XÉT CÁC ĐỈNH KỀ Open Close
        {1} {}
    1 {2; 3; 4} {2, 3, 4} {1}
    2 {1; 5; 6} {3; 4; 5; 6} {1; 2}
    3 {1; 4; 5; 7; 8; 9} {4; 5; 6; 4; 5; 7; 8; 9} {1; 2; 3}
    4 {1; 3} {5; 6; 4; 5; 7; 8; 9} {1; 2; 3; 4}
    5 {2; 3} {6; 4; 5; 7; 8; 9} {1; 2; 3; 4; 5}
    6 {2} {4; 5; 7; 8; 9} {1; 2; 3; 4; 5; 6}
    7 {3} {8; 9} {1; 2; 3; 4; 5; 6; 7}
    8 {3} {9} {1; 2; 3; 4; 5; 6; 7; 8}

    Nhận xét

    Ưu điểm

    • Xét duyệt tất cả các đỉnh để trả về kết quả.
    • Nếu số đỉnh là hữu hạn, thuật toán chắc chắn tìm ra kết quả.

    Khuyết điểm

    • Mang tính chất vét cạn, không nên áp dụng nếu duyệt số đỉnh quá lớn.
    • Mang tính chất mù quáng, duyệt tất cả đỉnh, không chú ý đến thông tin trong các đỉnh để duyệt hiệu quả, dẫn đến duyệt qua các đỉnh không cần thiết.

    Download mã nguồn

    Mã nguồn của bài viết và nhiều giải thuật khác được lưu trữ tại đây.

    0 Bình luận
    Giải Thuật Lập Trình

    Giải Thuật Lập Trình

    STDIO Training - Chia sẻ các giải thuật lập trình từ cổ điển đến hiện đại.

    Khi bạn nhấn vào sản phẩm do chúng tôi đề xuất và mua hàng, chúng tôi sẽ nhận được hoa hồng. Điều này hỗ trợ chúng tôi có thêm kinh phí tạo nhiều nội dung hữu ích. Tìm hiểu thêm.
    STDIO

    Trang chính

    Công ty TNHH STDIO

    • 30, Trịnh Đình Thảo, Hòa Thạnh, Tân Phú, Hồ Chí Minh
      +84 28.36205514 - +84 942.111912
      developer@stdio.vn
    • 383/1 Quang Trung, Phường 10, Quận Gò Vấp, Hồ Chí Minh
      Số giấy phép ĐKKD: 0311563559 do sở Kế hoạch và Đầu Tư TPHCM cấp ngày 23/02/2012
    ©STDIO, 2013 - 2021