| 词条 | Tarjan's off-line lowest common ancestors algorithm |
| 释义 |
In computer science, Tarjan's off-line lowest common ancestors algorithm is an algorithm for computing lowest common ancestors for pairs of nodes in a tree, based on the union-find data structure. The lowest common ancestor of two nodes d and e in a rooted tree T is the node g that is an ancestor of both d and e and that has the greatest depth in T. It is named after Robert Tarjan, who discovered the technique in 1979. Tarjan's algorithm is an offline algorithm; that is, unlike other lowest common ancestor algorithms, it requires that all pairs of nodes for which the lowest common ancestor is desired must be specified in advance. The simplest version of the algorithm uses the union-find data structure, which unlike other lowest common ancestor data structures can take more than constant time per operation when the number of pairs of nodes is similar in magnitude to the number of nodes. A later refinement by {{harvtxt|Gabow|Tarjan|1983}} speeds the algorithm up to linear time. PseudocodeThe pseudocode below determines the lowest common ancestor of each pair in P, given the root r of a tree in which the children of node n are in the set n.children. For this offline algorithm, the set P must be specified in advance. It uses the MakeSet, Find, and Union functions of a disjoint-set forest. MakeSet(u) removes u to a singleton set, Find(u) returns the standard representative of the set containing u, and Union(u,v) merges the set containing u with the set containing v. TarjanOLCA(r) is first called on the root r. '''function''' TarjanOLCA(u) MakeSet(u); u.ancestor := u; '''for each''' v '''in''' u.children '''do''' TarjanOLCA(v); Union(u,v); Find(u).ancestor := u; u.color := black; '''for each''' v '''such that''' {u,v} '''in''' P '''do''' '''if''' v.color == black print "Tarjan's Lowest Common Ancestor of " + u + " and " + v + " is " + Find(v).ancestor + ".";Each node is initially white, and is colored black after it and all its children have been visited. The lowest common ancestor of the pair {u,v} is available as Find(v).ancestor immediately (and only immediately) after u is colored black, provided v is already black. Otherwise, it will be available later as Find(u).ancestor, immediately after v is colored black. For reference, here are optimized versions of MakeSet, Find, and Union for a disjoint-set forest: '''function''' MakeSet(x) x.parent := x x.rank := 1 '''function''' Union(x, y) xRoot := Find(x) yRoot := Find(y) '''if''' xRoot.rank > yRoot.rank yRoot.parent := xRoot '''else if''' xRoot.rank < yRoot.rank xRoot.parent := yRoot '''else if''' xRoot.rank == yRoot.rank yRoot.parent := xRoot xRoot.rank := xRoot.rank + 1 '''function''' Find(x) '''if''' x.parent != x x.parent := Find(x.parent) '''return''' x.parent References
| last1 = Gabow | first1 = H. N. | last2 = Tarjan | first2 = R. E. | authorlink2 = Robert Tarjan | contribution = A linear-time algorithm for a special case of disjoint set union | title = Proceedings of the 15th ACM Symposium on Theory of Computing (STOC) | year = 1983 | pages = 246–251 | doi = 10.1145/800061.808753}}.
| last = Tarjan | authorlink = Robert Tarjan | title = Applications of path compression on balanced trees | journal = Journal of the ACM | volume = 26 | issue = 4 | year = 1979 | pages = 690–715 | doi = 10.1145/322154.322161|first =R. E.}}. 2 : Graph algorithms|Articles with example pseudocode |
| 随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。