lowest common ancestor Algorithm
In graph theory and computer science, the lowest common ancestor (LCA) of two nodes V and w in a tree or directed acyclic graph (DAG) However, there exist several algorithms for processing trees so that lowest common ancestors may be found more quickly. Their algorithm processes any tree in linear time, use a heavy path decomposition, so that subsequent lowest common ancestor query may be answered in constant time per query.
Omer Berkman and Uzi Vishkin (1993) observed a completely new manner to answer lowest common ancestor query, again achieve linear preprocessing time with constant query time. This is done by keeping the forest use the dynamic trees data structure with partitioning by size; this then keeps a heavy-light decomposition of each tree, and lets LCA query to be carry out in logarithmic time in the size of the tree.
# https://en.wikipedia.org/wiki/Lowest_common_ancestor
# https://en.wikipedia.org/wiki/Breadth-first_search
import queue
def swap(a, b):
a ^= b
b ^= a
a ^= b
return a, b
# creating sparse table which saves each nodes 2^i-th parent
def creatSparse(max_node, parent):
j = 1
while (1 << j) < max_node:
for i in range(1, max_node + 1):
parent[j][i] = parent[j - 1][parent[j - 1][i]]
j += 1
return parent
# returns lca of node u,v
def LCA(u, v, level, parent):
# u must be deeper in the tree than v
if level[u] < level[v]:
u, v = swap(u, v)
# making depth of u same as depth of v
for i in range(18, -1, -1):
if level[u] - (1 << i) >= level[v]:
u = parent[i][u]
# at the same depth if u==v that mean lca is found
if u == v:
return u
# moving both nodes upwards till lca in found
for i in range(18, -1, -1):
if parent[i][u] != 0 and parent[i][u] != parent[i][v]:
u, v = parent[i][u], parent[i][v]
# returning longest common ancestor of u,v
return parent[0][u]
# runs a breadth first search from root node of the tree
# sets every nodes direct parent
# parent of root node is set to 0
# calculates depth of each node from root node
def bfs(level, parent, max_node, graph, root=1):
level[root] = 0
q = queue.Queue(maxsize=max_node)
q.put(root)
while q.qsize() != 0:
u = q.get()
for v in graph[u]:
if level[v] == -1:
level[v] = level[u] + 1
q.put(v)
parent[0][v] = u
return level, parent
def main():
max_node = 13
# initializing with 0
parent = [[0 for _ in range(max_node + 10)] for _ in range(20)]
# initializing with -1 which means every node is unvisited
level = [-1 for _ in range(max_node + 10)]
graph = {
1: [2, 3, 4],
2: [5],
3: [6, 7],
4: [8],
5: [9, 10],
6: [11],
7: [],
8: [12, 13],
9: [],
10: [],
11: [],
12: [],
13: [],
}
level, parent = bfs(level, parent, max_node, graph, 1)
parent = creatSparse(max_node, parent)
print("LCA of node 1 and 3 is: ", LCA(1, 3, level, parent))
print("LCA of node 5 and 6 is: ", LCA(5, 6, level, parent))
print("LCA of node 7 and 11 is: ", LCA(7, 11, level, parent))
print("LCA of node 6 and 7 is: ", LCA(6, 7, level, parent))
print("LCA of node 4 and 12 is: ", LCA(4, 12, level, parent))
print("LCA of node 8 and 8 is: ", LCA(8, 8, level, parent))
if __name__ == "__main__":
main()
