Алгоритм указателя перехода

Опубликовано: 15 Января, 2022

Алгоритм указателя перехода - это метод разработки параллельных алгоритмов, которые работают со структурами указателей, такими как массивы или связанный список. Этот алгоритм обычно используется для определения корня леса корневого дерева.

В алгоритме указателя перехода мы предварительно обрабатываем дерево, чтобы можно было ответить на запросы, чтобы найти любого родителя любого узла в дереве с временной сложностью O (log n) .

Алгоритм указателя перехода связывает до log 2 n указателей с каждой вершиной дерева. Эти указатели называются указателями перехода, потому что они прыгают вверх по дереву к корневому узлу дерева. Для любого узла дерева обработки алгоритм сохраняет массив перемычек длиной l, где l = log2 (depth (v)) . I-й элемент этого массива указывает на 2-й родительский элемент узла v . Эта структура данных помогает нам перепрыгнуть половину дерева с любого заданного узла. Когда алгоритму предлагается обработать запрос, чтобы найти любого родителя любого узла в дереве, мы многократно перепрыгиваем вверх по дереву, используя эти указатели. Количество переходов будет не более log n, и поэтому на любую проблему с поиском родителя любого узла в дереве можно ответить с временной сложностью O (log n).
В указателе перехода есть указатель от узла N до j-го родителя N, для
j = 1, 2, 4, 8,… и так далее. Таким образом , мы сохраняем 2 Ith родителя каждого узла.

Алгоритм указателя перехода в основном работает по принципу динамического программирования, когда мы используем предварительно вычисленный результат для нахождения следующего результата . Выполнив несколько простых вычислений, мы можем вычислить математическую формулу, согласно которой для любого узла k, 2 j- й родитель k равен 2 j-1- му родительскому элементу 2 j-1- го родителя k .

Краткое объяснение этой формулы дано ниже в разделе алгоритмов.

Чаще всего этот алгоритм используется для решения запросов, в которых нам нужно найти предка любого узла с временной сложностью O (log n).

График для реализации алгоритма указателя перехода:

Представление массива переходов, в котором хранится 2 ^ i-й родитель всех узлов:

Примеры:

 Вход: 0-й родитель узла 2 
Выход: 0-й родитель узла 2 = 2

Вход: 2-й родитель узла 4
Выход: 2-й родитель узла 4 = 2

Вход: третий родитель узла 8 
Выход: 3-й родитель узла 8 = 1

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Алгоритм :
Вот алгоритм для реализации алгоритма указателя перехода для поиска любого родителя любого узла в графе. Мы определяем матрицу перехода с помощью динамического программирования . Здесь мы обозначаем корневой узел как R и изначально предполагаем, что родительский узел корневого узла равен 0, что означает, что у этого узла нет родителя . Теперь, глядя на график и массив, показанный на приведенной выше диаграмме, мы можем легко понять приведенную выше формулу для определения 2 i- го родителя каждого узла. Если мы посмотрим на узел со значением 8 мы видим , что его 2 0 - й родитель 10, теперь найти свою 2 1 - го родителя , мы видим , что это 2 1 - й родитель 2 0 - го родителя узла со значением 10 и здесь 10 - это 2 0- й родитель для 8, это означает, что 2 1- й родитель узла 8 является 2 0 -м родительским элементом 2 0- го родителя узла 8 . Точно так же мы также можем видеть, что 2 2- й родительский узел 8 равен 5, который является 2 1 -м родительским элементом 2 1- го родителя узла 8, т.е. 2 1- й родительский узел узла со значением 9 .
Таким образом , в этом случае мы можем вычислить массив указателей прыжковых для всех узлов , чтобы хранить их 2 - й я родитель.

Ниже приведен псевдокод для вычисления матрицы указателя прыжка , что магазин 2 - я я родитель всех узлов в дереве.

 jump [k] [j] = указывает на 2 ^ j-й родитель k    
             = 2 ^ j-1-й родитель (2 ^ j-1-й родитель k)       
             = прыжок [прыжок [i] [j-1] [j-1] 

Implementation: Below is the code to implement the above algorithm to find any parent of any node in O( logn ) time complexity.

C++

// C++ program to implement Jump pointer algorithm
#include <bits/stdc++.h>
using namespace std;
 
int R = 0;
// n -> it represent total number of nodes
// len -> it is the maximum length of array
// to hold parent of each node.
// In worst case, the highest value of
// parent a node can have is n-1.
// 2 ^ len <= n-1
// len = O(log2n)
int getLen(int n)
{
    int len = (int)(log(n) / log(2)) + 1;
    return len;
}
 
// jump represent 2D matrix to hold parent of node in jump matrix
// here we pass reference of 2D matrix so that the change made
// occur directly to the original matrix
// len is same as defined above
// n is total nodes in graph
void set_jump_pointer(vector<vector<int> >& jump,
                      int* node, int len, int n)
{
    for (int j = 1; j <= len; j++)
        for (int i = 0; i < n; i++)
            jump[node[i]][j] = jump[jump[node[i]][j - 1]][j - 1];
}
 
// c -> it represent child
// p -> it represent parent
// i -> it represent node number
// p=0 means the node is root node
// here also we pass reference of 2D matrix
// and depth vector so that the change made
// occur directly to the original matrix and original vector
void constructGraph(vector<vector<int> >& jump,
                    int* node, int* isNode, int c, int p, int i)
{
    // enter the node in node array
    // it stores all the nodes in the graph
    node[i] = c;
 
    // to confirm that no child node have 2 parents
    if (isNode == 0) {
        isNode = 1;
        // make parent of x as y
        jump[0] = p;
    }
    return;
}
 
// function to jump to Lth parent of any node
void jumpPointer(vector<vector<int> >& jump,
                 int* isNode, int x, int L)
{
    int j = 0, n = x, k = L;
 
    // to check if node is present in graph or not
    if (isNode[x] == 0) {
        cout << "Node is not present in graph " << endl;
        return;
    }
 
    // in this loop we decrease the value of L by L/2 and
    // increment j by 1 after each iteration, and check for set bit
    // if we get set bit then we update x with jth parent of x
    // as L becomes less than or equal to zero means
    // we have jumped to Lth parent of node x
    while (L > 0) {
        // to check if last bit is 1 or not
        if (L & 1)
            x = jump[x][j];
 
        // use of shift operator to make
        // L = L/2 after every iteration
        L = L >> 1;
        j++;
    }
 
    cout << k << "th parent of node " << n
                   << " is = " << x << endl;
 
    return;
}
 
// Driver code
int main()
{
    // n represent number of nodes
    int n = 11;
 
    // initialization of parent matrix
    // suppose max range of a node is up to 1000
    // if there are 1000 nodes than also
    // length of jump matrix will not exceed 10
    vector<vector<int> > jump(1000, vector<int>(10));
 
    // node array is used to store all nodes
    int* node = new int[1000];
 
    // isNode is an array to check whether
    // a node is present in graph or not
    int* isNode = new int[1000];
 
    // memset function to initialize isNode array with 0
    memset(isNode, 0, 1000 * sizeof(int));
 
    // function to calculate len
    // len -> it is the maximum length of
    // array to hold parent of each node.
    int len = getLen(n);
 
    // R stores root node
    R = 2;
 
    // construction of graph
    // here 0 represent that the node is root node
    constructGraph(jump, node, isNode, 2, 0, 0);
    constructGraph(jump, node, isNode, 5, 2, 1);
    constructGraph(jump, node, isNode, 3, 5, 2);
    constructGraph(jump, node, isNode, 4, 5, 3);
    constructGraph(jump, node, isNode, 1, 5, 4);
    constructGraph(jump, node, isNode, 7, 1, 5);
    constructGraph(jump, node, isNode, 9, 1, 6);
    constructGraph(jump, node, isNode, 10, 9, 7);
    constructGraph(jump, node, isNode, 11, 10, 8);
    constructGraph(jump, node, isNode, 6, 10, 9);
    constructGraph(jump, node, isNode, 8, 10, 10);
 
    // function to pre compute jump matrix
    set_jump_pointer(jump, node, len, n);
 
    // query to jump to parent using jump pointers
    // query to jump to 1st parent of node 2
    jumpPointer(jump, isNode, 2, 0);
 
    // query to jump to 2nd parent of node 4
    jumpPointer(jump, isNode, 4, 2);
 
    // query to jump to 3rd parent of node 8
    jumpPointer(jump, isNode, 8, 3);
 
    // query to jump to 5th parent of node 20
    jumpPointer(jump, isNode, 20, 5);
 
    return 0;
}

Python3

# Python3 program to implement
# Jump pointer algorithm
import math
 
# Initialization of parent matrix
# suppose max range of a node is
# up to 1000 if there are 1000 nodes
#  than also length of jump matrix
# will not exceed 10
jump = [[0 for j in range(10)]
           for i in range(1000)]
  
# Node array is used to store all nodes
node = [0 for i in range(1000)]
  
# isNode is an array to check whether
# a node is present in graph or not
isNode = [0 for i in range(1000)]
 
# n -> it represent total number of nodes
# len -> it is the maximum length of array
# to hold parent of each node.
# In worst case, the highest value of
# parent a node can have is n-1.
# 2 ^ len <= n-1
# len = O(log2n)
def getLen(n):
 
    len = int((math.log(n)) //
              (math.log(2))) + 1
    return len
 
# jump represent 2D matrix to hold parent
# of node in jump matrix here we pass
# reference of 2D matrix so that the
# change made occur directly to the
# original matrix len is same as
# defined above n is total nodes
# in graph
def set_jump_pointer(len, n):
     
    global jump, node
    for j in range(1,len + 1):
        for i in range(0, n):
            jump[node[i]][j] = jump[jump[node[i]][j - 1]][j - 1]
 
# c -> it represent child
# p -> it represent parent
# i -> it represent node number
# p=0 means the node is root node
# here also we pass reference of
# 2D matrix and depth vector so
# that the change made occur
# directly to the original matrix
# and original vector
def constructGraph(c, p, i):
     
    global jump, node, isNode
     
    # Enter the node in node array
    # it stores all the nodes in the graph
    node[i] = c
  
    # To confirm that no child node
    # have 2 parents
    if (isNode == 0):
        isNode = 1
         
        # Make parent of x as y
        jump[0] = p
     
    return
 
# function to jump to Lth parent
# of any node
def jumpPointer(x, L):
     
    j = 0
    n = x
    k = L
     
    global jump, isNode
     
    # To check if node is present in
    # graph or not
    if (isNode[x] == 0):
        print("Node is not present in graph ")
        return
         
    # In this loop we decrease the value
    # of L by L/2 and increment j by 1
    # after each iteration, and check
    # for set bit if we get set bit
    # then we update x with jth parent
    # of x as L becomes less than or
    # equal to zero means we have
    # jumped to Lth parent of node x
    while (L > 0):
         
        # To check if last bit is 1 or not
        if ((L & 1)!=0):
            x = jump[x][j]
  
        # Use of shift operator to make
        # L = L/2 after every iteration
        L = L >> 1
        j += 1
         
    print(str(k) + "th parent of node " +
          str(n) + " is = " + str(x))  
  
    return
 
# Driver code
if __name__=="__main__":
     
    # n represent number of nodes
    n = 11
  
    # Function to calculate len
    # len -> it is the maximum length of
    # array to hold parent of each node.
    len = getLen(n)
  
    # R stores root node
    R = 2
  
    # Construction of graph
    # here 0 represent that
    # the node is root node
    constructGraph(2, 0, 0)
    constructGraph(5, 2, 1)
    constructGraph(3, 5, 2)
    constructGraph(4, 5, 3)
    constructGraph(1, 5, 4)
    constructGraph(7, 1, 5)
    constructGraph(9, 1, 6)
    constructGraph(10, 9, 7)
    constructGraph(11, 10, 8)
    constructGraph(6, 10, 9)
    constructGraph(8, 10, 10)
  
    # Function to pre compute jump matrix
    set_jump_pointer(len, n)
  
    # Query to jump to parent using jump pointers
    # query to jump to 1st parent of node 2
    jumpPointer(2, 0)
  
    # Query to jump to 2nd parent of node 4
    jumpPointer(4, 2)
  
    # Query to jump to 3rd parent of node 8
    jumpPointer(8, 3)
  
    # Query to jump to 5th parent of node 20
    jumpPointer(20, 5)
 
# This code is contributed by rutvik_56
Output: 
0th parent of node 2 is = 2
2th parent of node 4 is = 2
3th parent of node 8 is = 1
Node is not present in graph


 

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.