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