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

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

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

　　 ．自由树(即无环连通图)T=(V E)的直径是树中所有点对间最短路径长度的最大值 即T的直径定义为MAX D(u v) 这里D(u v) (u v∈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域中 要求 首先写出算法思想 然后写算法过程 【山东科技大学 六 ( 分)】