题目描述:
自由树(即无环连通图)T=(V, E)的直径是树中所有顶点之间最短路径的最大值,试设计一个算法求T的直径,并分析算法的时间复杂度。
【分级提示】
(1)可用邻接表作为存储结构;
(2)引入一个辅助数组保存各顶点的度;
(3)执行删除过程;
(4)并修正各个顶点的度。
(15.0分)
下面是对算法的ADL语言描述:
算法Diameter(Head,n.length) /求无向连通无环图的直径/ D1 [寻找距离V0最远的叶子结点V1] FOR i <- 1 TO n DO vis[i] <- 0 CREATQ(q).q <= (1,0). WHILE(NOT Empty(q)) DO ( (v,d) <= q. p <- adjacent(Head[v]). WHILE(p<>NULL) DO IF(vis[VerAdj(p)]=0) THEN q<= (VerAdj(p),d+1). ) D2 [寻找距离V1最远的叶子结点V2] FOR j<- 1 TO n DO (vis[i] <- 0. f[i]<- 0.). CREATQ(q).q <= (v,0).f[i] <- v. WHILE(NOT QEmpty(q)) DO ( (u,d) <= q. p <- adjacent(Head[v]). WHILE(p<>NULL) DO IF(vis[VerAdj(p)]=0) THEN (q <= (VerAdj(p),d+1).f[VerAdj(p)] <- u.) ) D3 [输出V2到V1的最长路径] j <- u. WHILE(f[j]<>j) DO (PRINT(j).j <- f(j)). length <- j. RETURN. ▌