Given A Tree. How to find distance between every pair of nodes in tree without using 2D matrix of size n*n. I know solution of O(n^2) complexity .
问问题
7371 次
2 回答
11
If you want to be able to answer queries of form distance(u, v) fast enough with fast preprocessing, you may use LCA. LCA, or lowest common ancestor, of two vertices in a rooted tree is a vertex which is an ancestor of both of them and which is the lowest among all of theirs common ancestors. There is a not very complex algorithm to find LCA(u, v) in logarithmic time with n log n preprocessing time. I can describe it if it is needed.
So, your problem may be solved as following. First, fix a root of your tree. Then make an above mentioned preprocessing to be able to find LCA. Then, supposing h[v] is a distance from v to the root (can be precomputed in linear time for all vertices) then distance(u, v) = h[u] + h[v] - 2 * h[LCA(u, v)].
于 2013-08-19T14:43:22.593 回答
2
As I already mentioned in comment, assuming that the output should be (v1,v2,distance) for every pair of vertices v1,v2 in your tree - note that there are n*(n-1) pairs of such vertices. Since n*(n-1) is in O(n^2) - and it is the size of the output, it cannot be done better then O(n^2), so your algorithm is optimal, in terms of big O notation.
于 2013-08-06T13:43:12.813 回答