【正确答案】利用深度优先遍历求出一个根结点v到每个叶子结点的距离，这是由diameter(v)函数实现的。该函数的时间复杂度为O(n+e)，n为顶点个数，e为边数。然后，以每个顶点作为根结点调用diameter()函数，其中最大值即为T的直径，本算法的时间复杂度为O(n(n+e))。 实现本题功能的程序代码如下： void dfs(int parent,int child,int &len) //函数执行结束后，len中存放从根结点到child结点所在子树的叶子结点的最大距离 //cost是带权邻接矩阵，visited是已经初始化的访问标记数组 //N是已定义的常量，即顶点个数 { int clen,v=0,maxlen; clen=len; maxlen=len; while(v＜N && cost[child][v]==0) //找与child相邻的第一个顶点v v++; while(v＜N) //存在邻接顶点时循环 { if(v!=parent) { len=len+cost[child][v]; dfs(child,v,len); if(len＞maxlen) maxlen=len; } v++; while(v＜N && cost[child][v]==0) //找与child相邻的下一个顶点v v++; len=clen; } len=maxlen; } int diameter(int v) { int maxlen1=0; //存放到目前为止所找到的根v到叶子结点的最大值 int maxlen2=0; //存放到目前为止所找到的根v到叶子结点的次大值 int len=0; //记录深度优先遍历中到某个叶子结点的距离 int w=0; //存放v的邻接顶点 while(w＜N && cost [v][w]==0) //找与v相邻的第一个顶点w w++; while(w＜N) //存在邻接顶点时循环 { len=cost[v][w]; dfs(v,w,len); if(len＞maxlen1) { maxlen2=maxlen1; maxlen1=len; } else if(len＞maxlen2) maxlen2=len; w++; while(w＜N && cost [v][w]==0) //找与v相邻的第一个顶点w w++; } return maxlen1+maxlen2; } for(i=1;i＜N;i++) //找出从所有顶点出发直径的最大值 { d=diameter(i); if(diam＜d) diam=d; }

【答案解析】[说明] 本题提到最短路径，拿到题目后，考生容易将其归类为最短路径问题，而去想相应的算法。但由于本题限定图为自由树，所以只需用深度优先搜索的方法即可得到每两点的最短路径。这种在题目中设置干扰因素的情况在正式考题中是常见的，因此考生必须注意区分，以提高做题效率。