首页 > 代码库 > 树的直径
树的直径
*总结的别人博客
树的直径(Diameter)是指树上的最长简单路。
直径的求法：两遍BFS (or DFS)
任选一点u为起点，对树进行BFS遍历，找出离u最远的点v
以v为起点，再进行BFS遍历，找出离v最远的点w。则v到w的路径长度即为树的直径
*简单证明
于是原问题可以在O(E)时间内求出
关键在于证明第一次遍历的正确性，也就是对于任意点u，距离它最远的点v一定是最长路的一端。
如果u在最长路上，那么v一定是最长路的一端。可以用反证法：假设v不是最长路的一端，则存在另一点v’使得(u→v’)是最长路的一部分，于是len(u→v’) > len(u→v)。但这与条件“v是距u最远的点”矛盾。
如果u不在最长路上，则u到其距最远点v的路与最长路一定有一交点c，且(c→v)与最长路的后半段重合(why?)，即v一定是最长路的一端
BFS
DFS
一张无向图中，给定图中一点，以最短路径长度当作距离，找出改点最远的一点，这两点之间的距离就叫做偏心距。
要计算一张无向图的半径，只要先算好两点之间最短路径，然后按定义来算即可。
先用floyd 再搜索最长的路径（即为直径）。
1 int d[10][10]; // adjacency matrix 2 int ecc[10]; // 各點的偏心距 3 4 void diameter_radius() 5 { 6 // Floyd-Warshall Algorithm 7 for (int k=0; k<10; ++k) 8 for (int i=0; i<10; ++i) 9 for (int j=0; j<10; ++j)10 d[i][j] = min(d[i][j], d[i][k] + d[k][j]);11 12 // 計算偏心距13 memset(ecc, 0x7f, sizeof(ecc));14 for (int i=0; i<10; ++i)15 for (int j=0; j<10; ++j)16 ecc[i] = min(ecc[i], d[i][j]);17 18 // 計算直徑和半徑19 int diameter = 0;20 int radius = 1e9;21 for (int i=0; i<10; ++i)22 {23 diameter = max(diameter, ecc[i]);24 radius = min(radius , ecc[i]);25 }26 27 /*28 // 直徑也可以這樣算29 for (int i=0; i<10; ++i)30 for (int j=0; j<10; ++j)31 diameter = max(diameter, d[i][j]);32 */33 }
一棵樹的各種直徑一定會相交在同一點（同一群點）。
1.反證法。現在有兩條分開的直徑，可是一棵樹上各點都得連通，所以這兩條分開的直徑，中間一定有某處互相連接，一旦連接起來，勢必變成更長的直徑，矛盾。故所有直徑必相交。2.反證法。現在已有兩條直徑相交在某一點，如果另外一條直徑與這兩條直徑相交在另一點，勢必變成更長的直徑，矛盾。故所有直徑必相交在同一點（同一群點）。
树的直径
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。