数据结构考研分类复习真题 第七章 图[63]

．设计算法求出无向连通图中距离顶点V的最短路径长度(最短路径长度以边数为单位计算)为K的所有的结点要求尽可能地节省时间【西北大学 七】

．自由树(即无环连通图)T=(VE)的直径是树中所有点对间最短路径长度的最大值即T的直径定义为MAX D(uv) 这里D(uv) (uv∈V)表示顶点u到顶点v的最短路径长度(路径长度为路径中所包含的边数)写一算法求T的直径并分析算法的时间复杂度(时间复杂度越小得分越高)【中科院 五 (分)】

．求图的中心点的算法设V是有向图G的一个顶点我们把V的偏心度定义为max{从w到v的最短距离|w是g中所有顶点}如果v是有向图G中具有最小偏心度的顶点则称顶点v是G的中心点【长沙铁道学院 五 (分)】

．设G是含有n顶点(设顶点编号为…n)的有向无环图将G用如下定义的邻接表存储

TYPE arcptr=↑arcnode;

arcnode=RECORD{邻接表中的结点}

adjvex:n; nextarc:arcptr; END;

vexnode=RECORD{邻接表的表头结点}

vexnum: n; firstarc:arcptr; mpl:integer END;

Hnodes=ARRAY[n] OF vexnode;

请编写一个非递归算法求G的每个顶点出发的最长路径的长度(每条弧的长度均为)并存入mpl域中 要求首先写出算法思想然后写算法过程【山东科技大学 六 (分)】

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []