自由树(即无环连通图)T=(V，E)的直径是树中所有点对间最短路径长度的最大值，即T的直径定义为MAX d(u，v)，这里d(u，v)表示顶点u到顶点v的最短路径长度(路径长度为路径中所含的边数)。试写一算法求T的直径，并分析算法的时间复杂度(时间复杂度越小得分越高)。
参考答案：求树的直径的时间复杂度可为O(n)，O(n2)和O(n3)。
解法一：先调用求所有点对见最短路径算法(每边权数为1)如FLOYD算法，然后对指代矩阵求最大的COST[i，j]作为直径。
解法二：修改Bfs算法，使之遍历时，记录当前访问结点的深度(离根的边数)，用存在度为1的结点作起点调用Bfs，求出其他非根结点的深度，在各次调用Bps算法中求最大深度，即为树的直径。时间O(n(n+e))=O(n2+ne)，这里O(ne)是一次外部调用Bfs的运行时间，最多调用Bfs次数(指外部调用)不超过O(n)(存储结构为邻接表时)。
解法三：用邻接表作为存储结构。依次删去树叶(度为1的结点)，将与树叶相连的结点度数减1。设在第一轮删去原树T的所有树叶后，所得树为T1；再依次做第二轮删除，即删除所有T1的叶子；如此反复，若最后剩下一个结点，则树直径应为删除的轮数×2，具体算法如下：
int SZJ()
{
m=0：
for(i=；i≤n；i++)
if(du(veil)-1){
enqueue(Q，v[i])；∥叶子vi入队
m=m+l；∥m记录当前一轮叶子数
r=0；∥表示删除叶子轮数
while(m＞=2){∥当前叶子轮数
j=0；∥j计算新一轮叶子数目
for(i=1；ic=m；i++){
dequeue(Q，v)；∥出队，表示删去叶子v将与v相邻的结点w的度数减1
if(du(w)==1){∥w是新一轮的叶子
j=j+1；
enqueue(Q，w)；∥w入队
r=r+1；∥轮数加1
m=j；∥新一轮叶子总数
}
if(m==0)return 2*r-1∥m=0，直径为轮数*2-1
else return 2*r；∥m=l，直径为轮数*2
}