數(shù)據(jù)結(jié)構(gòu)ebook數(shù)據(jù)結(jié)構(gòu)課后答案-數(shù)據(jù)結(jié)構(gòu) 課后題答案（第4章）

數(shù)據(jù)結(jié)構(gòu)部分課后習題答案

第四章

廣度優(yōu)先生成樹（黑體加粗邊）:

深度拓撲排序序列：v0-v2-v3-vl-v4

4.2

4.3、如圖所示為一個有6個頂點｛ul,u2,u3,u4,u5,u6｝的帶權(quán)有向圖的鄰接矩陣。

根據(jù)此鄰接矩陣畫出相應(yīng)的帶權(quán)有向圖，利用dijkstra算法求第一個頂點ul到其

余各頂點的最短路徑，并給出計算過程。

帶權(quán)有向圖：

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證明在圖中邊權(quán)為負時Dijkstra算法不能正確運行

若允許邊上帶有負權(quán)值，有可能出現(xiàn)當與S（已求得最短路徑的頂點集，歸

入S內(nèi)的結(jié)點的最短路徑不再變更）內(nèi)某點（記為a）以負邊相連的點（記為b）

確定其最短路徑時，它的最短路徑長度加上這條負邊的權(quán)值結(jié)果小于a原先確定

的最短路徑長度，而此時a在Dijkstra算法下是無法更新的。

4.5

P.198圖中的權(quán)值有負值不會影響prim和kruskal的正確性

如圖：

V1

Prim求解過程

1.2.

4.6Dijkstra算法如何應(yīng)用到無向圖？

答：Dijkstra算法通常是運用在帶非負權(quán)值的有向圖中，但是無向圖其實就是兩

點之間兩條有向邊權(quán)值相同的特殊的有向圖，這樣就能將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對應(yīng)分別為9,8,12,8,9,最長為12,總和為46

V4對應(yīng)分別為5,4,12,4,9,最長為12,總和為34

V5對應(yīng)分別為9,4,8,4,9,最長為9,總和為34

V6對應(yīng)分別為9,13,9,9,9,最長為13,總和為49

題目要求娛樂中心“距其它各結(jié)點的最長往返路程最短”，結(jié)點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