沧元图 第四部分 图[10]

第四部分 图[10]  

   试题　　　　【 年真题】　　　　 下列关于无向连通图特性的叙述中 正确的是　　I 所有顶点的度之和为偶数　　II 边数大于顶点个数减 　　III 至少有一个顶点的度为 　　　　A 只有I   B 只有II   C I和II   D I和III　　　　答案A　　　　 （ 分）带权图（权值非负 表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径 假定从初始顶点到目标顶点之间存在路径 现有一种解决该问题的方法 　　①设最短路径初始时仅包含初始顶点 令当前顶点u为初始顶点 　　②选择离u最近且尚未在最短路径中的一个顶点v 加入到最短路径中 修改当前顶点u=v 　　③重复步骤② 直到u是目标顶点时为止 　　清问上述方法能否求得最短路径？若该方法可行 请证明之 否则 请举例说明 　　　　参考答案　　该方法求得的路径不一定是最短路径 例如 对于下图所示的带权图 如果按照题中的原则 从A到C的最短路径为A→B→C 事实上其最短路径为A→D→C

    返回《数据结构》考研复习精编