圖本章說明課件

本章說明7.1圖的定義和術(shù)語7.2圖的存儲結(jié)構(gòu)7.3圖的遍歷7.4生成樹7.5拓?fù)渑判?.6最短路徑

本章小結(jié)數(shù)據(jù)結(jié)構(gòu)返回主目錄本章說明數(shù)據(jù)結(jié)構(gòu)返回主目錄學(xué)習(xí)目標(biāo)領(lǐng)會圖的類型定義。熟悉圖的各種存儲結(jié)構(gòu)及其構(gòu)造算法，了解各種存儲結(jié)構(gòu)的特點(diǎn)及其選用原則。熟練掌握圖的兩種遍歷算法。理解各種圖的應(yīng)用問題的算法。本章說明學(xué)習(xí)目標(biāo)本章說明重點(diǎn)和難點(diǎn)圖的應(yīng)用極為廣泛，而且圖的各種應(yīng)用問題的算法都比較經(jīng)典，因此本章重點(diǎn)在于理解各種圖的算法及其應(yīng)用場合。知識點(diǎn)圖的類型定義、圖的存儲表示、圖的深度優(yōu)先搜索遍歷和圖的廣度優(yōu)先搜索遍歷、無向網(wǎng)的最小生成樹、最短路徑、拓?fù)渑判颉㈥P(guān)鍵路徑本章說明重點(diǎn)和難點(diǎn)本章說明7.1圖的定義和術(shù)語

圖(Graph)——圖G是由兩個集合V和VR組成的，記為G=(V,VR)其中：V是頂點(diǎn)的有窮非空有限集VR是兩個頂點(diǎn)之間關(guān)系的有限集合，即邊集合，邊是頂點(diǎn)的無序?qū)蛴行驅(qū)?/p>

有向圖——有向圖G是由兩個集合V和VR組成的其中：V是頂點(diǎn)的有窮非空有限集VR是有向邊（也稱?。┑挠邢藜?，弧是頂點(diǎn)的有序?qū)?，記?lt;v,w>，v,w是頂點(diǎn)，v為弧尾，w為弧頭7.1圖的定義和術(shù)語圖(Graph)——圖G是由兩個集7.1圖的定義和術(shù)語例如:G1=(V1,VR1)其中V1={1,2,3,4}VR1={<1,2>,<1,3>,<3,4>,<4,1>}有向圖G124137.1圖的定義和術(shù)語例如:G1=(V1,VR1)其7.1圖的定義和術(shù)語無向圖——由頂點(diǎn)集和邊集構(gòu)成的圖。若<v,w>VR必有<w,v>VR,則稱(v,w)為頂點(diǎn)v和頂點(diǎn)w之間存在一條邊。例如:G2=(V2,VR2)V2={A,B,C,D,E,F}VR2={(A,B),(A,E),(B,E),(C,D),(D,F),(B,F),(C,F)}無向圖G2251437.1圖的定義和術(shù)語無向圖——由頂點(diǎn)集和邊集構(gòu)成的圖。7.1圖的定義和術(shù)語有向完全圖——有n個頂點(diǎn)，n(n-1)弧的有向圖

無向完全圖——有n個頂點(diǎn)，n(n-1)/2條邊的無向圖例有向完全圖無向完全圖1232317.1圖的定義和術(shù)語有向完全圖——有n個頂點(diǎn)，n(n-7.1圖的定義和術(shù)語稀疏圖——有很少條邊和弧(e<nlogn)的圖稠密圖——與稀疏圖相反

權(quán)——與圖的邊或弧相關(guān)的數(shù)網(wǎng)——帶權(quán)的圖有向網(wǎng)——弧帶權(quán)的圖無向網(wǎng)——邊帶權(quán)的圖ABEC1圖的定義和術(shù)語稀疏圖——有很少條邊和弧(e<nl

子圖——如果圖G(V，E)和圖G′(V′，E′)，滿足：V′

V且E′E，則稱G′為G的子圖鄰接點(diǎn)——在無向圖中一條邊連起來的兩個頂點(diǎn)(v,v′)，互稱鄰接點(diǎn)，稱邊(v,v′)依附于頂點(diǎn)v和v′7.1圖的定義和術(shù)語BBCAEFC子圖——如果圖G(V，E)和圖G′(V′，E′)，滿足：7.1圖的定義和術(shù)語ABECF頂點(diǎn)的度(TD)=出度(OD)+入度(ID)例如:ID(B)=2OD(B)=1TD(B)=3頂點(diǎn)的度無向圖中頂點(diǎn)的度為與每個頂點(diǎn)相連的邊數(shù)有向圖中頂點(diǎn)的度為:入度：以該頂點(diǎn)為頭的弧的數(shù)目出度：以該頂點(diǎn)為尾的弧的數(shù)目7.1圖的定義和術(shù)語ABECF頂點(diǎn)的度(TD)=例如:I7.1圖的定義和術(shù)語路徑——路徑是一個頂點(diǎn)的序列V={Vi,0,Vi,1,……Vi,n}，滿足(Vi,j-1,Vi,j)E或<Vi,j-1,Vi,j>E,(1<jn)路徑上邊的數(shù)目稱作“路徑長度”回路（環(huán)）——第一個頂點(diǎn)和最后一個頂點(diǎn)相同的路徑簡單路徑——序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑簡單回路——除了第一個頂點(diǎn)和最后一個頂點(diǎn)外，其余頂點(diǎn)不重復(fù)出現(xiàn)的回路7.1圖的定義和術(shù)語路徑——路徑是一個頂點(diǎn)的序列V={7.1圖的定義和術(shù)語連通——從頂點(diǎn)V到頂點(diǎn)W有一條路徑，則說V和W是連通的連通圖——圖中任意個頂點(diǎn)都是連通的例G1245136路徑：1，2，3，5，6，3路徑長度：5簡單路徑：1，2，3，5回路：1，2，3，5，6，3，1簡單回路：3，5，6，3例連通圖2451367.1圖的定義和術(shù)語連通——從頂點(diǎn)V到頂點(diǎn)W有一條路徑，連通分量——指的是無向圖中的極大連通子圖強(qiáng)連通圖——有向圖中，如果對每一對Vi,VjV,Vi

Vj,從Vi到Vj

和從Vj到Vi都存在路徑強(qiáng)連通分量——指的是有向圖中的極大強(qiáng)連通子圖7.1圖的定義和術(shù)語強(qiáng)連通圖356例例245136非連通圖連通分量——指的是無向圖中的極大連通子圖7.1圖的定義和7.1圖的定義和術(shù)語生成樹——是連通圖的一個極小連通子圖，它含有圖的全部頂點(diǎn)，但只有足以構(gòu)成一棵樹的n-1條邊生成森林——對非連通圖，各個連通分量的生成樹的集合ABCDEFCDABEF一個有向圖及其生成森林7.1圖的定義和術(shù)語生成樹——是連通圖的一個極小連通子圖7.2圖的存儲結(jié)構(gòu)圖的數(shù)組(鄰接矩陣)存儲表示圖的鄰接表存儲表示有向圖的十字鏈表存儲表示無向圖的鄰接多重表存儲表示7.2圖的存儲結(jié)構(gòu)圖的數(shù)組(鄰接矩陣)存儲表示圖7.2圖的存儲結(jié)構(gòu)

鄰接矩陣——表示頂點(diǎn)間相聯(lián)關(guān)系的矩陣定義：設(shè)G=(V,E)是有n1個頂點(diǎn)的圖，G的鄰接矩陣A是具有以下性質(zhì)的n階方陣圖的數(shù)組(鄰接矩陣)存儲表示7.2圖的存儲結(jié)構(gòu)鄰接矩陣——表示頂點(diǎn)間相聯(lián)關(guān)系的矩陣7.2圖的存儲結(jié)構(gòu)

有向圖G1v2v4v1v3無向圖G2v2v5v1v4v37.2圖的存儲結(jié)構(gòu)有7.2圖的存儲結(jié)構(gòu)特點(diǎn)：無向圖的鄰接矩陣對稱，可壓縮存儲；有n個頂點(diǎn)的無向圖需存儲空間為n(n+1)/2有向圖鄰接矩陣不一定對稱；有n個頂點(diǎn)的有向圖需存儲空間為n2無向圖中頂點(diǎn)Vi的度TD(Vi)是鄰接矩陣A中第i行元素之和有向圖中:頂點(diǎn)Vi的出度是A中第i行元素之和頂點(diǎn)Vi的入度是A中第i列元素之和網(wǎng)的鄰接矩陣可定義為：7.2圖的存儲結(jié)構(gòu)特點(diǎn)：7.2圖的存儲結(jié)構(gòu)

例23753186421457.2圖的存儲結(jié)構(gòu)例237531867.2圖的存儲結(jié)構(gòu)鄰接矩陣的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：容易實(shí)現(xiàn)圖的創(chuàng)建、銷毀、查找頂點(diǎn)v和返回v的值操作。容易判定頂點(diǎn)間有無邊（?。?，容易計(jì)算頂點(diǎn)的度（出度、入度）

缺點(diǎn)：所占空間只和頂點(diǎn)個數(shù)有關(guān)，和邊數(shù)無關(guān)，在邊數(shù)較少時，空間浪費(fèi)較大鄰接矩陣的存儲表示#defineINFINITYINT_MAX#defineMAX_VERTEX_NUM20typedefenum{DG,DN,AG,AN}GraphKind;

//{有向圖，有向網(wǎng)，無向圖，無向網(wǎng)}7.2圖的存儲結(jié)構(gòu)鄰接矩陣的優(yōu)缺點(diǎn)鄰接矩陣的存儲表示7.2圖的存儲結(jié)構(gòu)typedefstructArcCell{//鄰接矩陣VRTypeadj;//頂點(diǎn)關(guān)系類型InfoType*info;//該弧相關(guān)信息的指針}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];//頂點(diǎn)向量AdjMatrixarcs;//弧的信息intvexnum,arcnum;//頂點(diǎn)數(shù)和弧數(shù)GraphKindkind;//圖的種類}MGraph;7.2圖的存儲結(jié)構(gòu)typedefstructArcC7.2圖的存儲結(jié)構(gòu)建立無向圖鄰接矩陣的算法

算法中：G.vexs[]，一維，頂點(diǎn)向量.arcs[][]，二維，鄰接矩陣.vexnum，頂點(diǎn)數(shù).arcnum，邊數(shù)7.2圖的存儲結(jié)構(gòu)建立無向圖鄰接矩陣的算法7.2圖的存儲結(jié)構(gòu)圖的鄰接表存儲表示

鄰接表是圖的一種鏈?zhǔn)酱鎯Y(jié)構(gòu)，為依附每個頂點(diǎn)的邊（或?。┙⒁粋€單鏈表頂點(diǎn)結(jié)構(gòu)

adjvexnextarcinfo表結(jié)點(diǎn)datafirstarc頭結(jié)點(diǎn)頂點(diǎn)位置下一條弧相關(guān)信息頂點(diǎn)數(shù)據(jù)第一條弧7.2圖的存儲結(jié)構(gòu)圖的鄰接表存儲表示鄰接表是圖的一V1V2

V3V40123V1V2V3V4V5012347.2圖的存儲結(jié)構(gòu)有向圖G12413無向圖G22514312

3

0

31

420

431

20

21

V1V2V3V40V1V2V3V4V507.2圖的存儲7.2圖的存儲結(jié)構(gòu)圖的鄰接表存儲表示

#defineMAX_VERTEX_NUM20TypedefstructArcNode//表結(jié)點(diǎn){intAdjvex;//與vi鄰接的頂點(diǎn)的下標(biāo)位置structArcNode*nextarc;//與vi鄰接的下一個頂點(diǎn)InfoType*info;}//ArcNode;TypedefstructVnode//頭結(jié)點(diǎn){VertexTypedata;ArcNode*firstarc;}Vnode,AdjList[MAX_VERTEX_NUM];Typedefstruct//圖{AdjListvertices;intvexnum,arcnum,kind;}ALGraph;7.2圖的存儲結(jié)構(gòu)圖的鄰接表存儲表示#define7.2圖的存儲結(jié)構(gòu)鄰接表是頂點(diǎn)的向量結(jié)構(gòu)和邊（弧）的單鏈表結(jié)構(gòu)每個頂點(diǎn)結(jié)點(diǎn)包括兩個域，將n個頂點(diǎn)放在一個向量中（稱為順序存儲的結(jié)點(diǎn)表）；一個頂點(diǎn)的所有鄰接點(diǎn)鏈接成單鏈表，該頂點(diǎn)在向量中有一個指針域指向其第一個鄰接點(diǎn)。鄰接表的優(yōu)缺點(diǎn)空間較?。粺o向圖容易求各頂點(diǎn)的度；表中結(jié)點(diǎn)個數(shù)是邊的兩倍；有向圖容易求頂點(diǎn)的出度；不容易求頂點(diǎn)的入度，要遍歷整個表。為了求頂點(diǎn)的入度，有時可設(shè)逆鄰接表（指向某頂點(diǎn)的鄰接點(diǎn)鏈接成單鏈表）7.2圖的存儲結(jié)構(gòu)鄰接表是頂點(diǎn)的向量結(jié)構(gòu)和邊（弧）的單7.2圖的存儲結(jié)構(gòu)建立鄰接表的算法有向圖G12413V1V2V3V43

0

0

2

逆鄰接表第i(下標(biāo)i-1)鏈表的結(jié)點(diǎn)個數(shù)即為Vi頂點(diǎn)的入度。7.2圖的存儲結(jié)構(gòu)建立鄰接表的算法有向圖G127.2圖的存儲結(jié)構(gòu)有向圖的十字鏈表存儲表示十字鏈表結(jié)點(diǎn)結(jié)構(gòu)tailvexheadvexhlinktlinkinfo弧結(jié)點(diǎn)datafirstinfirstout頂點(diǎn)結(jié)點(diǎn)弧尾位置弧頭位置弧尾相同的下一條弧指針弧相關(guān)信息的指針弧頭相同的下一條弧指針指向該頂點(diǎn)第一條入弧指向該頂點(diǎn)第一條出弧7.2圖的存儲結(jié)構(gòu)有向圖的十字鏈表存儲表示十字鏈7.2圖的存儲結(jié)構(gòu)例v2v4v1v302012320323130^v1v2v3v40123^^^^^^^7.2圖的存儲結(jié)構(gòu)例v2v4v1v3020127.2圖的存儲結(jié)構(gòu)有向圖十字鏈表存儲表示#defineMAX_VERTEX_NUM20typedefstructArcBox//弧結(jié)點(diǎn){inttailvex,hesdvex;structArcBox*hlink,*tlink;infoType*info;}ArcBox;TypedefstructVexNode//頂點(diǎn)結(jié)點(diǎn){VertexTypedata;ArcBox*firstin,*firstout;}VexNode;Typedefstruct{//頂點(diǎn)表VexNodexlist[MAX_VERTEX_NUM];//表頭向量intvexnum,arcnum;}OLGraph;7.2圖的存儲結(jié)構(gòu)有向圖十字鏈表存儲表示#define7.2圖的存儲結(jié)構(gòu)建立有向圖十字鏈表算法

思想：（1）初始化表頭向量、數(shù)據(jù)、指針（2）輸入一條弧，確定在G中位置，申請結(jié)點(diǎn)空間，賦值（3）插入到十字鏈表中（4）若InInfo=1，輸入其信息（5）重復(fù)（2）至（4），直到所有弧輸入完為止。7.2圖的存儲結(jié)構(gòu)建立有向圖十字鏈表算法7.2圖的存儲結(jié)構(gòu)無向圖的鄰接多重表存儲表示鄰接多重表結(jié)點(diǎn)結(jié)構(gòu)markivexilinkjvexinfo邊結(jié)點(diǎn)jlinkdatafirstedge頂點(diǎn)結(jié)點(diǎn)i頂點(diǎn)下一個依附于i頂點(diǎn)的邊j頂點(diǎn)下一個依附于j頂點(diǎn)的邊第1個依附于該頂點(diǎn)的邊7.2圖的存儲結(jié)構(gòu)無向圖的鄰接多重表存儲表示鄰接多7.2圖的存儲結(jié)構(gòu)例v1v2v4v5v30123v1v3v4v24v5010323212441^^^^^指向下一個依附于v1的邊指向下一個依附于v2的邊7.2圖的存儲結(jié)構(gòu)例v1v2v4v5v30123v1v37.2圖的存儲結(jié)構(gòu)無向圖鄰接多重表存儲表示#defineMAX_VERTEX_NUM20Typedefemnu{unvisited,visited}VisitIf;typedefstructArcBox//弧結(jié)點(diǎn){VisitIfmark;intivex,jvex;structEBox*ilink,*jlink;infoType*info;}EBox;TypedefstructVexBox//頂點(diǎn)結(jié)點(diǎn){VertexTypedata;EBox*firstedge;//指向第1條依附該頂點(diǎn)的邊}VexBox;Typedefstruct{//頂點(diǎn)表VexBoxadjlist[MAX_VERTEX_NUM];intvexnum,arcnum;}AMLGraph;7.2圖的存儲結(jié)構(gòu)無向圖鄰接多重表存儲表示#defin7.3圖的遍歷從圖的某頂點(diǎn)出發(fā)，對圖中的每個頂點(diǎn)進(jìn)行一次訪問且使每個頂點(diǎn)僅被訪問一次的過程。深度優(yōu)先遍歷廣度優(yōu)先遍歷7.3圖的遍歷從圖的某頂點(diǎn)出發(fā)，對圖中的7.3圖的遍歷思想：（1）從圖的某一頂點(diǎn)V0出發(fā)，訪問該頂點(diǎn)；然后依次從V0的未被訪問的鄰接點(diǎn)出發(fā)，深度優(yōu)先遍歷圖，直至圖中所有和V0相通的頂點(diǎn)都被訪問到；（2）若此時圖中尚有頂點(diǎn)未被訪問，則另選圖中一個未被訪問的頂點(diǎn)作起點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問為止

深度優(yōu)先遍歷7.3圖的遍歷思想：深度優(yōu)先遍歷7.3圖的遍歷V1V2V4V5V3V7V6V8例1深度遍歷：V1V2V4V8V5V3V6V7V1V2V4V5V3V7V6V87.3圖的遍歷V1V2V4V5V3V7V6V8例1深度遍7.3圖的遍歷例2V1V2V4V5V3V7V6V8例3V1V2V4V5V3V7V6V8例2：V1V2V4V8V5V6V3V7例3：V1V2V4V8V5V6V3V7V1V2V4V5V3V7V6V8例4例4：V1V2V4V8V3V6V7V57.3圖的遍歷例2V1V2V4V5V3V7V6V8例3V7.3圖的遍歷從上面例可見:1.從深度優(yōu)先搜索遍歷連通圖的過程類似于樹的先根遍歷;解決的辦法是:為每個頂點(diǎn)設(shè)立一個“訪問標(biāo)志visited[w]”;2.如何判別V的鄰接點(diǎn)是否被訪問？7.3圖的遍歷從上面例可見:1.從深度優(yōu)先搜索遍歷連通7.3圖的遍歷開始訪問標(biāo)志初始化i=1Vi訪問過DFSi=i+1i==Vexnums結(jié)束NNYY深度優(yōu)先遍歷算法開始訪問V,置標(biāo)志求V鄰接點(diǎn)有鄰接點(diǎn)w求下一鄰接點(diǎn)W訪問過結(jié)束NYNYDFSwV07.3圖的遍歷開始訪問標(biāo)志初始化i=1Vi訪問過DFSi7.3圖的遍歷abchdekfg812345670FFFFFFFFF012345678TTTTTTTTTachdkfebgachkfedbg訪問標(biāo)志:訪問次序:例如:achdkfe7.3圖的遍歷abchdekfg812345670F7.3圖的遍歷

廣度優(yōu)先搜索思想（1）從圖的某一頂點(diǎn)V0出發(fā)，訪問該頂點(diǎn)后，依次訪問V0的各個未被訪問過的鄰接點(diǎn)；然后分別從這些鄰接點(diǎn)出發(fā)，廣度優(yōu)先遍歷圖，直至圖中所有已被訪問的頂點(diǎn)的鄰接點(diǎn)都被訪問到（2）若此時圖中尚有頂點(diǎn)未被訪問，則另選圖中一個未被訪問的頂點(diǎn)作起點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問為止7.3圖的遍歷廣度優(yōu)先搜索思想7.3圖的遍歷V1V2V4V5V3V7V6V8例1廣度遍歷：V1V2V3V4V5V6V7V8V1V4V5V3V7V8V2V67.3圖的遍歷V1V2V4V5V3V7V6V8例1廣度遍7.3圖的遍歷例2V1V2V4V5V3V7V6V8例3V1V2V4V5V3V7V6V8例2：V1V2V3V4V5V6V7V8例3：V1V2V3V4V5V6V7V8V1V2V4V5V3V7V6V8例4例4：V1V2V3V4V6V7V8V57.3圖的遍歷例2V1V2V4V5V3V7V6V8例3V7.3圖的遍歷廣度優(yōu)先遍歷算法思想：借助隊(duì)列開始標(biāo)志數(shù)組初始化Vi=1Vi訪問過BFSVi=Vi+1Vi==Vexnums結(jié)束NNYY7.3圖的遍歷廣度優(yōu)先遍歷算法開始標(biāo)志數(shù)組初始化Vi=7.3圖的遍歷開始訪問V0,置標(biāo)志求V鄰接點(diǎn)ww存在嗎V下一鄰接點(diǎn)ww訪問過結(jié)束NYNYBFS初始化隊(duì)列V0入隊(duì)隊(duì)列空嗎隊(duì)頭V出隊(duì)訪問w,置標(biāo)志w入隊(duì)NY7.3圖的遍歷開始訪問V0,置標(biāo)志求V鄰接點(diǎn)ww存在嗎V7.4生成樹生成樹最小生成樹構(gòu)造最小生成樹7.4生成樹生成樹最小生成樹構(gòu)造最小生成樹7.4生成樹生成樹定義：所有（n個）頂點(diǎn)均由邊（n-1個）連接在一起，但不存在回路的圖深度優(yōu)先生成樹：由深度優(yōu)先遍歷得到的生成樹廣度優(yōu)先生成樹：由廣度優(yōu)先遍歷得到的生成樹生成森林：非連通圖每個連通分量的生成樹一起組成非連通圖7.4生成樹生成樹7.4生成樹說明一個圖可以有許多棵不同的生成樹所有生成樹具有以下共同特點(diǎn)：生成樹的頂點(diǎn)個數(shù)與圖的頂點(diǎn)個數(shù)相同生成樹是圖的極小連通子圖一個有n個頂點(diǎn)的連通圖的生成樹有n-1條邊生成樹中任意兩個頂點(diǎn)間的路徑是唯一的在生成樹中再加一條邊必然形成回路含n個頂點(diǎn)n-1條邊的圖不一定是生成樹7.4生成樹說明7.4生成樹V5V1V2V4V3V7V6V8例深度：V1V2V4V8V5V3V6V7V1V2V4V5V3V7V6V8深度優(yōu)先生成樹V1V2V4V5V3V7V6V8廣度優(yōu)先生成樹廣度：V1V2V3V4V5V6V7V8V5V1V2V4V3V7V6V8V5V1V2V4V3V7V6V87.4生成樹V5V1V2V4V3V7V6V8例深度：V17.4生成樹例ABLMCFDEGHKIJABLMCFJDEGHKI深度優(yōu)先生成森林7.4生成樹例ABLMCFDEGHKIJABLMCFJD7.4生成樹最小生成樹問題提出

假設(shè)要在n個城市之間建立通訊聯(lián)絡(luò)網(wǎng)，則連通n個城市只需要修建n-1條線路，如何在最節(jié)省經(jīng)費(fèi)的前提下建立這個通訊網(wǎng)？頂點(diǎn)——表示城市權(quán)——城市間建立通信線路所需花費(fèi)代價(jià)

最?。ù鷥r(jià)）生成樹：希望找到一棵生成樹，它的每條邊上的權(quán)值之和即建立該通信網(wǎng)所需花費(fèi)的總代價(jià)）最小7.4生成樹最小生成樹7.4生成樹問題分析

n個城市間，最多可設(shè)置n(n-1)/2條線路n個城市間建立通信網(wǎng)，只需n-1條線路該問題等價(jià)于：構(gòu)造網(wǎng)的一棵最小生成樹，即：在e條帶權(quán)的邊中選取n-1條邊（不構(gòu)成回路），使“權(quán)值之和”為最小。16543271317918127524107.4生成樹問題分析165432713179181277.4生成樹構(gòu)造最小生成樹方法方法一：普里姆(Prim)算法（選點(diǎn)法）思想：設(shè)N=(V,{E})是連通網(wǎng)，TE是N上最小生成樹中邊的集合（1）初始令U={u0},(u0V),TE=（2）在所有uU,vV-U的邊(u,v)E中，找一條代價(jià)最小的邊(u0,v0)（3）將(u0,v0)并入集合TE，同時v0并入U(xiǎn)（4）重復(fù)上述操作直至U=V為止，則T=(V,{TE})為N的最小生成樹樹存儲結(jié)構(gòu)：鄰接矩陣表示算法實(shí)現(xiàn)算法評價(jià)：O(n2)7.4生成樹構(gòu)造最小生成樹方法7.4生成樹例16543265135664255352461314211316131446131425246131427.4生成樹例1654326513566425535247.4生成樹方法二：克魯斯卡爾算法（選邊法）思想：設(shè)N=(V,{E})是連通網(wǎng)，TE是N上最小生成樹中邊的集合（1）初始狀態(tài)為只有n個頂點(diǎn)而無邊的非連通圖T=(V,{})，每個頂點(diǎn)自成一個連通分（2）在E中選取代價(jià)最小的邊，若該邊依附的頂點(diǎn)落在T中不同的連通分量上，則將此邊加入到T中；否則，舍去此邊，選取下一條代價(jià)最小的邊（3）依此類推，直至T中所有頂點(diǎn)都在同一連通分量上為止7.4生成樹方法二：克魯斯卡爾算法（選邊法）7.4生成樹例165432651356642516543265135664257.4生成樹例1654326513566425165437.4生成樹算法描述：構(gòu)造非連通圖ST=(V,{});k=i=0;//k計(jì)選中的邊數(shù)while(k<n-1){++i;檢查邊集E中第i條權(quán)值最小的邊(u,v);

若(u,v)加入ST后不使ST中產(chǎn)生回路，

則輸出邊(u,v);

且k++;}7.4生成樹算法描述：7.4生成樹普里姆算法克魯斯卡爾算法時間復(fù)雜度O(n2)O(eloge)稠密圖稀疏圖算法名適應(yīng)范圍比較兩種算法7.4生成樹普里姆算法克魯斯卡爾算法時間復(fù)雜度O(n2)7.5拓?fù)渑判蛴邢驘o環(huán)圖拓?fù)渑判蜿P(guān)鍵路徑7.5拓?fù)渑判蛴邢驘o環(huán)圖拓?fù)渑判蜿P(guān)鍵路徑7.5拓?fù)渑判蛴邢驘o環(huán)圖：一個無環(huán)的有向圖（DAG）是描述一項(xiàng)工程或系統(tǒng)的進(jìn)行過程的有效工具。7.5拓?fù)渑判蛴邢驘o環(huán)圖：一個無環(huán)的有向圖（DAG）7.5拓?fù)渑判騿栴}提出：學(xué)生選修課程問題頂點(diǎn)——表示課程有向弧——表示先決條件，若課程i是課程j的先決條件，則圖中有弧<i,j>學(xué)生應(yīng)按怎樣的順序?qū)W習(xí)這些課程，才能無矛盾、順利地完成學(xué)業(yè)——拓?fù)渑判蚨xAOV網(wǎng)——用頂點(diǎn)表示活動，用弧表示活動間優(yōu)先關(guān)系的有向圖稱為頂點(diǎn)表示活動的網(wǎng)(ActivityOnVertexnetwork)，簡稱AOV網(wǎng)若<vi,vj>是圖中有向邊，則vi是vj的直接前驅(qū)；vj是vi的直接后繼AOV網(wǎng)中不允許有回路，這意味著某項(xiàng)活動以自己為先決條件7.5拓?fù)渑判騿栴}提出：學(xué)生選修課程問題7.5拓?fù)渑判蛲負(fù)渑判颉袮OV網(wǎng)絡(luò)中各頂點(diǎn)按照它們相互之間的優(yōu)先關(guān)系排列成一個線性序列的過程檢測AOV網(wǎng)中是否存在環(huán)方法：對有向圖構(gòu)造其頂點(diǎn)的拓?fù)溆行蛐蛄?，若網(wǎng)中所有頂點(diǎn)都在它的拓?fù)溆行蛐蛄兄?，則該AOV網(wǎng)必定不存在環(huán)拓?fù)渑判虻姆椒ㄔ谟邢驁D中選一個沒有前驅(qū)的頂點(diǎn)且輸出之從圖中刪除該頂點(diǎn)和所有以它為尾的弧重復(fù)上述兩步，直至全部頂點(diǎn)均已輸出；或者當(dāng)圖中不存在無前驅(qū)的頂點(diǎn)為止7.5拓?fù)渑判蛲負(fù)渑判颉袮OV網(wǎng)絡(luò)中各頂點(diǎn)按照它們相7.5拓?fù)渑判駽1C2C3C4C5C6C7C8C9C10C11C12無C1C1,C2C1C3,C4C11C3.C5C3,C6無C9C9C1,C9,C10程序設(shè)計(jì)基礎(chǔ)離散數(shù)學(xué)數(shù)據(jù)結(jié)構(gòu)匯編語言語言的設(shè)計(jì)和分析計(jì)算機(jī)原理編譯原理操作系統(tǒng)高等數(shù)學(xué)線性代數(shù)普通物理數(shù)值分析課程代號課程名稱先修課C1C2C3C4C5C6C7C8C9C10C11C12例7.5拓?fù)渑判駽1無程序設(shè)計(jì)基礎(chǔ)課程代號7.5拓?fù)渑判駽1C2C3C4C5C6C7C8C9C10C11C12拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12--C8或：C9--C10--C11--C6--C1--C12--C4--C2--C3--C5--C7--C8一個AOV網(wǎng)的拓?fù)湫蛄胁皇俏ㄒ坏?.5拓?fù)渑判駽1C2C3C4C5C6C7C8C9C107.5拓?fù)渑判駽1C2C3C4C5C6C7C8C9C10C11C127.5拓?fù)渑判駽1C2C3C4C5C6C7C8C9C10C3C4C5C6C7C8C9C10C11C127.5拓?fù)渑判駽2C3C4C5C6C7C8C9C10C11C12C3C4C5C6C7C8C9C10C11C127.5拓?fù)?.5拓?fù)渑判駽4C5C6C7C8C9C10C11C12C5C6C7C8C9C10C11C127.5拓?fù)渑判駽4C5C6C7C8C9C10C11C12C6C8C9C10C11C127.5拓?fù)渑判駽6C7C8C9C10C11C12C6C8C10C11C12C6C8C11C12C6C8C9C10C11C127.5拓?fù)渑判駽6C7C87.5拓?fù)渑判駽6C8C12C8C12C87.5拓?fù)渑判駽6C8C12C8C12C87.5拓?fù)渑判蛩惴▽?shí)現(xiàn)以鄰接表作存儲結(jié)構(gòu)把鄰接表中所有入度為0的頂點(diǎn)進(jìn)棧棧非空時，輸出棧頂元素Vj并退棧；在鄰接表中查找Vj的直接后繼Vk，把Vk的入度減1；若Vk的入度為0則進(jìn)棧重復(fù)上述操作直至?？諡橹埂Ｈ魲？諘r輸出的頂點(diǎn)個數(shù)不是n，則有向圖有環(huán)；否則，拓?fù)渑判蛲戤?.5拓?fù)渑判蛩惴▽?shí)現(xiàn)554325240122inlink^^^vexnext3^^0123456^7.5拓?fù)渑判?2104例123456top16toptop算法描述入度554325240122inlink^^^v7.5拓?fù)渑判?54325240122inlink^^^vexnext3^^0123456^輸出序列：63210416toptop7.5拓?fù)渑判?54325240122i7.5拓?fù)渑判蜉敵鲂蛄校?321041topp554325240122inlink^^^vexnext3^^0123456^7.5拓?fù)渑判蜉敵鲂蛄校?321041topp557.5拓?fù)渑判?122inlink5543^^^vexnext2^25^240123456^輸出序列：6321041topp7.5拓?fù)渑判?122inlink5543^^^7.5拓?fù)渑判?122inlink5543^^^vexnext2^25^240123456^輸出序列：6321041topp7.5拓?fù)渑判?122inlink5543^^^7.5拓?fù)渑判?112inlink5543^^^vexnext2^25^240123456^輸出序列：6321041topp7.5拓?fù)渑判?112inlink5543^^^7.5拓?fù)渑判?112inlink5543^^^vexnext2^25^240123456^輸出序列：6321041topp=NULL7.5拓?fù)渑判?112inlink5543^^^7.5拓?fù)渑判?112inlink5543^^^vexnext2^25^240123456^輸出序列：61321041toptop7.5拓?fù)渑判?112inlink5543^^^7.5拓?fù)渑判?112inlink5543^^^vexnext2^25^240123456^輸出序列：6132104topp7.5拓?fù)渑判?112inlink5543^^^7.5拓?fù)渑判?102inlink5543^^^vexnext2^25^240123456^輸出序列：6132104topp47.5拓?fù)渑判?102inlink5543^^^7.5拓?fù)渑判?102inlink5543^^^vexnext2^25^240123456^輸出序列：6132104p4top7.5拓?fù)渑判?102inlink5543^^^7.5拓?fù)渑判?102inlink5543^^^vexnext2^25^240123456^輸出序列：6132104p4top7.5拓?fù)渑判?102inlink5543^^^7.5拓?fù)渑判?002inlink5543^^^vexnext2^25^240123456^輸出序列：6132104p4top37.5拓?fù)渑判?002inlink5543^^^7.5拓?fù)渑判?002inlink5543^^^vexnext2^25^240123456^輸出序列：6132104p4top37.5拓?fù)渑判?002inlink5543^^^7.5拓?fù)渑判?002inlink5543^^^vexnext2^25^240123456^輸出序列：6132104p4top37.5拓?fù)渑判?002inlink5543^^^7.5拓?fù)渑判?001inlink5543^^^vexnext2^25^240123456^輸出序列：6132104p4top37.5拓?fù)渑判?001inlink5543^^^7.5拓?fù)渑判?001inlink5543^^^vexnext2^25^240123456^輸出序列：6132104p=NULL4top37.5拓?fù)渑判?001inlink5543^^^7.5拓?fù)渑判?001inlink5543^^^vexnext2^25^240123456^輸出序列：613321044top37.5拓?fù)渑判?001inlink5543^^^7.5拓?fù)渑判?001inlink5543^^^vexnext2^25^240123456^輸出序列：613321044topp7.5拓?fù)渑判?001inlink5543^^^7.5拓?fù)渑判?001inlink5543^^^vexnext1^25^240123456^輸出序列：613321044topp7.5拓?fù)渑判?001inlink5543^^^7.5拓?fù)渑判?001inlink5543^^^vexnext1^25^240123456^輸出序列：613321044topp7.5拓?fù)渑判?001inlink5543^^^7.5拓?fù)渑判?000inlink5543^^^vexnext1^25^240123456^輸出序列：613321044topp27.5拓?fù)渑判?000inlink5543^^^7.5拓?fù)渑判?000inlink5543^^^vexnext1^25^240123456^輸出序列：613321044topp27.5拓?fù)渑判?000inlink5543^^^7.5拓?fù)渑判?000inlink5543^^^vexnext1^25^240123456^輸出序列：613321044top2p=NULL7.5拓?fù)渑判?000inlink5543^^^7.5拓?fù)渑判?000inlink5543^^^vexnext1^25^240123456^輸出序列：6132321044top2p=NULL7.5拓?fù)渑判?000inlink5543^^^7.5拓?fù)渑判?000inlink5543^^^vexnext1^25^240123456^輸出序列：6132321044topp=NULL7.5拓?fù)渑判?000inlink5543^^^7.5拓?fù)渑判?000inlink5543^^^vexnext1^25^240123456^輸出序列：61324321044top7.5拓?fù)渑判?000inlink5543^^^7.5拓?fù)渑判?000inlink5543^^^vexnext1^25^240123456^輸出序列：6132432104topp7.5拓?fù)渑判?000inlink5543^^^7.5拓?fù)渑判?000inlink5543^^^vexnext0^25^240123456^輸出序列：6132432104topp57.5拓?fù)渑判?000inlink5543^^^7.5拓?fù)渑判?000inlink5543^^^vexnext0^25^240123456^輸出序列：6132432104topp=NULL57.5拓?fù)渑判?000inlink5543^^^7.5拓?fù)渑判?000inlink5543^^^vexnext0^25^240123456^輸出序列：61324532104top57.5拓?fù)渑判?000inlink5543^^^7.5拓?fù)渑判?000inlink5543^^^vexnext0^25^240123456^輸出序列：61324532104topp=NULL7.5拓?fù)渑判?000inlink5543^^^7.5拓?fù)渑判蛩惴ǚ治鼋ㄠ徑颖恚篢(n)=O(e)搜索入度為0的頂點(diǎn)的時間：T(n)=O(n)拓?fù)渑判颍篢(n)=O(n+e)7.5拓?fù)渑判蛩惴ǚ治鼋ㄠ徑颖恚篢(n)=O(e)7.5拓?fù)渑判騿栴}提出

假設(shè)以有向網(wǎng)表示一個施工流圖，弧上的權(quán)值表示完成該項(xiàng)子工程所需時間。問題：（1）完成整項(xiàng)工程至少需要多少時間？（2）哪些活動是影響工程進(jìn)度的關(guān)鍵？1956年，美國杜邦公司提出關(guān)鍵路徑法，并于1957年首先用于1000萬美元進(jìn)行化工廠建設(shè)，工期比原計(jì)劃縮短了4個月。杜邦公司在采用關(guān)鍵路徑法的一年中，節(jié)省了100萬美元。例如：有一個工程有11項(xiàng)活動，9個事件(v1--v9)v1--表示整個工程開始v9--表示整個工程結(jié)束v9v8v7v6v4v5v3v2v1a1=6a2=4a3=5a4=1a5=1a6=2a7=8a8=7a9=4a10=2a11=47.5拓?fù)渑判騿栴}提出假設(shè)以有向網(wǎng)表示一7.5拓?fù)渑判蚨xAOE網(wǎng)(ActivityOnEdge)——即邊表示活動的網(wǎng)。AOE網(wǎng)是一個帶權(quán)的有向無環(huán)圖，其中頂點(diǎn)表示事件，弧表示活動，權(quán)表示活動持續(xù)時間路徑長度——路徑上各活動持續(xù)時間之和關(guān)鍵路徑——路徑長度最長的路徑Ve(j)——表示事件Vj的最早發(fā)生時間Vl(j)——表示事件Vj的最遲發(fā)生時間e(i)——表示活動ai的最早開始時間l(i)——表示活動ai的最遲開始時間l(i)-e(i)——表示完成活動ai的時間余量關(guān)鍵活動——關(guān)鍵路徑上的活動，即l(i)=e(i)的活動7.5拓?fù)渑判蚨x7.5拓?fù)渑判蛘麄€工程完成的時間為：從有向圖的源點(diǎn)到匯點(diǎn)的最長路徑。12345678964521187244例如:“關(guān)鍵活動”指的是：該弧上的權(quán)值增加

將使有向圖上的最長路徑的長度增加。源點(diǎn)匯點(diǎn)61747.5拓?fù)渑判蛘麄€工程完成的時間為：從有向圖的源點(diǎn)到匯點(diǎn)7.5拓?fù)渑判?/p>

如何求關(guān)鍵活動？該活動的最早開始時間=該活動的最遲開始時間ijdut問題分析持續(xù)時間7.5拓?fù)渑判蛉绾吻箨P(guān)鍵活動？該活動的最早開始時間ij7.5拓?fù)渑判颉笆录?頂點(diǎn))”的最早發(fā)生時間ve(j)ve(j)=從源點(diǎn)到頂點(diǎn)j的最長路徑長度;“事件(頂點(diǎn))”的最遲發(fā)生時間vl(k)vl(k)=從頂點(diǎn)k到匯點(diǎn)的最短路徑長度;7.5拓?fù)渑判颉笆录?頂點(diǎn))”的最早發(fā)生時間ve(7.5拓?fù)渑判?/p>

假設(shè)第i條弧為<j,k>則對第i項(xiàng)活動言“活動(弧)”的最早開始時間ee(i)ee(i)=ve(j);“活動(弧)”的最遲開始時間el(i)el(i)=vl(k)–dut(<j,k>);7.5拓?fù)渑判蚣僭O(shè)第i條弧為<j,k>7.5拓?fù)渑判?/p>

事件發(fā)生時間的計(jì)算公式:ve(源點(diǎn))=0;ve(k)=Max{ve(j)+dut(<j,k>)}vl(匯點(diǎn))=ve(匯點(diǎn));vl(j)=Min{vl(k)–dut(<j,k>)}7.5拓?fù)渑判蚴录l(fā)生時間的計(jì)算公式:7.5拓?fù)渑判?2345678964521187244拓?fù)溆行蛐蛄?1-4-6-3-2-5-8-7-9000000000645711571514181818181818181818181614866108077.5拓?fù)渑判?2345678964521187244拓7.5拓?fù)渑判?6457715141818141610786600006457771514141602366887107.5拓?fù)渑判?645771514181814161077.5拓?fù)渑判蚯箨P(guān)鍵路徑步驟求Ve(i)求Vl(j)求e(i)求l(i)計(jì)算l(i)-e(i)0645771514181814161078660123456789645211872447.5拓?fù)渑判蚯箨P(guān)鍵路徑步驟064577151418187.5拓?fù)渑判蛩惴▽?shí)現(xiàn)以鄰接表作存儲結(jié)構(gòu)從源點(diǎn)V1出發(fā)，令Ve[1]=0,按拓?fù)湫蛄星蟾黜旤c(diǎn)的Ve[i]從匯點(diǎn)Vn出發(fā)，令Vl[n]=Ve[n],按逆拓?fù)湫蛄星笃溆喔黜旤c(diǎn)的Vl[i]根據(jù)各頂點(diǎn)的Ve和Vl值，計(jì)算每條弧的e[i]和l[i],找出e[i]=l[i]的關(guān)鍵活動要點(diǎn)：顯然，求ve的順序應(yīng)該是按拓?fù)溆行虻拇涡?而求vl的順序應(yīng)該是按拓?fù)淠嫘虻拇涡?因?yàn)橥負(fù)淠嫘蛐蛄屑礊橥負(fù)溆行蛐蛄械哪嫘蛄?，因此?yīng)該在拓?fù)渑判虻倪^程中，另設(shè)一個“棧”記下拓?fù)溆行蛐蛄小?.5拓?fù)渑判蛩惴▽?shí)現(xiàn)要點(diǎn)：顯然，求ve的順序應(yīng)該是按拓7.5拓?fù)渑判蛩惴枋鲚斎腠旤c(diǎn)和弧信息，建立其鄰接表計(jì)算每個頂點(diǎn)的入度對其進(jìn)行拓?fù)渑判蚺判蜻^程中求頂點(diǎn)的Ve[i]將得到的拓?fù)湫蛄羞M(jìn)棧按逆拓?fù)湫蛄星箜旤c(diǎn)的Vl[i]計(jì)算每條弧的e[i]和l[i],找出e[i]=l[i]的關(guān)鍵活動改寫算法7.127.5拓?fù)渑判蛩惴枋龈膶懰惴?.127.6最短路徑

每一對頂點(diǎn)之間的最短路徑從某個源點(diǎn)到其余各點(diǎn)的最短路徑7.6最短路徑每一對頂點(diǎn)從某個源點(diǎn)到7.6最短路徑問題提出用帶權(quán)的有向圖表示一個交通運(yùn)輸網(wǎng)圖中：頂點(diǎn)——表示城市邊——表示城市間的交通聯(lián)系權(quán)——表示此線路的長度或沿此線路運(yùn)輸所花的時間或費(fèi)用等問題：從某頂點(diǎn)出發(fā)，沿圖的邊到達(dá)另一頂點(diǎn)所經(jīng)過的路徑中，各邊上權(quán)值之和最小的一條路徑——最短路徑7.6最短路徑問題提出用帶權(quán)的有向圖表示一個交7.6最短路徑從某個源點(diǎn)到其余各頂點(diǎn)的最短路徑24158639735104afedbcg2最短路徑長度<a,d,g,b>22<a,c>8<a,d>15<a,c,f,e>13<a,c,f>11<a,g>197.6最短路徑從某個源點(diǎn)到其余各頂點(diǎn)的最短路徑24157.6最短路徑求從源點(diǎn)到其余各點(diǎn)的最短路徑的算法的基本思想:依最短路徑的長度遞增的次序求得各條路徑源點(diǎn)v1…其中，從源點(diǎn)到頂點(diǎn)v1的最短路徑是所有最短路徑中長度最短者。v27.6最短路徑求從源點(diǎn)到其余各點(diǎn)的最短路徑的7.6最短路徑在這條路徑上，必定只含一條弧，并且