Любопытно найти глубину графа алгоритма - PullRequest
Новая
       4

Любопытно найти глубину графа алгоритма

0 голосов
/ 06 ноября 2018

Я очень новичок в структуре данных и алгоритме, и сегодня мы изучаем график, но я не понимаю этот код, вот он, этот код используется для определения глубины графика: 

struct Node {
    int id;
    int weight;

    Node(int id_, int weight_)
    {
        id = id_;
        weight = weight_;
    }
};

int depth_tree(vector<Node> graph[], int root)
{
    if (graph[root].size() == 0) {
        return 0;
    } else {
        int max_d = depth_tree(graph, graph[root][0].id);
        for (int i = 1; i < graph[root].size(); i++) {
            int d = depth_tree(graph, graph[root][i].id);
            if (d > max_d) {
                max_d = d;
            }
        }
        return max_d + 1;
    }
}

int main()
{
    int n;
    cin >> n;
    vector<Node> graph[n];

    int u, v;
    for (int i = 0; i < n - 1; i++) {
        cin >> u >> v;
        Node temp_uv(v, 0);
        graph[u].push_back(temp_uv);
    }

    cout << depth_tree(graph, 0);

}

я не понимаю в 2-х точках:

FIRST : при расчете глубины int max_d = depth_tree(graph, graph[root][0].id я понимаю, что это означает, что требуется идентификатор элемента [0] root Node например при вводе 

5
0 1
0 2
1 3
3 4

там, что max_d будет 1, а 0 должно быть u при вводе в main(), но root (root - это u, а не изменение значения), поэтому я думаю, что при вызове depth_tree(graph, 0) просто найти глубину 0 ???????

ВТОРОЙ : почему int max_d = depth_tree(graph, graph[root][0].id) ??? как в примере выше 1 2 3 4 ??? поэтому ответ должен быть 4 (неправильно, но я не понимаю)

ПОЖАЛУЙСТА, ПОЖАЛУЙСТА, ПОЯСНИТЕ ЭТУ ЛОГИКУ КОДА, СПАСИБО МНОГО, мне очень любопытно

1 Ответ

0 голосов
/ 07 ноября 2018

Вы начинаете с определения слова Глубина: Глубина узла - это количество ребер от узла до корневого узла дерева.

Основная идея найти максимальную глубину - это нарезать задачу на меньшую.

Какая самая простая проблема: какова глубина корневого узла листа? Ну, это 0, потому что под листом нет детей, и поэтому вы не можете пересечь любое ребро. 

if (graph[root].size() == 0) { // here root only means the current node
    return 0;

Далее мы спрашиваем: какова глубина узла, который не является листом? Ну, это зависит от глубины детей. Здесь алгоритм ищет максимальную глубину, поэтому нам нужно искать максимальную глубину дочерних элементов. 

int max_d = depth_tree(..., ...[0]...);

for (int i = 1; i < graph[root].size(); i++) {

    // the loop starts at 1 because 0 is the highest depth so far

    int d = depth_tree(..., ...[i]...);

    if (d > max_d) { // if the new child is deeper

       // then this is the new max depth

       max_d = d;
    }
}

И как только мы узнаем это, и поскольку между дочерним узлом и текущим узлом есть грань, мы добавляем 1. 

return max_d + 1;
...