Алгоритм указателя перехода
Алгоритм указателя перехода - это метод разработки параллельных алгоритмов, которые работают со структурами указателей, такими как массивы или связанный список. Этот алгоритм обычно используется для определения корня леса корневого дерева.
В алгоритме указателя перехода мы предварительно обрабатываем дерево, чтобы можно было ответить на запросы, чтобы найти любого родителя любого узла в дереве с временной сложностью 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
Алгоритм :
Вот алгоритм для реализации алгоритма указателя перехода для поиска любого родителя любого узла в графе. Мы определяем матрицу перехода с помощью динамического программирования . Здесь мы обозначаем корневой узел как 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 |
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.