Difference between pages "7.23" and "7.25"
(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. | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
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