Рубрики

LCA для общих или n-арных деревьев (подход Sparse Matrix DP <O (nlogn), O (logn)>)

В предыдущих статьях мы обсуждали, как вычислять самого низкого общего предка (LCA) для двоичного дерева и двоичного дерева поиска ( это , это и это ). Теперь давайте посмотрим на метод, который может вычислять LCA для любого дерева (не только для двоичного дерева). В нашем методе мы используем динамическое программирование с подходом разреженной матрицы. Этот метод очень удобен и быстр, когда вам нужно ответить на несколько запросов LCA для дерева.

Пререквизиты: —
1) ДФС
2) Базовые знания DP ( это и это )
3) Минимальный запрос по дальности (квадратное разложение и разреженная таблица)

Наивный подход: — O (n)

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

Реализация на С ++ для наивного подхода приведена ниже:

/ * Программа для поиска LCA n1 и n2, используя одну DFS на

   дерево */

#include "iostream"
#include "vector"

using namespace std;

  
// Максимальное количество узлов составляет 100000, а узлы
// пронумерованы от 1 до 100000
#define MAXN 100001

  

vector < int > tree[MAXN];

int path[3][MAXN]; // сохраняем путь от корня до узла

  
// сохраняем путь от корня до узла

void dfs(int cur, int prev, int pathNumber, int ptr,

                             int node, bool &flag)

{

    for (int i=0; i<tree[cur].size(); i++)

    {

        if (tree[cur][i] != prev and !flag)

        {

            // вставляем текущий узел в путь

            path[pathNumber][ptr] = tree[cur][i];

            if (tree[cur][i] == node)

            {

                // узел найден

                flag = true;

  

                // завершаем путь

                path[pathNumber][ptr+1] = -1;

                return;

            }

            dfs(tree[cur][i], cur, pathNumber, ptr+1,

                                        node, flag);

        }

    }

}

  
// Эта функция сравнивает путь от root до 'a' и root
// в 'b' и возвращает LCA a и b. Сложность времени: O (n)

int LCA(int a, int b)

{

    // тривиальный случай

    if (a == b)

        return a;

  

    // установка корня в качестве первого элемента в пути

    path[1][0] = path[2][0] = 1;

  

    // вычисляем путь от корня до

    bool flag = false;

    dfs(1, 0, 1, 1, a, flag);

  

    // вычисляем путь от корня до б

    flag = false;

    dfs(1, 0, 2, 1, b, flag);

  

    // работает до пути 1 и пути 2

    int i = 0;

    while (path[1][i] == path[2][i])

        i++;

  

    // возвращает последний соответствующий узел в путях

    return path[1][i-1];

}

  

void addEdge(int a,int b)

{

    tree[a].push_back(b);

    tree[b].push_back(a);

}

  
// Код драйвера

int main()

{

    int n = 8; // Количество узлов

    addEdge(1,2);

    addEdge(1,3);

    addEdge(2,4);

    addEdge(2,5);

    addEdge(2,6);

    addEdge(3,7);

    addEdge(3,8);

  

    cout << "LCA(4, 7) = " << LCA(4,7) << endl;

    cout << "LCA(4, 6) = " << LCA(4,6) << endl;

    return 0;

}

Выход:

LCA(4, 7) = 1
LCA(4, 6) = 2

Подход с разреженной матрицей (O (nlogn) предварительная обработка, O (log n) — запрос)

Предварительные вычисления : — Здесь мы храним 2 ^ i-го родителя для каждого узла, где 0 <= i <LEVEL, здесь «LEVEL» — это постоянное целое число, которое сообщает максимально возможное число 2 ^ i-го предка.
Поэтому мы предполагаем наихудший случай, чтобы увидеть, каково значение постоянной LEVEL. В нашем худшем случае каждый узел в нашем дереве будет иметь не более 1 родителя и 1 потомка, или мы можем сказать, что он просто сводится к связанному списку.
Итак, в этом случае LEVEL = ceil ( log(number of nodes) ).
Мы также предварительно вычисляем высоту для каждого узла, используя одну dfs за O (n) времени.

int n             // number of nodes
int parent[MAXN][LEVEL] // all initialized to -1 

parent[node][0] : contains the 2^0th(first) 
parent of all the nodes pre-computed using DFS

// Sparse matrix Approach
for node -> 1 to n :        
  for i-> 1 to LEVEL :
    if ( parent[node][i-1] != -1 ) :
      parent[node][i]  =  
         parent[ parent[node][i-1] ][i-1]

Теперь, как мы видим из приведенного выше кода динамического программирования, выполняется два вложенных цикла, которые проходят по всему их диапазону соответственно.
Следовательно, можно легко сделать вывод, что его асимптотическая временная сложность равна O (количество узлов * LEVEL) ~ O (n * LEVEL) ~ O (nlogn).

Вернуть LCA (u, v) : —
1) Первый шаг — привести оба узла на одну высоту. Как мы уже предварительно вычислили высоты для каждого узла. Сначала мы рассчитаем разницу в высотах u и v (скажем, v> = u). Теперь нам нужен узел 'v', чтобы перейти выше на h узлов. Это легко сделать за время O (log h) (где h — разница высот u и v), поскольку мы уже сохранили родителя 2 ^ i для каждого узла. Этот процесс точно такой же, как и вычисление x ^ y за O (log y) времени. (Смотрите код для лучшего понимания).

2) Теперь и u, и v узлы находятся на одной высоте. Поэтому теперь еще раз мы будем использовать стратегию прыжков 2 ^ i, чтобы достичь первого Общего Родителя u и v.

Pseudo-code:
For i->  LEVEL to 0 :
      If parent[u][i] != parent[v][i] :
           u = parent[u][i]
           v = parent[v][i]

Реализация вышеуказанного алгоритма на C ++ приведена ниже:

// Разреженный матричный подход DP для нахождения LCA двух узлов
#include <bits/stdc++.h>

using namespace std;

#define MAXN 100000
#define level 18

  

vector <int> tree[MAXN];

int depth[MAXN];

int parent[MAXN][level];

  
// предварительно вычисляем глубину для каждого узла и их
// первый родитель (2 ^ 0-й родитель)
// временная сложность: O (n)

void dfs(int cur, int prev)

{

    depth[cur] = depth[prev] + 1;

    parent[cur][0] = prev;

    for (int i=0; i<tree[cur].size(); i++)

    {

        if (tree[cur][i] != prev)

            dfs(tree[cur][i], cur);

    }

}

  
// Динамическое программирование разреженного матричного подхода
// заполнение 2 ^ i родителя для каждого узла
// Сложность времени: O (nlogn)

void precomputeSparseMatrix(int n)

{

    for (int i=1; i<level; i++)

    {

        for (int node = 1; node <= n; node++)

        {

            if (parent[node][i-1] != -1)

                parent[node][i] =

                    parent[parent[node][i-1]][i-1];

        }

    }

}

  
// Возвращаем LCA для u и v
// Сложность времени: O (log n)

int lca(int u, int v)

{

    if (depth[v] < depth[u])

        swap(u, v);

  

    int diff = depth[v] - depth[u];

  

    // Шаг 1 псевдокода

    for (int i=0; i<level; i++)

        if ((diff>>i)&1)

            v = parent[v][i];

  

    // теперь глубина [и] == глубина [у]

    if (u == v)

        return u;

  

    // Шаг 2 псевдокода

    for (int i=level-1; i>=0; i--)

        if (parent[u][i] != parent[v][i])

        {

            u = parent[u][i];

            v = parent[v][i];

        }

  

    return parent[u][0];

}

  

void addEdge(int u,int v)

{

    tree[u].push_back(v);

    tree[v].push_back(u);

}

  
// функция драйвера

int main()

{

    memset(parent,-1,sizeof(parent));

    int n = 8;

    addEdge(1,2);

    addEdge(1,3);

    addEdge(2,4);

    addEdge(2,5);

    addEdge(2,6);

    addEdge(3,7);

    addEdge(3,8);

    depth[0] = 0;

  

    // выполняется DFS и предрасчет глубины

    // каждого узла.

    dfs(1,0);

  

    // Предварительный расчет 2 ^ i-го предка для каждого узла

    precomputeSparseMatrix(n);

  

    // вызов функции LCA

    cout << "LCA(4, 7) = " << lca(4,7) << endl;

    cout << "LCA(4, 6) = " << lca(4,6) << endl;

    return 0;

}

Выход:

LCA(4,7) = 1
LCA(4,6) = 2

Сложность времени: Сложность времени для ответа на один запрос LCA будет O (logn), но в общей сложности времени преобладает предварительный расчет 2 ^ i-го (0 <= i <= level) предка для каждого узла. Следовательно, общая асимптотическая временная сложность будет O (n * logn), а пространственная сложность будет O (nlogn) для хранения данных о предках каждого узла.

Эта статья предоставлена Нитишем Кумаром . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

LCA для общих или n-арных деревьев (подход Sparse Matrix DP <O (nlogn), O (logn)>)

0.00 (0%) 0 votes