求无向图的直径

题目描述：

自由树（即无环连通图）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. ▌​