【正文】 樹枝，不在生成樹中的邊稱為弦。 ),( 1EVK ?一個圖 G 有生成樹的充要條件是 G 是連通圖。 v1 v2 v3 v4 v5 v1 v2 v3 v4 v5 ),( 1EVK ?用避圈法求出下圖的一個生成樹。 v1 v2 v3 v4 v5 e1 e2 e3 e4 e5 e6 e7 e8 v1 v2 v3 v4 v5 e2 e4 e6 e8 v1 v2 v3 v4 v5 e1 e2 e3 e4 e5 e6 e7 e8 （一） 破圈法 （二） 避圈法 在圖中任取一條邊 e1， 找一條與 e1不構成圈的邊 e2，再找一條與 {e1， e2}不構成圈的邊 e3。 一般設已有 {e1，e2， … ， ek}， 找一條與 {e1， e2， … ， ek}中任何一些邊不構成圈的邊 ek+1， 重復這個過程，直到不能進行為止。 v1 v2 v3 v4 v5 v6 v1 v3 v1 v3 v2 v1 v3 v2 v5 v6 v1 v3 v2 v5 v6 v4 v1 v3 v2 v5 最小生成樹問題 如果圖 是圖 G的一個生成樹 ， 那么稱 E1上所有邊的權的和為生成樹 T 的權 ， 記作 S(T)。 如果圖 G的生成樹 T* 的權 S(T*)， 在 G 的所有生成樹 T 中的權最小 ， 即 那么稱 T*是 G 的最小生成樹 。 ),( 1EVT ? )(min)( * TSTS T? 某六個城市之間的道路網如圖 所示，要求沿著已知長度的道路聯(lián)結六個城市的電話線網，使電話線的總長度最短。 v1 v2 v3 v4 v5 v6 6 5 1 5 7 2 3 4 4 5 v1 v2 v3 v4 v5 v6 1 2 3 4 4 v1 v2 v3 v4 v5 1 4 2 3 1 3 5 2 最短路的一般提法為：設 為連通圖，圖中各邊 有權 （ 表示 之間沒有邊）， 為圖中任意兩點，求一條路 ，使它為從 到 的所有路中總權最短。即： 最小。 ),( EVG ?jil ???jil ts vv ,? sv ),( jiv jiv ,tv ? ?? ?? ),()(ji vvjilL(一 )、 狄克斯屈拉 (Dijkstra)算法 適用于 wij≥0， 給出了從 vs到任意一個點 vj的最短路 。 三 、最短路問題 算法步驟： vs以 P標號 ，這表示從 vs到 vs的最短距離為 0，其余節(jié)點均給 T標號， 。 vi 為剛得到 P標號的點，考慮點 vj， 其中 ，且 vj為 T標號。對 vj的 T標號進行如下修改： T標號的節(jié)點，把最小者改為 P標號，即： 當存在兩個以上最小者時，可同時改為 P標號。若全部節(jié)點均為 P標號，則停止，否則用 vk代替 vi， 返回步驟（ 2）。 0)( ?svP ),3,2()( nivP i ?????Evv ji ?),( ])(,)(min [)( jiijj lvPvTv ?? )](min[)(ik vTvP ?例一、 用 Dijkstra算法求下圖從 v1到 v6的最短路。 v1 v2 v3 v4 v6 v5 3 5 2 2 4 2 4 2 1 解 （ 1） 首先給 v1以 P標號 ， 給其余所有點 T標號 。 0)( 1 ?v)6,3,2()( ????? ivT i（ 2） （ 3） 3]30,min[])(,)(min[)( 12122 ??????? lvPvTvT 5]50,min[])(,)(min[) 13133 ??????? lvPvT3)( 2 ?vP（ 4） 4]13,5min[])(,)(min[)( 23233 ????? lvPvTvT 5]23,min[])(,)(min[)( 24244 ??????? lvPvTv 5]23,min[])(,)(min[) 25255 ??????? lvPvTTv1 v2 v3 v4 v6 v5 3 5 2 2 4 2 4 2 1 4)( 3 ?vP（ 5） （ 6） 8]44,6min[])(,)(min[)( 35355 ????? lvPvTvT 5)( 4 ?vP 5)( 5 ?vP 9]45,min[])(,)(min[)( 46466 ??????? lvPvTvT 7]25,min[])(,)()(56566 ?????l7)( 6 ?vP（ 7） （ 8） （ 9） （ 10） 反向追蹤得 v1到 v6的最短路為： 6521 vvvv ???2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 求從 1到 8的最短路徑 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X={1}, w1=0 min {c12,c14,c16}=min {0+2,0+1,0+3}=min {2,1,3}=1 X={1,4}, p4=1 p4=1 p1=0 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X={1,4} min {c12,c16,c42,c47}=min {0+2,0+3,1+10,1+2}=min {2,3,11,3}=2 X={1,2,4}, p2=2 p1=0 p4=1 p2=2 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X={1,2,4} min {c13,c23,c25,c47}=min {0+3,2+6,2+5,1+2}=min {3,8,7,3}=3 X={1,2,4,6}, p6=3 p2=2 p4=1 p1=0 p6=3 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X={1,2,4,6} min {c23,c25,c47,c67}=min {2+6,2+5,1+2,3+4}=min {8,7,3,7}=3 X={1,2,4,6,7}, p7=3 p2=2 p4=1 p1=0 p6=3 p7=3 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X={1,2,4,6,7} min {c23,c25,c75,c78}=min {2+6,2+5,3+3,3+8}=min {8,7,6,11}=6 X={1,2,4,5,6,7}, p5=6 p2=2 p4=1 p1=0 p6=3 p7=3 p5=6 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X={1,2,4,6,7} min {c23,c53,c58,c78}=min {2+6,6+9,6+4,3+8}=min {8,15,10,11}=8 X={1,2,3,4,5,6,7}, p3=8 p2=2 p4=1 p1=0 p6=3 p7=3 p5=6 p3=8 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X={1,2,3,4,6,7} min {c38,c58,c78}=min {8+6,6+4,3+7}=min {14,10,11}=10 X={1,2,3,4,5,6,7,8}, p8=10 p2=2 p4=1 p1=0 p6=3 p7=3 p5=6 p3=8 p8=10 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X={1,2,3,4,6,7,8} 1到 8的最短路徑為 {1， 4， 7， 5， 8}，長度為 10。 p2=2 p4=1 p1=0 p6=3 p7=3 p5=6 p3=8 p8=10 求從 V1 到 V8 的最短路線 。 3 V 1 V 2 V V 4 V 5 V V 6 7 V 8 3 7 2 1 2 3 3 4 1 2 2 6 V1 V2