版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领
文档简介
数据结构部分课后习题答案
第四章
广度优先生成树（黑体加粗边）:
深度拓扑排序序列：v0-v2-v3-vl-v4
4.2
4.3、如图所示为一个有6个顶点｛ul,u2,u3,u4,u5,u6｝的带权有向图的邻接矩阵。
根据此邻接矩阵画出相应的带权有向图，利用dijkstra算法求第一个顶点ul到其
余各顶点的最短路径，并给出计算过程。
带权有向图：
U1到其他点的最短路径:
{U4}{U2,U4}{U2,U4,U5}{U2,U4,U5,U6}
U277
U3OOOOOO3827
U42
U5OO1413
U660171717
最短路径U1,U4U1,U2U1,U2,U5U1,U4,U6U1,U4,U6,U3
新顶点U4U2U5U6U3
路径长度27131727
4.4证明在图中边权为负时Dijkstra算法不能正确运行
若允许边上带有负权值，有可能出现当与S（已求得最短路径的顶点集，归
入S内的结点的最短路径不再变更）内某点（记为a）以负边相连的点（记为b）
确定其最短路径时，它的最短路径长度加上这条负边的权值结果小于a原先确定
的最短路径长度，而此时a在Dijkstra算法下是无法更新的。
4.5
P.198图中的权值有负值不会影响prim和kruskal的正确性
如图：
V1
Prim求解过程
1.2.
4.6Dijkstra算法如何应用到无向图？
答：Dijkstra算法通常是运用在带非负权值的有向图中，但是无向图其实就是两
点之间两条有向边权值相同的特殊的有向图，这样就能将Dijkstra算法运用到无
向图中。
4.7
用FLOYD算法求出任意两顶点的最短路径(如图A(6)所示)。
025453025453025451
303236303236303236
460847450747450747
136014125014125014
414303414303414303
682560A(5)=672560A(6)=672560
VI至UV2、73、V4、V5、V6往返路径长度分别为5,9,5,9,9,最长为9,
总的往返路程为37
同理V2到VI、V3、V4、V5、V6分别为5,8,4,4,13,最长为13,总和34
V3对应分别为9,8,12,8,9,最长为12,总和为46
V4对应分别为5,4,12,4,9,最长为12,总和为34
V5对应分别为9,4,8,4,9,最长为9,总和为34
V6对应分别为9,13,9,9,9,最长为13,总和为49
题目要求娱乐中心“距其它各结点的最长往返路程最短”，结点VI,V5最长往
返路径最短都是9。按“相同条件下总的往返路径越短越好”，选顶点V5,总的
往返路径是34<>
4.8
iabcdefghw
最早016342413392252
最晚02924373113392252
iabcdefghw
i-ala2a3a4
aa5
ba6a7
ca8a9
dalO
eall
fal2al3al4
gal5
hal6al7
w
aaaaaaaaaalalalalalalalal
12345678901234567
最0000166334
温馨提示
- 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- java基础面试题及答案120问
- java面试题及答案问题实际工作中
- 现代汉语考试知识闭环试题及答案
- 环境政策与法律措施的效果分析试题及答案
- Delphi编程语言的优势与挑战试题及答案
- 2025年Delphi开发者常见问题试题及答案
- 流行趋势的计算机二级Delphi试题及答案
- 编程语言的演化与应用场景分析试题及答案
- 财务成本管理的关键绩效指标试题及答案
- 赠送广告合同协议书
- 阵发性室上性心动过速临床路径
- JGT475-2015 建筑幕墙用硅酮结构密封胶
- 工序交接记录表
- IT项目周报模板
- 机械工业出版社2020《人工智能导论》课程同步PPT课件第4章 搜索算法
- 说专业-物流管理专业
- 图纸会审记录SG-007
- 院外药品使用告知书
- 钢结构门头施工方案
- 住房城乡建设领域重大安全风险隐患清单
- (完整版)土的参数换算(计算饱和重度)
评论
0/150
提交评论