17 Aug
2015
17 Aug
'15
4:30 p.m.
On 17.08.2015 17:23, Christopher Morris wrote:
Thanks, is it also possible to obtain the leaves of the resulting tree without traversing the whole tree?
The leaves are just the nodes that are visited last by the BFS/Dijkstra, i.e. the ones that are furthest away from the source. Are you sure this is what you want? In any case, the answer is no, you have to find them in the tree. Note however that the ordering of the nodes in this tree are the same as in the original graph. So if you want to traverse the successor/predecessor of any particular node v in the original graph, you can lookup t.vertex(v) in time O(1), where t is the predecessor tree. Best, Tiago -- Tiago de Paula Peixoto <tiago@skewed.de>