Đếm số nút tại cấp độ cho trước trong cây dùng BFS trong C++

Cho một đồ thị vô hướng chứa các nút của cây làm đỉnh. Mục tiêu: tìm số nút tại cấp độ (level) cho trước của cây sử dụng thuật toán BFS (breadth first search).

Thuật toán BFS: bắt đầu từ nút cấp độ 0, duyệt tất cả nút trực tiếp kết nối cấp độ 1, sau đó cấp độ tiếp theo, v.v.

• Duyệt nút ngang tại cấp độ hiện tại.
• Duyệt nút cấp độ tiếp theo theo cách tương tự.

Hiểu qua ví dụ

Đầu vào: level = 2

Đầu ra: Số nút tại cấp độ 2: 1

Giải thích: Tất cả cấp độ chỉ có 1 nút.

Đầu vào: level = 1

Đầu ra: Số nút tại cấp độ 1: 2

Giải thích: Các nút: 1, 2.

Phương pháp sử dụng

Duyệt từng nút và gán cấp độ = cấp độ cha + 1. Biểu diễn đồ thị bằng danh sách kề.

Nếu nút bắt đầu là 0:

• level[0] = 0
• level[1] = level[0] + 1 = 1, level[2] = level[0] + 1 = 1
• level[3] = level[2] + 1 = 2, level[4] = level[2] + 1 = 2

• Tạo lớp node biểu diễn đồ thị với data = số đỉnh, next = con trỏ danh sách kề.
• Phương thức insert(int val, int point) thêm cạnh: thêm val vào danh sách kề của point và ngược lại.
• Hàm count_nodes(int a, int b) trả về số nút cấp độ b từ nút nguồn a.
• Khởi tạo count = 0, mảng check bool, mảng arr lưu cấp độ.
• Đặt tất cả đỉnh chưa thăm: check[i] = false, arr[i] = 0.
• Tạo hàng đợi l1 cho BFS.
• Đánh dấu nút bắt đầu đã thăm: check[a] = true, thêm vào l1, arr[a] = 0.

• Khi hàng đợi không rỗng: lấy phần tử đầu a = l1.front(), l1.pop_front().
• Đánh dấu các đỉnh kề chưa thăm là đã thăm, thêm vào hàng đợi, gán cấp độ = cấp độ a + 1.
• Sau vòng lặp, duyệt arr[], nếu arr[i] == b tăng count.
• Trả về count.

Ví dụ mã nguồn

#include <bits/stdc++.h> 
using namespace std; 

class node { 
    int data; 
    list<int> *next; 
public: 
    node(int data) { 
        this->data = data; 
        next = new list<int>[data]; 
    } 
    void insert(int val, int point) { 
        next[val].push_back(point); 
        next[point].push_back(val); 
    } 
    int count_nodes(int a, int b); 
}; 

int node::count_nodes(int a, int b) { 
    int count = 0; 
    bool *check = new bool[data]; 
    int arr[data]; 
    for (int i = 0; i < data; i++) { 
        check[i] = false; 
        arr[i] = 0; 
    } 
    list<int> l1; 
    check[a] = true; 
    l1.push_back(a); 
    arr[a] = 0; 
    while (!l1.empty()) { 
        a = l1.front(); 
        l1.pop_front(); 
        for (auto it = next[a].begin(); it != next[a].end(); ++it) { 
            if (!check[*it]) { 
                arr[*it] = arr[a] + 1; 
                check[*it] = true; 
                l1.push_back(*it); 
            } 
        } 
    } 
    for (int i = 0; i < data; i++) { 
        if (arr[i] == b) count++; 
    } 
    return count; 
} 

int main() { 
    node n1(5); 
    n1.insert(1, 2); 
    n1.insert(0, 3); 
    n1.insert(1, 3); 
    n1.insert(2, 4); 
    int level = 1; 
    cout << "Count of number of nodes at given level in a tree using BFS are: " << n1.count_nodes(0, level); 
    return 0; 
}

Chạy mã trên cho kết quả:

Kết quả

Count of number of nodes at given level in a tree using BFS are: 1