问答题
自由树(即无环连通图)T=(K,E)的直径是树中所有点对间最短路径长度的最大值,即T的直径定义为MAX D(u,v),这里D(u,v)表示顶点u到顶点v的最短路径长度(路径长度为路径中所包含的边数)。试写一算法求T的直径,并分析算法的时间复杂度。(时间复杂度越小得分越高。)【中科院计算所1999五、3(20分)】
【正确答案】
正确答案:对于无环连通图,顶点间均有路径,树的直径是生成树上距根结点最远的两个叶子间的距离,利用深度优先遍历可求出图的直径。
【答案解析】
提交答案
关闭