Làm sao để tìm nút trung tâm của cây N-ary?

Cho một cây N-ary có N nút được đánh số từ 0 đến N-1 và danh sách các cạnh vô hướng, nhiệm vụ là tìm (các) nút ở tâm của cây đã cho.

Trước khi tìm hiểu cách tìm nút ở giữa của cây ta cần hiểu một vài thuật ngữ sau:

• Độ lệch tâm: Độ lệch tâm của bất kỳ đỉnh V nào trong một cây nhất định là khoảng cách tối đa giữa đỉnh V đã cho và bất kỳ đỉnh nào khác của cây. 
• Tâm: Tâm của cây là đỉnh có độ lệch tâm nhỏ nhất.

Vây, để tìm được tâm chúng ta phải giảm thiểu độ lệch tâm này. 

Ví dụ:

Đầu vào: 

• N = 4,
• Cạnh[] = { (1, 0), (1, 2), (1, 3)} 

Đầu ra: 1 
Giải thích: 

Đầu vào: 

• N = 6,
• Cạnh[] = { (0, 3), (1, 3), (2, 3), (4, 3), (5, 4)} 

Đầu ra: 3, 4 
Giải thích: 

Có thể quan sát thấy đường đi có độ lệch tâm cực đại là đường kính của cây. Do đó, tâm của đường kính cây cũng sẽ là tâm của cây.

• Nếu đường kính bao gồm số nút lẻ thì chỉ tồn tại 1 tâm.
• Nếu đường kính bao gồm số nút chẵn thì có 2 nút trung tâm.

• Độ phức tạp về thời gian: O(N) 
• Không gian phụ trợ: O(N)

Dưới đây là cách thực hiện phương pháp trên với c++:  

Hàm thêm cạnh giữa 2 điểm

void addedge(int a, int b)
{
    tree[a].push_back(b);
    tree[b].push_back(a);
}

Hàm lấy và trả về nút xa nhất từ ​​một đỉnh nhất định

void farthestNode(int vertex, int parent,
                  int height, int& maxHeight,
                  int& maxHeightNode)
{
    if (height > maxHeight) {
        maxHeight = height;
        maxHeightNode = vertex;
    }
    for (auto i : tree[vertex]) {
        if (i == parent)
            continue;
 
        farthestNode(i, vertex,
                     height + 1,
                     maxHeight,
                     maxHeightNode);
    }
}

Hàm lưu trữ đường đi từ đỉnh đã cho đến đỉnh đích trong đường dẫn vectơ

bool getDiameterPath(int vertex,
                     int targetVertex,
                     int parent,
                     vector<int>& path)
{
    if (vertex == targetVertex) {
 
        path.push_back(vertex);
        return true;
    }
 
    for (auto i : tree[vertex]) {
        if (i == parent)
            continue;
 
        if (getDiameterPath(i, targetVertex,
                            vertex, path)) {
            path.push_back(vertex);
            return true;
        }
    }
 
    return false;
}

Hàm tìm node trung tâm

void FindCenter(int n)
{
    int maxHeight = -1;

    int maxHeightNode = -1;
 
    farthestNode(0, -1, 0, maxHeight,
                 maxHeightNode);

    int leaf1 = maxHeightNode;

    maxHeight = -1;
    farthestNode(maxHeightNode,
                 -1, 0, maxHeight,
                 maxHeightNode);
    int leaf2 = maxHeightNode;
 
    vector<int> path;
 
    getDiameterPath(leaf1, leaf2,
                    -1, path);
 
    int pathSize = path.size();
 
    if (pathSize % 2) {
        cout << path[pathSize / 2]
             << endl;
    }
    else {
        cout << path[pathSize / 2]
             << ", "
             << path[(pathSize - 1) / 2]
             << endl;
    }
}

Kết hợp code

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

void addedge(int a, int b)
{
    tree[a].push_back(b);
    tree[b].push_back(a);
} 

void farthestNode(int vertex, int parent,
                  int height, int& maxHeight,
                  int& maxHeightNode)
{
    if (height > maxHeight) {
        maxHeight = height;
        maxHeightNode = vertex;
    }
    for (auto i : tree[vertex]) {
        if (i == parent)
            continue;
 
        farthestNode(i, vertex,
                     height + 1,
                     maxHeight,
                     maxHeightNode);
    }
}

bool getDiameterPath(int vertex,
                     int targetVertex,
                     int parent,
                     vector<int>& path)
{
    if (vertex == targetVertex) {
 
        path.push_back(vertex);
        return true;
    }
 
    for (auto i : tree[vertex]) {
        if (i == parent)
            continue;
 
        if (getDiameterPath(i, targetVertex,
                            vertex, path)) {
            path.push_back(vertex);
            return true;
        }
    }
 
    return false;
}

void FindCenter(int n)
{
    int maxHeight = -1;

    int maxHeightNode = -1;
 
    farthestNode(0, -1, 0, maxHeight,
                 maxHeightNode);

    int leaf1 = maxHeightNode;

    maxHeight = -1;
    farthestNode(maxHeightNode,
                 -1, 0, maxHeight,
                 maxHeightNode);
    int leaf2 = maxHeightNode;
 
    vector<int> path;
 
    getDiameterPath(leaf1, leaf2,
                    -1, path);
 
    int pathSize = path.size();
 
    if (pathSize % 2) {
        cout << path[pathSize / 2]
             << endl;
    }
    else {
        cout << path[pathSize / 2]
             << ", "
             << path[(pathSize - 1) / 2]
             << endl;
    }
}

map<int, vector<int> > tree;
int main()
{
    int N = 4;
    addedge(1, 0);
    addedge(1, 2);
    addedge(1, 3);
 
    FindCenter(N);
 
    return 0;
}

Tài liệu tham khảo: Find the node at center