树的重心与直径.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,树的重心,树的重心定义为删掉这个节点之后将树分成几部分使得这几部分中点个数的最大值最小。.,算法分析：,建立边表data。由于是无向的，因此边表长度为(N-1)*2。边表按照p1端点递增的顺序排序，以便计算每一个顶点的边表序号,树的基本操作:以结点1为根，计算出每个结点所在的子树的结点数。,枚举每一个结点，若将其删掉，那么考虑剩余的所有连通分量。,1、它的子树，其结点数可以直接调用。,2、它的上方子树，其结点数可通过n-1-减去所有子树的结点数算出。,这样，在其中选择d(i)最小的即可。时间复杂度：O(N)，空间复杂度：O(N),void dfs(int i),int j,k;,j=lasti;,sizei=1;,while(j!=0),k=otherj;,if(k!=fatheri),fatherk=i;,dfs(k);,sizei+=sizek;,if(ansiansi)ansi=n-sizei;,return;,树的直径,树的直径是指树的最长简单路。求法:两遍BFS:先任选一个起点BFS找到最长路的终点，再从终点进行BFS，则第二次BFS找到的最长路即为树的直径；,原理:设起点为u,第一次BFS找到的终点v一定是树的直径的一个端点,证明:1)如果u 是直径上的点，则v显然是直径的终点(因为如果v不是的话，则必定存在另一个点w使得u到w的距离更长，则于BFS找到了v矛盾),2)如果u不是直径上的点，则u到v必然于树的直径相交(反证),那么交点到v 必然就是直径的后半段了,所以v一定是直径的一个端点，所以从v进行BFS得到的一定是直径长度,