求无向图的直径

题目描述:

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

 

点赞

发表评论