Difference between pages "7.23" and "7.25"

From The Algorithm Design Manual Solution Wiki
(Difference between pages)
Jump to navigation Jump to search
(Created page with " for any node in the tree, there are two possibilities # either the diameter is contained in one of the subtrees # or the node itself is at the top of the longest path in the...")
 
(Created page with "Use the BFS starting from the vertex v. For every node keep track of the level from the vertex v. When w is encountered for the first time the level of w is the length of the...")
 
Line 1: Line 1:
 
+
Use the BFS starting from the vertex v. For every node keep track of the level from the vertex v. When w is encountered for the first time the level of w is the length of the shortest path. Count how many times you discover w on that level. Stop expanding nodes when you go past the length of the shortest path.
for any node in the tree, there are two possibilities
 
# either the diameter is contained in one of the subtrees
 
# or the node itself is at the top of the longest path in the tree that defines the diameter
 
 
 
in the second case, the diameter is equal to the sum of depth of the two deepest sub-trees of that node
 
 
 
the following algorithm calculates the diameter in <math>O(n)</math> time
 
 
 
<source lang="python">
 
 
 
class Node:
 
 
 
    def __init__(self, value, children):
 
        self.value = value
 
        self.children = children
 
 
 
    @classmethod
 
    def preorder(cls, lists):
 
        return cls(
 
                lists[0],
 
                [cls.preorder(l) for l in lists[1:]]
 
            )
 
 
 
 
def dd(root):
 
    """
 
    returns depth, diameter for tree with given root node
 
 
 
    >>> dd(Node.preorder([0, [1], [2]]))
 
    (1, 2)
 
    >>> dd(Node.preorder([1, [2, [3]], [4, [5]]]))
 
    (2, 4)
 
    >>> dd(Node.preorder([1, [2, [3, [4]], [5, [6, [7], [8]]]], [9]]))
 
    (4, 5)
 
    """
 
    d1 = d2 = -1
 
    md = 0
 
    for child in root.children:
 
        depth, diameter = dd(child)
 
        if diameter > md:
 
            md = diameter
 
        if depth >= d1:
 
            d2 = d1
 
            d1 = depth
 
        elif depth > d2:
 
            d2 = depth
 
    return d1 + 1, max(md, d1 + d2 + 2)
 
 
 
 
 
if __name__ == "__main__":
 
    import doctest
 
    doctest.testmod()
 
 
 
</source>
 
 
 
  
 
Back to [[Chapter 7]]
 
Back to [[Chapter 7]]

Latest revision as of 01:09, 21 September 2020

Use the BFS starting from the vertex v. For every node keep track of the level from the vertex v. When w is encountered for the first time the level of w is the length of the shortest path. Count how many times you discover w on that level. Stop expanding nodes when you go past the length of the shortest path.

Back to Chapter 7