数据结构课后题答案(第4章).

数据结构部分课后习题答案第四章 4.1

广度优先生成树(黑体加粗边:

深度拓扑排序序列:v0-v2-v3-v1-v4 4.2 广度 深度 (1

(2

加边顺序 a-b b-e e-d d-f f-c

4.3、 如图所示为一个有6个顶点{u1,u2,u3,u4,u5,u6}的带权有向图的邻接矩阵。 根据此邻接矩阵画出相应的带权有向图,利用dijkstra 算法求第一个顶点u1到其余各顶点的最短路径,并给出计算过程。

带权有向图:

4.4证明在图中边权为负时Dijkstra算法不能正确运行

若允许边上带有负权值,有可能出现当与S(已求得最短路径的顶点集,归入S内的结点的最短路径不再变更内某点(记为a以负边相连的点(记为b确定其最短路径时,它的最短路径长度加上这条负边的权值结果小于a原先确定的最短路径长度,而此时a在Dijkstra算法下是无法更新的。

4.5

P.198 图中的权值有负值不会影响prim和kruskal的正确性 如图:

KRUSKAL求解过程: