算法导论22.27

从任意起点开始&＃xff0c;运行一次BFS&＃xff0c;得到一个最远点d1&＃xff0c;d1即为直径的一点

再运行一次BFS&＃xff0c;得到一个最远点d2&＃xff0c;则d1~d2为树的直径

为什么这样是对的&＃xff1f;

&＃xff08;1&＃xff09;证明d1是树直径的一点

a) 若s在直径d1,d2上&＃xff0c;则最后一个点必能搜到d1或d2&＃xff1b;因为若搜到最后一个点为v&＃xff0c;则直径为vd2&＃xff0c;与题意不符

     b) 若s不在直径d1,d2上,BFS搜到的最远点为v&＃xff0c;d1-d2为直径,根据连通图的性质&＃xff0c;

            路径s-v当中必有一点t1&＃xff0c;与路径d1-d2相连

 .

根据d1-d2直径定义 d1d2&＃61;d2t2&＃43;t2d1,且t2d1>&＃61;t2t1&＃43;t1v,否则直径为d2-t2-t1-v

    根据v是BFS搜到的最远点&＃xff0c;t1v>&＃61;t1t2&＃43;t2d1,最远点为d1

    根据两个不等式可得

    t1t2&＃61;0

t1v&＃61;t2d1

&＃xff08;2&＃xff09;通过d1进行BFS&＃xff0c;最后搜到的点必为d2

因为若搜到最后一个点为v&＃xff0c;则直径为vd1&＃xff0c;与题意不符

转自&＃xff1a;http://www.cnblogs.com/inpeace7/archive/2012/04/18/2454996.html