廣州南海東莞佛山中山清遠惠州第八章圖的應用

圖的最小生成樹最短路徑拓撲序列關鍵路徑8.1圖的生成樹和最小生成樹圖的生成樹定義：無向圖的所有頂點加上遍歷時所經過的邊，這樣構成的子圖稱為圖的生成樹。12340561256734從0號點出發(fā)，按深度遍歷得到的生成樹從0號點出發(fā)，按廣度遍歷得到的生成樹每個圖的生成樹可以構造許多棵。123405612345678.1圖的生成樹和最小生成樹任一生成樹的構造方法：從空集開始，依次加入圖中每個頂點。每加入一個頂點，就增加一條連接該點到已有部分的邊。12340561256734每個圖的生成樹可以構造許多棵。請問：生成樹的特點？1234056123456712340561234567生成樹的特點：含有n-1條邊。（n為圖的頂點數）生成樹中，任意增加一條邊，必定出現(xiàn)回路。生成樹中，任意刪除一條邊，必定變?yōu)榉沁B通圖。12340561256734最小生成樹（對于無向連通帶權圖）定義：網絡的每條邊上帶權值，因此，生成樹不同，每棵樹的權（樹中所有邊權值之和）也不同。其中，樹的權最小的生成樹叫做最小生成樹。實際意義：下圖代表6個城市間的交通網，邊上的權是公路的造價?，F(xiàn)在要用公路把6個城市聯(lián)系起來，問：至少需要修筑幾條公路？如何設計使公路的總造價最??？至少需要修筑5條公路，使公路總造價最小也就是找最小生成樹的問題。12340516192111143318665

在n個城市間建立通訊網絡，要考慮的問題是:如何在保證n點連通的前提下最節(jié)省經費36521655V5V4V2V0V3V146例即要構造連通網的最小生成樹。

這應在連通網的所有帶權的邊中選取n－1條邊（不構成回路），使權值之和為最小。？8.1.2Prime算法分析（以p276圖8-4(a)為例）：首先把圖中所有點劃分為兩個集合：生成樹內的點集T、生成樹外的點集T’，并且列出從生成樹內點集到生成樹外每個點的最短邊以供下次選擇。

生成樹內點集T生成樹外點集T’T的點到T’的各點的最短邊1：01，2，3，4，5，68，∞，5，∞，∞，∞2：0，31，2，4，5，63，∞，∞，7，153：0，3，12，4，5，612，10，7，154：0，3，1，52，4，62，9，155：0，3，1，5，24，66，156：0，3，1，5，2，46157：所有圖中點空集空集如果把（2,4）邊的權修改為12，（4,5）邊上的權改為11，則（2,4）邊不被選入，取而代之的是（1,4）邊被選入生成樹。V3V1V4V6V5V26665551324V3V1V4V6V5V2普里姆算法構造最小生成樹舉例V3V1V4V6V5V2V3V1V4V6V5V2TT’TEV3V1V4V6V5V2(v1,v3),(v3,v6),(v6,v4),(v3,v2),(v2,v5)123405161921111433186658.1.3Kruskal算法思想：按照權值遞增順序構造最小生成樹。1、選擇圖中權最小的邊，加入生成樹中，在圖中刪除這條邊2、再從圖中剩下的邊里選擇權最小者，若與生成樹中邊不構成回路，則加入生成樹。如此繼續(xù)，直到生成樹中包含n-1條邊。12（a）123（b）1235（c）12305（d）123405（e）abcdegf195141816821312727148531621例:7121819cdbaegf27算法實現(xiàn):k=1；d=0;//k為最小生成樹的邊數，d為待掃描的邊的//下標。開始時圖的所有邊按權值由小到大排while(k<n){

從邊集數組GE中取出第d條權值最小的邊(i,j);

若(i,j)加入CT后不使CT中產生回路， 則將邊(i,j)加入CT中;且

k++;d++;}8.2最短路徑

實際意義：交通網絡中常常提出這樣的問題：從甲地到乙地之間是否有公路連通?在有多條通路的情況下，哪一條路最短或運費最省或運輸時間最短?

解決方法：把交通網絡畫成帶權圖。頂點表示城市，邊表示兩個城市間的公路，邊上的權值可以表示公路長度、運費或運輸時間等。則上述問題就簡化為在帶權圖中求兩個頂點之間最短路徑的問題。這里的路徑是指邊上權的總和，而不是指路徑上邊數。ABC238如左圖，A到C的最短路徑是(A,B,C)，長度為5，包含兩條邊。求最短路徑的問題概念簡單，但計算量很大，所以用計算機解決很適合?？紤]有向圖，介紹兩個算法8.2.2求一個點到其余各點的最短路徑（Dijkstra算法）說明：某條路徑上的起點(出發(fā)點)稱為源點，路徑上的最后一個點稱為終點。思路：先把圖中頂點分為兩組：A組：已確定最短路徑的點

B組：未確定最短路徑的點1、初始時：A集合中只有源點（假設0）。列出源點到其余各點的直接路徑長度。從中選出路徑最短者，求得第一條最短路徑（假設為d(0,1)），把對應的這個點加入到A集合中。2、接著以該點（假設1）為中間點，修改源點到剩余各點（B集合中點）的最短路徑長度。也就是說，假如d(0,1)+d(1,2)<d(0,2)，則修改d(0,2)。修改后再從中選出路徑最短者，求得第二條，并把此路徑所對應點加入集合A3、依此類推，不斷以新的點作為中間點修改最短路徑長度，直到最后所有的點都進入A集合為止。具體實現(xiàn)時要使用三個數組：s[n]：用作標記某個點vi是否已求得最短路徑。若是，則相應的s[i]標記為1，否則0dist[n]：存放源點到其余各點最短路徑長度path[n]：存放源點到其余各點最短路徑，即所經過的點分析書上p281圖8-6(a)：初始：源點0，故A{0}、B{1,2,3,4}，列出dist[1]～dist[4]，找出最短路徑d[1]=3第1輪：A{0,1}、B{2,3,4}，以1作為中間點，看是否需要修改dist[2]～dist[4]。比較dist[j]和dist[1]+dist(1,j)的值，若后者小，則修改原值dist[j]。B集合中每個點都處理過后，從中（也就是從s取值為0的點集里）找出dist最小者dist[3]第二輪：A{0,1,3}、B{2,4}，以3作為中間點，比較dist[j]和dist[3]+dist(3,j)的值……∞10∞30

100V5

V4

1006053010V1

V2

V0

V310205012345dist[i]A｛｝ipath[i]10，V2,V4,V3V5

V4

V2

V0

V3603050905060,V5V0,

V2V0,

V4V0V4V3V0V4V3V5,V160∞無源點V02、求每對點之間的最短路徑（Floyed算法）前面已經可以求一個點到其余各點的最短路徑，現(xiàn)在要求每對點間最短路徑，一個直接辦法是？最直觀辦法是：輪流以每個點為源點，反復執(zhí)行Dijkstra算法n次，就能求得每個點到其余點的最短路徑。另一種Floyed算法：概念更簡單。其基本思想為：遞推地產生一個矩陣序列A(-1)，A(0)，A(1)，…，A(n-1)，其中初始的A(-1)[i][j]是圖的鄰接矩陣，其余的A(k)[i][j]=min{A(k-1)[i][j]，A(k-1)[i][k]＋A(k-1)[k][j]}具體地說，第一次把V0作為中間點，用上式檢查矩陣A(-1)中除V0對應行和列以外的每個元素，作相應修改，得矩陣A(0)。第二次把V1作為中間點，用上式檢查矩陣A(0)中除V1對應行和列以外的每個元素，作類似檢查和修改，得矩陣A(1)?！钡矫總€點都做過一次中間點，最后矩陣A(n-1)給出任意兩點間的最短路徑長度。8.3拓撲排序

實例：通常我們把計劃、施工過程、生產流程、程序流程等都看作一個大工程，大工程常常被劃分成許多小的子工程，這些子工程稱為活動。這些活動之間可能有一定的先后關系。當這個工程中所有活動都完成時，整個工程完成。例如：計算機專業(yè)學生的課程開設可看成是一個工程，每一門課程就是工程中的活動，圖8-9給出了若干門所開設的課程，其中有些課程的開設有先后關系，有些則沒有先后關系，有先后關系的課程必須按先后關系開設，如開設數據結構課程之前必須先學完算法語言及離散數學，而開設離散數學則必須學完高等數學和程序設計基礎。為了反映整個工程中各活動之間的先后關系，我們可以采用有向圖來表示。8.3拓撲排序

學生選修課程問題頂點——表示課程（即活動）有向邊——表示先決條件，若課程i是j的先決條件，則圖中有邊<i,j>學生應按怎樣的順序學習這些課程，才能無矛盾、順利地完成學業(yè)——拓撲排序有向圖中，頂點表示活動，有向邊表示活動的優(yōu)先關系，如<Vi,Vj>表示活動Vi必須在Vj之前完成。這種有向圖叫做頂點活動網，簡稱AOV網。AOV網——有向無環(huán)圖有向：清楚地表示出各活動先后關系。無環(huán)：指圖中無回路。如果出現(xiàn)回路，則回路上活動無法進行由于AOV網中無回路，因此可以把所有活動排成一個線性序列，并保證各活動按先后順序要求排列。這種把有向圖線性化的過程就叫做拓撲排序。得到的線性序列叫做拓撲序列。對圖8-10進行拓撲排序結果可以有多個，因此拓撲序列不唯一。實際意義：整個工程若按拓撲序列的順序依次進行，則每項活動開始時，其前驅活動已完成，各活動間就不會發(fā)生沖突。

拓撲排序算法基本思想：（1）選擇一個入度為0的點并輸出（2）從圖中刪除該點及其所有出邊反復執(zhí)行以上兩步，直到所有點都輸出，則拓撲排序完成。或者剩下的點中沒有入度為0者，則說明圖中有回路。C7C1C2C4C9C12C11C10C6C8C5C3表示必修課程優(yōu)先關系的有向圖（AOV網）必修課程關系表課程編號課程名稱先決條件

C1

程序設計基礎無

C2離散數學C1C3數據結構C1

，C2C4匯編語言C1C5語言的設計與分析C3，C4C6計算機原理C11C7編譯原理C3，C5C8操作系統(tǒng)C3，C6C9高等數學無

C10線性代數C9C11普通物理C9C12數值分析C9，C10，C1舉例：C7C1C2C4C9C12C11C10C6C8C5C3拓撲排序：拓撲序列為：C1C4C2C3C5C7C9C11C6C10C12C8

拓撲排序算法的具體實現(xiàn)準備工作：

圖——鄰接表表示（刪除出邊比較方便）一維數組d[n]——存放圖中每個點的入度值?！獣捍嫒攵葹?的點拓撲排序過程：檢查d[n]數組，把所有入度為0的點進棧從棧頂彈一個點top，檢查它的出邊表，對每條出邊的終點，把它在d[n]中對應的入度值減1（相當于刪除top點所有出邊）。若發(fā)現(xiàn)某點入度為0，則入棧。01出棧404進棧04出棧0出棧22入棧2出棧312200012345d1301100d2201000d4000000d6201100d3012345100000d5012345100,1進棧33入棧3出棧8.4關鍵路徑

研究對象——AOE網，即邊表示活動的網絡，邊上的權表示活動持續(xù)時間。常常用AOE網表示工程的計劃或進度。AOE網是一個有向帶權圖，其中：

邊：表示活動(子工程)；

邊上的權：表示該活動的持續(xù)時間，即完成該活動所需要的時間；

頂點：表示事件，每個事件是活動與活動之間的轉接點，即表示在它之前的所有活動已經完成，在它之后的活動可以開始。

實際意義——解決以下兩個問題

1)估算整個工程至少需多長時間完成

2)哪些活動是影響工程進度的關鍵，通過縮短關鍵活動的時間（即縮短關鍵路徑）可加快工程進度。V0V1V2V3V4V5V6V7V8a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4有9個事件、11個活動的AOE網舉例：工程的開始點（源點）工程的完成點（匯點）8.4關鍵路徑

關鍵路徑：路徑長度最長的路徑。關鍵活動：關鍵路徑上的活動。求工程的最短工期：在AOE網上求一條關鍵路徑的長度。

問題：

1.完成一項工程至少需要多長時間？

2.影響一項工程進度的活動是哪些？

3.如何加快工程進度、縮短工程完成時間？——源點到匯點的最長路徑的長度——最長路徑上的所有活動——縮短最長路徑長度8.4關鍵路徑

8.4關鍵路徑

設源點是v0,定義：事件vi的最早發(fā)生時間ve(i)：事件vi最早可以發(fā)生的時間，即從v0到vi的最長路徑長度。事件vi的最遲發(fā)生時間vl(i)

：在不影響整個工程進度的前提下事件vi最遲必須發(fā)生的時間。（從匯點往回算）ve(0)=0ve(j)=max{ve(i)+dut(<i,j>)}j=2,3,…,n{vl(n)=ve(n)vl(i)=min{vl(j)-dut(<i,j>)}j=n-1,n-2,…,1{8.4關鍵路徑

活動ak=<vi,vj>的最早開始時間ee(k)

：等于事件vi的最早發(fā)生時間ve(i)?；顒觓k=<vi,vj>的最遲開始時間el(k)

：在不影響整個工程進度的前提下，活動ak最遲必須開始的時間，等于事件vj的最遲發(fā)生時間vl(j)減去活動ak的持續(xù)時間dut(<i,j>)。關鍵活動ak=<vi,vj>即為ee(k)=el(k)的活動。ee(k)=ve(i)el(k)=vl(j)-dut(<i,j>)其中活動ak=<vi，vj>{頂點ive(i)vl(i)V0

v1

v2

v3

v4

v5v6v7

v8

0645771614180668710161418V0V1V2V3V4V5V6V7V8a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=48.4關鍵路徑

活動kdut(k)ee(k)el(k)el(k)-ee(k)

a1

a2

a3

a4

a5

a6

a7

a8

a9

a10

a11

6451129742400064577716140236687710161402302300300頂點ive(i)vl(i)V0

v1

v2