圖是一種比線性表和樹更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)解讀課件

2019年6月30感謝你的觀看1第七章圖圖是一種比線性表和樹更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。在圖中，元素間的關(guān)系是多對多的，即任何兩個元素都有可能存在關(guān)系。圖的應(yīng)用非常廣泛，已滲入到諸如語言學(xué)、邏輯學(xué)、物理、化學(xué)、電訊工程、計(jì)算機(jī)科學(xué)以及數(shù)學(xué)的其它分支中(日常生活中的交通圖等)。在離散數(shù)學(xué)中，圖論是專門研究圖的性質(zhì)的數(shù)學(xué)分支。在數(shù)據(jù)結(jié)構(gòu)中對圖的討論主要側(cè)重于圖在計(jì)算機(jī)中的存儲方式和有關(guān)操作的算法。2019年6月30感謝你的觀看1第七章圖圖是一種比線性表和2019年6月30感謝你的觀看2

圖的基本內(nèi)容7.1圖的定義和術(shù)語7.2圖的存儲結(jié)構(gòu)7.3圖的遍歷7.4圖的連通性問題7.5有向無環(huán)圖及其應(yīng)用7.6最短路徑2019年6月30感謝你的觀看2圖的基本內(nèi)容7.1圖2019年6月30感謝你的觀看37.1圖的定義和術(shù)語抽象數(shù)據(jù)類型圖的定義：

ADTGraph{

數(shù)據(jù)對象V:V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點(diǎn)集。數(shù)據(jù)關(guān)系R:R={VR}VR={<v,w>|v,wV且P(v,w),<v,w>表示從v到w的弧，謂詞

P(v,w)定義了弧<v,w>的意義或信息}

基本操作P:CreateGraph,DestroyGraph,LocateVex,GetVex,PutVex,FirstAdjVex,NextAdjVex,InsertVex,DeleteVex,InsertArc,DeleteArc,DFSTraverse,BFSTraverse}ADTGraph2019年6月30感謝你的觀看37.1圖的定義和術(shù)語抽象數(shù)2019年6月30感謝你的觀看4圖的定義(續(xù))圖中的數(shù)據(jù)元素稱為頂點(diǎn)(vertex),V是頂點(diǎn)的有窮非空集合；VR是V上頂點(diǎn)的序偶或無序?qū)Φ募?。?lt;v,w>VR，則<v,w>表示從v到w的一條弧(Arc),且稱v為弧尾(Tail)或初始點(diǎn)(Initialnode),稱w為弧頭(Head)或終端點(diǎn)(Terminalnode),此時(shí)的圖稱為有向圖(Digraph)。若<v,w>VR必有<w,v>VR，即VR是對稱的，則以無序?qū)?v,w)代替兩個有序?qū)Γ硎緑和w之間的一條邊(Edge),此時(shí)的圖稱為無向圖(Undigraph)。可以說圖由非空頂點(diǎn)集和邊集所組成。2019年6月30感謝你的觀看4圖的定義(續(xù))圖中的數(shù)據(jù)元2019年6月30感謝你的觀看5

圖的示例無向圖G1有向圖G2圖的二元組表示參見教材P1572019年6月30感謝你的觀看5圖的示例無向圖G1有向圖2019年6月30感謝你的觀看6圖的基本術(shù)語完全圖、稠密圖、稀疏圖約定：用n表示圖中頂點(diǎn)的數(shù)目，用e表示邊或弧的數(shù)目若無向圖中的每兩個頂點(diǎn)之間都存在著一條邊，有向圖中的每兩個頂點(diǎn)之間都存在著方向相反的兩條邊，則稱此圖為完全圖。當(dāng)一個圖接近完全圖時(shí)，稱為稠密圖。當(dāng)一個圖含有較少的邊或弧(e<nlogn)時(shí)，稱為稀疏圖。2019年6月30感謝你的觀看6圖的基本術(shù)語完全圖、稠密圖、2019年6月30感謝你的觀看7圖的基本術(shù)語(續(xù))權(quán)和網(wǎng)：在一個圖中，每條邊可以標(biāo)上具有某種含義的數(shù)值，此數(shù)值稱為該邊的權(quán)。邊上帶有權(quán)的圖稱為網(wǎng)。子圖：設(shè)有兩個圖G=(V,{E})和G’=(V’,{E’}),如果V’V，E’E，則稱G’是G的子圖。端點(diǎn)和鄰接點(diǎn)：在一個無向圖中，若(v,v’)E,則稱v,v’為此邊的兩個端點(diǎn)，v,v’互為鄰接點(diǎn)。頂點(diǎn)的度、入度、出度：無向圖中頂點(diǎn)v的度定義為和v相關(guān)聯(lián)的邊的數(shù)目，記為TD(v)。有向圖中，頂點(diǎn)v的入度是該頂點(diǎn)入邊的數(shù)目，記為ID(v)，出度是該頂點(diǎn)出邊的數(shù)目，記為OD(v)。顯然TD(v)=ID(v)+OD(v)。一般地，e=TD(vi)/2。2019年6月30感謝你的觀看7圖的基本術(shù)語(續(xù))權(quán)和網(wǎng)：在2019年6月30感謝你的觀看8圖的基本術(shù)語(續(xù))路徑和回路：在一個圖中，從頂點(diǎn)v到頂點(diǎn)v’的一條路徑是一個頂點(diǎn)序列。路徑長度是路徑上邊或弧的數(shù)目。第一個頂點(diǎn)和最后一個頂點(diǎn)相同的路徑稱為回路或或環(huán)。序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑稱為簡單路徑。除了第一個頂點(diǎn)和最后一個頂點(diǎn)之外，其余頂點(diǎn)不重復(fù)出現(xiàn)的回路，稱為簡單回路或簡單環(huán)。連通圖和連通分量：在無向圖G中，若兩個頂點(diǎn)v和v’之間有路徑存在，則稱v和v’是連通的。若G中任意兩個頂點(diǎn)都是連通的，則稱G為連通圖，否則稱為非連通圖。非連通圖的極大連通子圖叫做連通分量。例子見P159。2019年6月30感謝你的觀看8圖的基本術(shù)語(續(xù))路徑和回路2019年6月30感謝你的觀看9圖的基本術(shù)語(續(xù))強(qiáng)連通圖與強(qiáng)連通分量：在有向圖中,若對于每一對頂點(diǎn)v和v’,都存在一條從v到v’和從v’到v的路徑,則稱此圖是強(qiáng)連通圖。非強(qiáng)連通圖的極大強(qiáng)連通子圖叫做強(qiáng)連通分量。例子見P159。生成樹：一個連通圖的生成樹是一個極小連通子圖，它含有圖中全部頂點(diǎn)，但只有足以構(gòu)成一棵樹的n-1條邊。如果一個有向圖恰有一個頂點(diǎn)的入度為0，其余頂點(diǎn)的入度為1，則是一棵有向樹。一個有向圖的生成森林是由若干棵有向樹組成，含有圖中全部頂點(diǎn)，但只有足以構(gòu)成若干棵不相交的有向樹的弧。例子見P159-160。2019年6月30感謝你的觀看9圖的基本術(shù)語(續(xù))強(qiáng)連通圖與2019年6月30感謝你的觀看107.2圖的存儲結(jié)構(gòu)圖的存儲結(jié)構(gòu)又稱圖的存儲表示或圖的表示。它有多種方法，主要介紹鄰接矩陣、鄰接表，簡要介紹鄰接多重表和十字鏈表。鄰接矩陣：表示頂點(diǎn)之間相鄰關(guān)系的矩陣。所謂兩頂點(diǎn)的相鄰關(guān)系即它們之間有邊相連。鄰接矩陣是一個（n×n）階方陣，n為圖的頂點(diǎn)數(shù)，它的每一行分別對應(yīng)圖的各個頂點(diǎn)，它的每一列也分別對應(yīng)圖的各個頂點(diǎn)。我們規(guī)定矩陣的元素為：2019年6月30感謝你的觀看107.2圖的存儲結(jié)構(gòu)圖的存2019年6月30感謝你的觀看11

無向圖的鄰接矩陣2019年6月30感謝你的觀看11無向圖的鄰接矩陣2019年6月30感謝你的觀看12

有向圖的鄰接矩陣2019年6月30感謝你的觀看12有向圖的鄰接矩陣2019年6月30感謝你的觀看13無向圖的鄰接矩陣是對稱的，如果A[i，j]=1，必有A[j，i]=1。這說明，只輸入和存儲其上三角陣元素即可得到整個鄰接矩陣。一般有向圖的鄰接矩陣是不對稱的，A[i，j]不一定等于A[j，i]。鄰接矩陣用二維數(shù)組即可存儲，定義如下：

intadjmatrix=ARRAY[n][n];如果圖的各邊是帶權(quán)的，只需將矩陣中的各個1元素?fù)Q成相應(yīng)邊的權(quán)即可。

鄰接矩陣的若干說明2019年6月30感謝你的觀看13無向圖的鄰接矩陣是對稱的，2019年6月30感謝你的觀看14產(chǎn)生無向圖鄰接矩陣算法voidcreatgraph(intadjarray[][]){inti,j,v1,v2,num;scanf(“%d”,&num);/*輸入頂點(diǎn)數(shù)*/if(num>0){for(i=1;i<=num;i++)for(j=1;j<=num;j++)adjarry[i][j]=0;/*矩陣初始化*/do{2019年6月30感謝你的觀看14產(chǎn)生無向圖鄰接矩陣算法vo2019年6月30感謝你的觀看15

產(chǎn)生無向圖鄰接矩陣算法續(xù)

scanf(“%d,%d”,&v1,&v2);/*輸入邊*/adjarray[v1][v2]=1;adjarray[v2][v1]=1;}while(v1!=0&&v2!=0);}elsenum=0;retrunnum;}2019年6月30感謝你的觀看15產(chǎn)生無向圖鄰接矩陣算法續(xù)2019年6月30感謝你的觀看16

鄰接表鄰接表是圖的一種鏈?zhǔn)酱鎯Y(jié)構(gòu)。在鄰接表結(jié)構(gòu)中，對圖中每個頂點(diǎn)建立一個單鏈表，第i個單鏈表中的結(jié)點(diǎn)表示依附于該頂點(diǎn)Vi的邊，即對于無向圖每個結(jié)點(diǎn)表示與該頂點(diǎn)相鄰接的一個頂點(diǎn)；對于有向圖則表示以該頂點(diǎn)為起點(diǎn)的一條邊的終點(diǎn)。一個圖的鄰接矩陣表示是唯一的，但其鄰接表表示是不唯一的。因?yàn)樵卩徑颖淼拿總€單鏈表中，各結(jié)點(diǎn)的順序是任意的。2019年6月30感謝你的觀看16鄰接表鄰接表是圖的一種2019年6月30感謝你的觀看17無向圖、有向圖

2019年6月30感謝你的觀看17無向圖、有向圖2019年6月30感謝你的觀看18無向圖的鄰接表

2019年6月30感謝你的觀看18無向圖的鄰接表2019年6月30感謝你的觀看19

有向圖的鄰接表2019年6月30感謝你的觀看19有向圖的鄰接表2019年6月30感謝你的觀看20鄰接表中每個表結(jié)點(diǎn)均由兩個域組成，其一是鄰接點(diǎn)域（adjvex），用以存放與頂點(diǎn)Vi相鄰接的頂點(diǎn)在圖中的位置；其二是鏈域（next），用以指向依附于頂點(diǎn)Vi的下一條邊所對應(yīng)的結(jié)點(diǎn)。如果用鄰接表存放網(wǎng)絡(luò)中的信息，則還需要在結(jié)點(diǎn)中增加一個存放權(quán)值的域。在每個鏈表設(shè)一表頭結(jié)點(diǎn)，一般這些表頭結(jié)點(diǎn)本身以向量的形式存儲。鄰接表的若干說明2019年6月30感謝你的觀看20鄰接表中每個表結(jié)點(diǎn)均由兩個2019年6月30感謝你的觀看21對于無向圖的鄰接表來說，一條邊對應(yīng)兩個單鏈表結(jié)點(diǎn)，鄰接表結(jié)點(diǎn)總數(shù)是邊數(shù)的2倍。在無向圖的鄰接表中，各頂點(diǎn)對應(yīng)的單鏈表的結(jié)點(diǎn)數(shù)（不算表頭結(jié)點(diǎn)）就等于該頂點(diǎn)的度數(shù)。在有向圖鄰接表中，一條弧對應(yīng)一個表結(jié)點(diǎn)，表結(jié)點(diǎn)的數(shù)目和弧的數(shù)目相同。在有向圖鄰接表中，單鏈表的結(jié)點(diǎn)數(shù)就等于相應(yīng)頂點(diǎn)的出度數(shù)。要求有向圖中某頂點(diǎn)的入度數(shù)，需掃視鄰接表的所有單鏈表，統(tǒng)計(jì)與頂點(diǎn)標(biāo)號相應(yīng)的結(jié)點(diǎn)個數(shù)。鄰接表的若干說明2019年6月30感謝你的觀看21對于無向圖的鄰接表來說，一2019年6月30感謝你的觀看22鄰接表存儲結(jié)構(gòu)定義#defineMAXVEX30structedgenode{intadjvex;/*鄰接點(diǎn)域*/structedgenode*next;/*鏈域*/};structvexnode{chardata;/*頂點(diǎn)信息*/structedgenode*link;};typedefstructvexnodeadjlist[MAXVEX];2019年6月30感謝你的觀看22鄰接表存儲結(jié)構(gòu)定義#def2019年6月30感謝你的觀看23生成無向圖的鄰接表算法voidcreategraph(adjlistg){inte,i,s,d,n;structedgenode*p;printf(“請輸入結(jié)點(diǎn)數(shù)(n)和邊數(shù)(e):\n”);scanf(“%d,%d”,&n,&e);for(i=1;i<=n;i++){printf(“\n請輸入第%d個頂點(diǎn)信息：”,i);scanf(“%c”,&g[i].data);g[i].link=NULL;}for(i=1;i<=e;i++)

2019年6月30感謝你的觀看23生成無向圖的鄰接表算法vo2019年6月30感謝你的觀看24生成無向圖的鄰接表算法續(xù)

{printf(“\n請輸入第%d條邊起點(diǎn)序號，終點(diǎn)序號：”,i);scanf(“%d,%d”,&s,&d);p=(structedgenode*)malloc(sizeof(edgenode));p→adjvex=d;/*鄰接點(diǎn)序號為d*/

p→next=g[s].link;

g[s].link=p;

/*將新結(jié)點(diǎn)插入頂點(diǎn)Vs邊表的頭部*/p=(structedgenode*)malloc(sizeof(edgenode));p→adjvex=s;/*鄰接點(diǎn)序號為s*/p→next=g[d].link;g[d].link=p;/*將新結(jié)點(diǎn)插入頂點(diǎn)Vd邊表的頭部*/}}2019年6月30感謝你的觀看24生成無向圖的鄰接表算法續(xù)2019年6月30感謝你的觀看25十字鏈表和鄰接多重表簡介十字鏈表是將有向圖的鄰接表和逆鄰接表結(jié)合起來得到的一種鏈表。鄰接多重表是無向圖的另一種鏈?zhǔn)酱鎯Y(jié)構(gòu)。在鄰接多重表中，每一條邊用一個結(jié)點(diǎn)表示，它由五個域組成；每一個頂點(diǎn)也用一個結(jié)點(diǎn)表示，它由兩個域組成。2019年6月30感謝你的觀看25十字鏈表和鄰接多重表簡介十2019年6月30感謝你的觀看26

思考題1.已知如下圖所示的有向圖，請給出該圖的（1）每個頂點(diǎn)的入/出度；（2）鄰接矩陣；（3）鄰接表。1562432019年6月30感謝你的觀看26思考題1.已知如下圖所示2019年6月30感謝你的觀看277.3圖的遍歷從圖中某一頂點(diǎn)出發(fā)訪遍圖中其余結(jié)點(diǎn)，且使每一個頂點(diǎn)僅被訪問一次，這一過程稱為圖的遍歷(TraversingGraph).圖的遍歷算法是求解圖的連通性、拓?fù)渑判蚝颓箨P(guān)鍵路徑等算法的基礎(chǔ)。為了避免同一頂點(diǎn)被訪問多次，在遍歷圖的過程中，必須記下每個已訪問過的頂點(diǎn)。圖的遍歷有兩種：深度優(yōu)先搜索和廣度優(yōu)先搜索。2019年6月30感謝你的觀看277.3圖的遍歷從圖中某一2019年6月30感謝你的觀看28

深度優(yōu)先搜索(DFS)類似于樹的先根遍歷，是樹的先根遍歷的推廣。首先訪問圖中某指定起始點(diǎn)Vi

，然后由Vi出發(fā)訪問它的任一相鄰接頂點(diǎn)Vj,再從Vj出發(fā)訪問Vj的任一未訪問過的相鄰接頂點(diǎn)Vk,再從Vk出發(fā)進(jìn)行類似訪問，如此進(jìn)行下去，直到某頂點(diǎn)已沒有未被訪問過的相鄰接頂點(diǎn)時(shí)，則退回一步，退到前一個頂點(diǎn)，找前一個頂點(diǎn)的其它尚未被訪問的相鄰接頂點(diǎn)。如有未訪問過的相鄰接頂點(diǎn)，則訪問此頂點(diǎn)后，再從該頂點(diǎn)出發(fā)向前進(jìn)行與前述類似的訪問；如退回一步后，前一頂點(diǎn)也沒有未被訪問過的相鄰接頂點(diǎn)，則再向回退一步進(jìn)行搜索，重復(fù)上述過程，一直到所有頂點(diǎn)均被訪問過為止。

2019年6月30感謝你的觀看28深度優(yōu)先搜索(DFS)2019年6月30感謝你的觀看29

圖的深度優(yōu)先遍歷例子深度優(yōu)先遍歷序列：124853672019年6月30感謝你的觀看29圖的深度優(yōu)先遍歷例子深2019年6月30感謝你的觀看30由于圖中的路徑可能有環(huán)路，為了避免重復(fù)訪問某些頂點(diǎn)，設(shè)計(jì)圖的搜索算法時(shí)，可設(shè)置一個表示頂點(diǎn)是否被訪問過的輔助數(shù)組visited，初始時(shí)將數(shù)組元素置零，一旦某頂點(diǎn)Vi被訪問過，則令visited[Vi]=1，以后此頂點(diǎn)即不再訪問。

深度優(yōu)先搜索算法2019年6月30感謝你的觀看30由于圖中的路徑可能有環(huán)路，2019年6月30感謝你的觀看31

深度優(yōu)先搜索算法深度優(yōu)先搜索是一種遞歸的過程，可以簡單地將其表示成遞歸的形式，其算法描述如下：

DFS(V0){

訪問V0頂點(diǎn);visited[V0]=1;

對所有與V0相鄰接的頂點(diǎn)wif(visited[w]==0)DFS(w);}2019年6月30感謝你的觀看31深度優(yōu)先搜索算法深度優(yōu)2019年6月30感謝你的觀看32鄰接表表示的圖的DFS算法

intvisited[MAXVEX];voiddfsgraph(adjlistadj,intn){inti;for(i=1;i<=n;i++)visited[i]=0;/*給visited數(shù)組賦初值*/for(i=1;i<=n;i++)if(!visited[i])dfs(adj,i);}2019年6月30感謝你的觀看32鄰接表表示的圖的DFS算法2019年6月30感謝你的觀看33鄰接表存儲結(jié)構(gòu)定義#defineMAXVEX30structedgenode{intadjvex;/*鄰接點(diǎn)域*/structedgenode*next;/*鏈域*/};structvexnode{chardata;/*頂點(diǎn)信息*/structedgenode*link;};typedefstructvexnodeadjlist[MAXVEX];2019年6月30感謝你的觀看33鄰接表存儲結(jié)構(gòu)定義#def2019年6月30感謝你的觀看34從Vi出發(fā)進(jìn)行DFS的遞歸算法voiddfs(adjlistadj,intv){structedgenode*p;visited[v]=1;printf(“%d”,v);p=adj[v]→link;while(p!=NULL){if(visited[p→adjvex]==0)dfs(adjlist,p→adjvex);/*從v未訪問的鄰接點(diǎn)出發(fā)進(jìn)行DFS*/p=p→next;}}2019年6月30感謝你的觀看34從Vi出發(fā)進(jìn)行DFS的遞歸2019年6月30感謝你的觀看35

時(shí)間復(fù)雜性分析一個有n個頂點(diǎn)、e條邊的圖，在深度優(yōu)先搜索圖的過程中，找鄰接點(diǎn)所需時(shí)間為O(e)。對輔助數(shù)組初始化時(shí)間為O(n)。因此，當(dāng)用鄰接表作為圖的存儲結(jié)構(gòu)時(shí)，深度優(yōu)先搜索圖的時(shí)間復(fù)雜性為O(e+n)。2019年6月30感謝你的觀看35時(shí)間復(fù)雜性分析一個有n2019年6月30感謝你的觀看36

非遞歸算法從頂點(diǎn)Vi出發(fā)進(jìn)行深度優(yōu)先遍歷的遞歸過程也可以寫成非遞歸的形式，此時(shí)需借助一個堆棧保存被訪問過的結(jié)點(diǎn)，以便回溯時(shí)查找已被訪問結(jié)點(diǎn)的未被訪問過的鄰接點(diǎn)。設(shè)堆棧由一個一維數(shù)組構(gòu)成，數(shù)組名為stack，棧頂指針為top,假設(shè)此數(shù)組足夠大,不必考慮溢出的可能。2019年6月30感謝你的觀看36非遞歸算法從頂點(diǎn)Vi2019年6月30感謝你的觀看37非遞歸算法#defineMAXVEX100voiddfs(adjlistg，intv,intn)/*從頂點(diǎn)v出發(fā)進(jìn)行深度優(yōu)先遍歷*/{structvexnode*stack[MAXVEX],*p;intvisited[MAXVEX],top=0;for(i=1;i<=n;i++)visited[i]=0;printf(“%d”,v);p=g[v].link;visited[v]=1;while(top>0||p!=NULL)2019年6月30感謝你的觀看37非遞歸算法#define2019年6月30感謝你的觀看38非遞歸算法續(xù){while(p!=NULL)if(visited[p->adjvex]==1)p=p->next;else{printf(“%d”,p->adjvex);visited[p->adjvex]=1;top++;stack[top]=p;p=g[p->adjvex].link;}2019年6月30感謝你的觀看38非遞歸算法續(xù){2019年6月30感謝你的觀看39非遞歸算法續(xù)

if(top>0){top--;/*退棧，回溯查找已被訪問結(jié)點(diǎn)的未被訪問過的鄰接點(diǎn)*/p=stack[top];p=p->next;}}}2019年6月30感謝你的觀看39非遞歸算法續(xù)2019年6月30感謝你的觀看40

廣度優(yōu)先搜索(BFS)圖的廣度優(yōu)先搜索（BFS）類似于樹的按層次遍歷。廣度優(yōu)先搜索的基本思想是：首先訪問圖中某指定的起始點(diǎn)Vi并將其標(biāo)記為已訪問過，然后由Vi出發(fā)訪問與它相鄰接的所有頂點(diǎn)Vj、Vk……，并均標(biāo)記為已訪問過，然后再按照Vj、Vk……的次序，訪問每一個頂點(diǎn)的所有未被訪問過的鄰接頂點(diǎn)，并均標(biāo)記為已訪問過，下一步再從這些頂點(diǎn)出發(fā)訪問與它們相鄰接的尚未被訪問的頂點(diǎn)，如此做下去，直到所有的頂點(diǎn)均被訪問過為止。2019年6月30感謝你的觀看40廣度優(yōu)先搜索(BFS2019年6月30感謝你的觀看41廣度優(yōu)先搜索(續(xù))在廣度優(yōu)先搜索中，若對頂點(diǎn)V1的訪問先于頂點(diǎn)V2的訪問，則對V1鄰接頂點(diǎn)的訪問也先于V2鄰接頂點(diǎn)的訪問。就是說廣度優(yōu)先搜索中對鄰接點(diǎn)的尋找具有“先進(jìn)先出”的特性。因此，為了保證訪問頂點(diǎn)的這種先后關(guān)系，需借助一個隊(duì)列暫存那些剛訪問過的頂點(diǎn)。設(shè)此隊(duì)列由一個一維數(shù)組構(gòu)成，數(shù)組名為Queue，隊(duì)首指針和隊(duì)尾指針分別為front和rear。假設(shè)數(shù)組足夠大，不必考慮有溢出的可能性。廣度優(yōu)先搜索不是遞歸過程，不能用遞歸形式。2019年6月30感謝你的觀看41廣度優(yōu)先搜索(續(xù))在廣度優(yōu)2019年6月30感謝你的觀看42

圖的廣度優(yōu)先遍歷例子廣度優(yōu)先遍歷序列：123456782019年6月30感謝你的觀看42圖的廣度優(yōu)先遍歷例子廣2019年6月30感謝你的觀看43

圖的遍歷舉例已知一有向圖的鄰接表存儲結(jié)構(gòu)如下頁圖所示，分別給出從頂點(diǎn)v1出發(fā)進(jìn)行深度優(yōu)先和廣度優(yōu)先遍歷所得到的頂點(diǎn)序列。2019年6月30感謝你的觀看43圖的遍歷舉例已知一有向2019年6月30感謝你的觀看44

一個有向圖的鄰接表2019年6月30感謝你的觀看44一個有向圖的鄰接表2019年6月30感謝你的觀看45例子解答解：根據(jù)有向圖的深度優(yōu)先遍歷算法，從頂點(diǎn)v1出發(fā)所得到的頂點(diǎn)序列是：

v1，v3，v4，v5，v2

根據(jù)有向圖的廣度優(yōu)先遍歷算法，從頂點(diǎn)v1出發(fā)所得到的頂點(diǎn)序列是：

v1，v3，v2，v4，v52019年6月30感謝你的觀看45例子解答解：根據(jù)有向圖的深2019年6月30感謝你的觀看46BFS算法描述BFS(v0){訪問v0頂點(diǎn)；

visited[v0]=1;

被訪問過的頂點(diǎn)入隊(duì)；當(dāng)隊(duì)列非空時(shí)，進(jìn)行下面的循環(huán)

{（1）被訪問過的頂點(diǎn)出隊(duì)；（2）對所有與該頂點(diǎn)相鄰接的頂點(diǎn)wif(visited[w]==0){(a)訪問w頂點(diǎn)；

(b)visited[w]=1;(c)w入隊(duì);}}}2019年6月30感謝你的觀看46BFS算法描述BFS(v02019年6月30感謝你的觀看47時(shí)間復(fù)雜性分析一個有n個頂點(diǎn)、e條邊的圖，在廣度優(yōu)先搜索圖的過程中，每個頂點(diǎn)至多進(jìn)一次隊(duì)列，圖的搜索過程實(shí)質(zhì)上是通過邊來找頂點(diǎn)的過程，找鄰接點(diǎn)所需時(shí)間為O(e)。對輔助數(shù)組初始化時(shí)間為O(n)。因此，當(dāng)用鄰接表作為圖的存儲結(jié)構(gòu)時(shí)，廣度優(yōu)先搜索圖的時(shí)間復(fù)雜性為O(e+n)。2019年6月30感謝你的觀看47時(shí)間復(fù)雜性分析一個有n個頂2019年6月30感謝你的觀看487.4圖的連通性問題

無向圖的連通分量和生成樹深度優(yōu)先搜索或廣度優(yōu)先搜索在遍歷無向圖時(shí)，若無向圖是連通圖，則從圖中任一頂點(diǎn)出發(fā)，便可訪問到圖中所有頂點(diǎn)。若無向圖是非連通圖，則需從多個頂點(diǎn)出發(fā)進(jìn)行搜索，每次調(diào)用搜索過程得到的頂點(diǎn)訪問序列恰為其各個連通分量中的頂點(diǎn)集。遍歷過程中經(jīng)過的邊的集合和圖中所有頂點(diǎn)一起構(gòu)成連通圖的極小連通子圖，為連通圖的一棵生成樹。分別有深度優(yōu)先生成樹和廣度優(yōu)先生成樹。2019年6月30感謝你的觀看487.4圖的連通性問題無2019年6月30感謝你的觀看49

生成樹的進(jìn)一步描述在一個無向連通圖G中，如果取它的全部頂點(diǎn)和一部分邊構(gòu)成一個子圖G’，若邊集E(G’)中的邊剛好將圖的所有頂點(diǎn)連通但又不形成環(huán)路，我們就稱子圖G’是原圖G的生成樹（Spanningtree）。生成樹有如下特點(diǎn)：任意兩個頂點(diǎn)之間有且僅有一條路徑；如果再增加一條邊就會出現(xiàn)環(huán)路；如果去掉一條邊此子圖就會變成非連通圖。一個有n個頂點(diǎn)的完全圖，一共存在n(n-2)種不同的生成樹。2019年6月30感謝你的觀看49生成樹的進(jìn)一步描述在一個2019年6月30感謝你的觀看50非連通圖的生成森林對于非連通圖，每個連通分量中的頂點(diǎn)集，和遍歷時(shí)走過的邊一起構(gòu)成若干棵生成樹，這些連通分量的生成樹組成非連通圖的生成森林。生成樹和生成森林除依賴于遍歷算法外，還依賴于采用的存儲結(jié)構(gòu)。2019年6月30感謝你的觀看50非連通圖的生成森林對于非連2019年6月30感謝你的觀看51最小生成樹對于帶權(quán)的連通圖（連通網(wǎng)）G，其生成樹也是帶權(quán)的。我們把生成樹各邊的權(quán)值總和稱為該生成樹的權(quán)。并且將權(quán)最小的生成樹稱為最小生成樹（MinimumSpanningTree）。具有n個頂點(diǎn)的連通圖的生成樹具有n-1條邊（少于此邊數(shù)不可能將各頂點(diǎn)連通，多于此邊數(shù)則必然要出現(xiàn)環(huán)路）。2019年6月30感謝你的觀看51最小生成樹對于帶權(quán)的連通圖2019年6月30感謝你的觀看52

無向連通圖G及其生成樹無向連通圖G

生成樹

2019年6月30感謝你的觀看52無向連通圖G及其生成2019年6月30感謝你的觀看53

圖G的其它生成樹生成樹最小生成樹2019年6月30感謝你的觀看53圖G的其它生成樹生成樹最2019年6月30感謝你的觀看54

普里姆(prim)算法描述假設(shè)G=(V,E)是一個具有n個頂點(diǎn)的連通網(wǎng)絡(luò)，T=(U,TE)是G的最小生成樹，其中U是T的頂點(diǎn)集，TE是T的邊集，U和TE的初值均為空。算法開始時(shí)，首先從V中任取一個頂點(diǎn)（假定為V1），將此頂點(diǎn)并入U(xiǎn)中，此時(shí)最小生成樹頂點(diǎn)集U={V1}；然后從那些其一個端點(diǎn)已在U中，另一個端點(diǎn)仍在U外的所有邊中，找一條最短（即權(quán)值最?。┑倪?，假定該邊為(Vi,Vj),其中Vi∈U，Vj∈V-U,并把該邊(Vi,Vj)和頂點(diǎn)Vj分別并入T的邊集TE和頂點(diǎn)集U；2019年6月30感謝你的觀看54普里姆(prim)算法描2019年6月30感謝你的觀看55普里姆(prim)算法描述續(xù)如此進(jìn)行下去，每次往生成樹里并入一個頂點(diǎn)和一條邊，直到n-1次后，把所有n個頂點(diǎn)都并入生成樹T的頂點(diǎn)集U中，此時(shí)U=V，TE中包含有（n-1）條邊；這樣，T就是最后得到的最小生成樹。普里姆算法中每次選取的邊兩端，總是一個已連通頂點(diǎn)（在U集合內(nèi)）和一個未連通頂點(diǎn)（在U集合外），故這個邊選取后一定能將未連通頂點(diǎn)連通而又保證不會形成環(huán)路。2019年6月30感謝你的觀看55普里姆(prim)算法描述2019年6月30感謝你的觀看56普里姆算法例子2019年6月30感謝你的觀看56普里姆算法例子2019年6月30感謝你的觀看57普里姆算法為了便于在頂點(diǎn)集合U和V-U之間選擇權(quán)最小的邊，建立兩個數(shù)組closest和lowcost,closest[i]表示U中的一個頂點(diǎn)，該頂點(diǎn)與V-U中的一個頂點(diǎn)構(gòu)成的邊具有最小的權(quán)；lowcost表示該邊對應(yīng)的權(quán)值。開始，由于U的初值為{1}，所以，closest[i]的值為1，i=2,…n,而lowcost[i]為V1到各頂點(diǎn)的邊中最小的權(quán)值。2019年6月30感謝你的觀看57普里姆算法為了便于在頂點(diǎn)集2019年6月30感謝你的觀看58算法分析該算法中每一步執(zhí)行都要掃描數(shù)組lowcost，在V-U頂點(diǎn)集中找出與U最近的頂點(diǎn)，令其為k，并打印邊（k,closest[k]）。然后將k加入U(xiǎn)頂點(diǎn)集合中，并修改數(shù)組lowcost和closest。這里用c表示圖的鄰接矩陣，c[i][j]和c[j][i]是邊(i,j)的權(quán)。2019年6月30感謝你的觀看58算法分析該算法中每一步執(zhí)行2019年6月30感謝你的觀看59克魯斯卡爾（Kruskal）算法假設(shè)G=（V，E）是一個具有n個頂點(diǎn)的連通網(wǎng)絡(luò)，T=(U,TE)是G的最小生成樹，U的初值等于V，即包含有G中的全部頂點(diǎn)，TE的初值為空集?；舅枷耄簩DG中的邊按權(quán)值從小到大的順序依次選取，若選取的邊使生成樹T不形成環(huán)路，則把它并入TE中，保留作為生成樹T的一條邊，若選取的邊使生成樹T形成環(huán)路，則將其舍棄，如此進(jìn)行下去，直到TE中包含n-1條邊為止。此時(shí)的T即為最小生成樹。2019年6月30感謝你的觀看59克魯斯卡爾（Kruskal2019年6月30感謝你的觀看60

克魯斯卡爾算法例子(a)帶權(quán)圖2019年6月30感謝你的觀看60克魯斯卡爾算法例子(a2019年6月30感謝你的觀看61(c)最小生成樹2019年6月30感謝你的觀看61(c)最小生成樹2019年6月30感謝你的觀看62克魯斯卡爾算法續(xù)在選取某邊時(shí)如何判斷是否與已保留的邊形成環(huán)路？克魯斯卡爾算法是通過將各頂點(diǎn)劃分為集合的辦法來解決的。開始時(shí)假定n個頂點(diǎn)分屬于n個集合,即每個集合中有一個頂點(diǎn),當(dāng)確定某條邊保留作為生成樹的一條邊時(shí),就將該邊兩端點(diǎn)所屬的兩集合合并為一個,表示原來屬于兩個集合的各個頂點(diǎn)已被這條新的邊連通.如果取到某條邊,發(fā)現(xiàn)它的兩個端點(diǎn)已屬于同一集合時(shí),此邊則應(yīng)當(dāng)舍去.因?yàn)閮蓚€頂點(diǎn)屬于同一集合說明它們已連通,若再添上這條邊就會出現(xiàn)環(huán)路。如此進(jìn)行下去，到所有的頂點(diǎn)均已屬于一個集合時(shí)，此最小生成樹就構(gòu)成了。2019年6月30感謝你的觀看62克魯斯卡爾算法續(xù)在選取某邊2019年6月30感謝你的觀看637.5有向無環(huán)圖及其應(yīng)用在工程實(shí)踐中，一個工程項(xiàng)目往往由若干個子項(xiàng)目組成，這些子項(xiàng)目間往往有多種關(guān)系：①先后關(guān)系，即必須在一子項(xiàng)目完成后，才能開始實(shí)施另一個子項(xiàng)目；②子項(xiàng)目之間無次序要求，即兩個子項(xiàng)目可以同時(shí)進(jìn)行，互不影響。在工廠中，一件設(shè)備的生產(chǎn)包括許多工序，各工序之間也存在這兩種關(guān)系。學(xué)校里某個專業(yè)的課程學(xué)習(xí)，有些課程是基礎(chǔ)課，它們可以獨(dú)立于其它課程，即無前導(dǎo)課程；有些課程必須在一些課程學(xué)完后才能開始學(xué)。2019年6月30感謝你的觀看637.5有向無環(huán)圖及其應(yīng)用2019年6月30感謝你的觀看64AOV網(wǎng)絡(luò)這些類似的問題都可以用有向圖來表示，我們把這些子項(xiàng)目、工序、課程看成一個個頂點(diǎn)稱之為活動(Activity)。如果從頂點(diǎn)Vi到Vj之間存在有向邊<Vi，Vj>,則表示活動i必須先于活動j進(jìn)行。這種圖稱做頂點(diǎn)表示活動的網(wǎng)絡(luò)(ActivityOnVertexnetwork,簡稱AOV網(wǎng)絡(luò))。例如某校計(jì)算機(jī)專業(yè)的課程及其相互之間的關(guān)系，它對應(yīng)的AOV網(wǎng)絡(luò)如下頁圖所示。2019年6月30感謝你的觀看64AOV網(wǎng)絡(luò)這些類似的問題都2019年6月30感謝你的觀看65

某專業(yè)課程設(shè)置2019年6月30感謝你的觀看65某專業(yè)課程設(shè)置2019年6月30感謝你的觀看66

課程設(shè)置的AOV網(wǎng)絡(luò)2019年6月30感謝你的觀看66課程設(shè)置的AOV網(wǎng)絡(luò)2019年6月30感謝你的觀看67

有向無環(huán)圖描述在AOV網(wǎng)絡(luò)中，如果頂點(diǎn)Vi的活動必須在頂點(diǎn)Vj的活動以前進(jìn)行，則稱Vi為Vj的前趨頂點(diǎn)，而稱Vj為Vi的后繼頂點(diǎn)。這種前趨后繼關(guān)系有傳遞性。AOV網(wǎng)絡(luò)中一定不能有有向環(huán)路。例如在下頁圖那樣的有向環(huán)路中，V2是V3的前趨頂點(diǎn)，V1是V2的前趨頂點(diǎn)，V3又是V1的前趨頂點(diǎn)，環(huán)路表示頂點(diǎn)之間的先后關(guān)系進(jìn)入了死循環(huán)。因此，對給定的AOV網(wǎng)絡(luò)首先要判定網(wǎng)絡(luò)中是否存在環(huán)路，只有有向無環(huán)路網(wǎng)絡(luò)在應(yīng)用中才有實(shí)際意義。一個無環(huán)的有向圖稱為有向無環(huán)圖，它是一類較有向樹更一般的特殊有向樹。2019年6月30感謝你的觀看67有向無環(huán)圖描述在AOV網(wǎng)2019年6月30感謝你的觀看68

有向環(huán)路舉例2019年6月30感謝你的觀看68有向環(huán)路舉例2019年6月30感謝你的觀看69拓?fù)渑判蛩^“拓?fù)渑判颉本褪菍OV網(wǎng)絡(luò)中的各個頂點(diǎn)(各個活動)排列成一個線性有序序列，使得所有要求的前趨、后繼關(guān)系都能得到滿足。由于AOV網(wǎng)絡(luò)中有些頂點(diǎn)之間沒有次序要求，它們在拓?fù)溆行蛐蛄兄械奈恢每梢匀我忸嵉?，所以拓?fù)渑判虻慕Y(jié)果一般并不是唯一的。通過拓?fù)渑判蜻€可以判斷出此AOV網(wǎng)絡(luò)是否包含有有向環(huán)路，若有向圖G所有頂點(diǎn)都在拓?fù)渑判蛐蛄兄?，則AOV網(wǎng)絡(luò)必定不包含有有向環(huán)路。2019年6月30感謝你的觀看69拓?fù)渑判蛩^“拓?fù)渑判颉本?019年6月30感謝你的觀看70拓?fù)渑判蚍椒?1)在網(wǎng)絡(luò)中選擇一個沒有前趨(入度為0)的頂點(diǎn)，并把它輸出；(2)從網(wǎng)絡(luò)中刪去該頂點(diǎn)和從該頂點(diǎn)發(fā)出的所有有向邊；(3)重復(fù)執(zhí)行上述兩步，直到網(wǎng)中所有的頂點(diǎn)都被輸出(此時(shí)，原AOV網(wǎng)絡(luò)中的所有頂點(diǎn)和邊就都被刪除掉了)。如果進(jìn)行到某一步，無法找到無前趨的頂點(diǎn)，則說明此AOV網(wǎng)絡(luò)中存在有向環(huán)路，遇到這種情況，拓?fù)渑判蚓蜔o法進(jìn)行了。2019年6月30感謝你的觀看70拓?fù)渑判蚍椒?1)在網(wǎng)絡(luò)2019年6月30感謝你的觀看71

拓?fù)渑判蜻^程AOV網(wǎng)絡(luò)

輸出V3后2019年6月30感謝你的觀看71拓?fù)渑判蜻^程AOV網(wǎng)絡(luò)2019年6月30感謝你的觀看72輸出V4后輸出V2后輸出V1后輸出V5后輸出拓?fù)湫蛄袨椋?42152019年6月30感謝你的觀看72輸出V4后輸出V2后輸出V2019年6月30感謝你的觀看73關(guān)鍵路徑法關(guān)鍵路徑法是采用邊表示活動(ActivityOnEdge)的網(wǎng)絡(luò)，簡稱為AOE網(wǎng)絡(luò)。AOE網(wǎng)絡(luò)是一個帶權(quán)的有向無環(huán)路圖，其中，每個頂點(diǎn)代表一個事件(Event)，事件說明某些活動或某一項(xiàng)活動的完成，即階段性的結(jié)果。離開某頂點(diǎn)的各條邊所代表的活動，只有在該頂點(diǎn)對應(yīng)的事件出現(xiàn)后才能開始。權(quán)值表示活動持續(xù)的時(shí)間。2019年6月30感謝你的觀看73關(guān)鍵路徑法關(guān)鍵路徑法是采用2019年6月30感謝你的觀看74一個AOE網(wǎng)絡(luò)2019年6月30感謝你的觀看74一個AOE網(wǎng)絡(luò)2019年6月30感謝你的觀看75AOE網(wǎng)絡(luò)通常利用AOE網(wǎng)絡(luò)可以研究以下兩個問題：(1)完成整個工程至少需要多少時(shí)間？(2)哪些活動是影響工程進(jìn)度的關(guān)鍵？2019年6月30感謝你的觀看75AOE網(wǎng)絡(luò)通常利用AOE網(wǎng)2019年6月30感謝你的觀看76關(guān)鍵路徑完成工程所需的時(shí)間就是從開始點(diǎn)起進(jìn)行到結(jié)束點(diǎn)止所需的時(shí)間。路徑長度是指沿路徑各邊的權(quán)值之和，也就是這些邊所代表的活動所需時(shí)間之和。完成整個工程所需的時(shí)間取決于從開始點(diǎn)到結(jié)束點(diǎn)的最長路徑長度，此長度最大的路徑叫做關(guān)鍵路徑。分析關(guān)鍵路徑的目的是辨別哪些是關(guān)鍵活動，以便爭取提高關(guān)鍵活動的效率，縮短整個工期。2019年6月30感謝你的觀看76關(guān)鍵路徑完成工程所需的時(shí)間2019年6月30感謝你的觀看77求關(guān)鍵路徑的算法描述在描述關(guān)鍵路徑的算法時(shí)，設(shè)活動ai由弧<j,k>表示，要確定如下幾個相關(guān)的量：(1)事件Vj的最早出現(xiàn)時(shí)間和活動的最早開始時(shí)間：從源點(diǎn)V1到某頂點(diǎn)Vj的最長路徑長度叫作事件j的最早出現(xiàn)時(shí)間，表示成ve[j]。頂點(diǎn)Vj的最早出現(xiàn)時(shí)間ve[j]決定了從Vj指出的各條邊所代表活動的最早開始時(shí)間，因?yàn)槭录不出現(xiàn)，它后面的各項(xiàng)活動就不能開始。我們以e[i]表示活動ai的最早開始時(shí)間。顯然e[i]=ve[j]。2019年6月30感謝你的觀看77求關(guān)鍵路徑的算法描述在描述2019年6月30感謝你的觀看78求關(guān)鍵路徑的算法描述(續(xù))(2)活動ai的最遲開始時(shí)間：在不影響整個工程按時(shí)完成的前提下，此項(xiàng)活動最遲的必須開始時(shí)間，表示成L[i]。只要某活動ai有L[i]=e[i]的關(guān)系，我們就稱ai為關(guān)鍵活動。關(guān)鍵活動只允許在一個確定的時(shí)間開始，再早，它前面的事件還沒出現(xiàn)，尚不能開始；再晚，又會延誤整個工程的按時(shí)完成。由于完成整個工程所需的時(shí)間是由關(guān)鍵路徑上各邊權(quán)值之和所決定的，顯然關(guān)鍵路徑上各條邊所對應(yīng)的活動都是關(guān)鍵活動。2019年6月30感謝你的觀看78求關(guān)鍵路徑的算法描述(續(xù))2019年6月30感謝你的觀看79求關(guān)鍵路徑的算法描述(續(xù))(3)事件j的最遲出現(xiàn)時(shí)間：即事件j在不延誤整個工程的前提下允許發(fā)生的最遲時(shí)間，表示為vl[j]。對某條指向頂點(diǎn)Vk的邊所代表的活動ai可得到：

L[i]=vl[k]-(活動ai所需時(shí)間)

也就是活動ai必須先于它后面事件的最遲出現(xiàn)時(shí)間開始，提前的時(shí)間為進(jìn)行此活動所需的時(shí)間。下圖所示為活動開始時(shí)間與事件出現(xiàn)時(shí)間的關(guān)系。VjaiVk2019年6月30感謝你的觀看79求關(guān)鍵路徑的算法描述(續(xù))2019年6月30感謝你的觀看80求關(guān)鍵路徑的算法描述(續(xù))確定關(guān)鍵路徑的方法就是要確定e[i]=L[i]的關(guān)鍵活動。假設(shè)以w[j,k]表示有向邊<j,k>的權(quán)，即此邊對應(yīng)的活動所需的時(shí)間，為了求AOE網(wǎng)絡(luò)中活動ai的最早開始時(shí)間e[i]和活動ai的最遲開始時(shí)間L[i]，先要求得頂點(diǎn)Vk的最早出現(xiàn)時(shí)間ve[k]和最遲出現(xiàn)時(shí)間vl[k]。2019年6月30感謝你的觀看80求關(guān)鍵路徑的算法描述(續(xù))2019年6月30感謝你的觀看81ve[k]和vl[k]可以采用下面的遞推公式計(jì)算：(1)向匯點(diǎn)遞推由源點(diǎn)的ve[1]=0開始，利用公式：向匯點(diǎn)的方向遞推，可逐個求出各頂點(diǎn)的ve。式中p表示所有指向頂點(diǎn)的邊的集合。2019年6月30感謝你的觀看81ve[k]和vl[k]可以2019年6月30感謝你的觀看82集合p此式的意義為：從指向頂點(diǎn)Vk的各邊的活動中取最晚完成的一個活動的完成時(shí)間作為Vk的最早出現(xiàn)時(shí)間ve[k]。

2019年6月30感謝你的觀看82集合p此式的意義為：從指向2019年6月30感謝你的觀看83(2)向源點(diǎn)遞推由上一步的遞推，最后總可求出匯點(diǎn)的最早出現(xiàn)時(shí)間ve[n]。因匯點(diǎn)就是結(jié)束點(diǎn)，最遲出現(xiàn)時(shí)間與最早出現(xiàn)時(shí)間相同，即vl[n]=ve[n]。從匯點(diǎn)的最遲出現(xiàn)時(shí)間vl[n]開始，利用下面公式：向源點(diǎn)的方向往回遞推，可逐個求出各頂點(diǎn)的最遲出現(xiàn)時(shí)間vl。式中s表示所有由Vj點(diǎn)指出的邊的集合，如下頁圖所示。2019年6月30感謝你的觀看83(2)向源點(diǎn)遞推2019年6月30感謝你的觀看84

集合s上述公式的意義為：由從Vj頂點(diǎn)指出的各邊所代表的活動中取需最早開始的一個開始時(shí)間作為Vj的最遲出現(xiàn)時(shí)間。2019年6月30感謝你的觀看84集合s上述公式的意義2019年6月30感謝你的觀看85無論是向匯點(diǎn)遞推還是向源點(diǎn)遞推，都必須按一定的頂點(diǎn)順序進(jìn)行。對所有的有向邊，向匯點(diǎn)遞推是先求出尾頂點(diǎn)的ve值，再求頭頂點(diǎn)的ve值；向源點(diǎn)遞推則相反，先求頭頂點(diǎn)的vl值，再求尾頂點(diǎn)的vl值。為此，可利用上節(jié)介紹的拓?fù)渑判虻玫降捻旤c(diǎn)次序進(jìn)行向匯點(diǎn)的遞推，向源點(diǎn)的遞推按相反的順序進(jìn)行即可，不必再重新排序。2019年6月30感謝你的觀看85無論是向匯點(diǎn)遞推還是向源點(diǎn)2019年6月30感謝你的觀看86AOE網(wǎng)絡(luò)中的關(guān)鍵活動2019年6月30感謝你的觀看86AOE網(wǎng)絡(luò)中的關(guān)鍵活動2019年6月30感謝你的觀看87求關(guān)鍵路徑的算法描述(續(xù))由表可知時(shí)間余量為零的活動都是關(guān)鍵活動，即為a1，a4，a7，a8，a10，a11。這些關(guān)鍵活動構(gòu)成兩條關(guān)鍵路徑，即關(guān)鍵路徑(V1，V2，V5，V7，V9)和(V1，V2，V5，V8，V9)。在安排工程時(shí)，對于關(guān)鍵活動和余量小的活動應(yīng)重點(diǎn)保證，余量較大的活動可適當(dāng)?shù)胤潘尚?，對非關(guān)鍵活動加速進(jìn)行，并不能使整個工程提前完成，只有提高關(guān)鍵路徑上的活動的效率，才能縮短整個工程的工期。2019年6月30感謝你的觀看87求關(guān)鍵路徑的算法描述(續(xù))2019年6月30感謝你的觀看887.6最短路徑所謂最短路徑（shortestpath）問題指的是：如果從圖中某頂點(diǎn)出發(fā)（此點(diǎn)稱為源點(diǎn)），經(jīng)圖的邊到達(dá)另一頂點(diǎn)（稱為終點(diǎn)）的路徑不止一條，如何找到一條路徑使沿此路徑上各邊的權(quán)值之和為最小。設(shè)一有向網(wǎng)絡(luò)G=（V,E），已知各邊的權(quán)值，并設(shè)每邊的權(quán)均大于零，以某指定V0為源點(diǎn)，求從V0到圖的其余各點(diǎn)的最短路徑。以下頁圖為例，若指定以頂點(diǎn)V6為源點(diǎn)V0，該圖比較簡單，通過觀察可得到從V6到其余各點(diǎn)的最短路徑。2019年6月30感謝你的觀看887.6最短路徑所謂最短路2019年6月30感謝你的觀看89

最短路徑例子2019年6月30感謝你的觀看89最短路徑例子2019年6月30感謝你的觀看90狄杰斯特拉算法狄克斯特拉于1959年提出了一個按路徑“長度”遞增的次序，逐步得到由給定源點(diǎn)到圖的其余各點(diǎn)間的最短路徑的算法。假設(shè)我們以鄰接矩陣cost表示所研究的有向圖，cost[i][j]表示有向邊<i,j>對應(yīng)權(quán)值，如果兩點(diǎn)之間無相應(yīng)方向的邊，則該元素取為無窮大。在計(jì)算機(jī)中此矩陣用一個（n×n）二維數(shù)組表示（n為圖的頂點(diǎn)數(shù)），無窮大元素則可用某很大的有限值（如32767）代替。2019年6月30感謝你的觀看90狄杰斯特拉算法狄克斯特拉于2019年6月30感謝你的觀看91

有向圖對應(yīng)的鄰接矩陣

2019年6月30感謝你的觀看91有向圖對應(yīng)的鄰接矩陣2019年6月30感謝你的觀看92狄克斯特拉算法狄克斯特拉算法需要一個頂點(diǎn)集合，初始時(shí)集合內(nèi)只有一個源點(diǎn)V0

，以后陸續(xù)將已求得最短路徑的頂點(diǎn)加入到集合中，到全部頂點(diǎn)都進(jìn)入集合了，過程就結(jié)束了。集合可用一維數(shù)組來表示，設(shè)此數(shù)組為S，凡在集合S以外的頂點(diǎn)，其相應(yīng)的數(shù)組元素S[i]為0，否則為1。還需要另一個一維數(shù)組dist，每個頂點(diǎn)對應(yīng)數(shù)組的一個單元，記錄從源點(diǎn)到其他各頂點(diǎn)當(dāng)前的最短路徑長度，其初值為dist[i]=cost[0][i]，i=2…n。數(shù)組dist中的數(shù)據(jù)隨著算法的逐步進(jìn)行要不斷地修改。2019年6月30感謝你的觀看92狄克斯特拉算法狄克斯特拉算2019年6月30感謝你的觀看93定義了S集合和dist數(shù)組并對其初始化后，狄克斯特拉算法在進(jìn)行中，都是從S之外的頂點(diǎn)集合中選出一個頂點(diǎn)w，使dist[w]的值最小。于是從源點(diǎn)到達(dá)w只通過S中的頂點(diǎn)，把w加入集合S中，并調(diào)整dist中記錄的從源點(diǎn)到集合中每個頂點(diǎn)v的距離：從原來的dist[v]和dist[w]+cost[w][v]中，選擇較小的值作為新的dist[v]。重復(fù)上述過程，直到S中包含V中其余各頂點(diǎn)的最短路徑。2019年6月30感謝你的觀看93定義了S集合和dist數(shù)組2019年6月30感謝你的觀看94狄克斯特拉算法例子以圖所示的圖為例來說明當(dāng)指定以V6為源點(diǎn)V0后，用狄克斯特拉算法求最短路徑的動態(tài)執(zhí)行情況，其表示集合的數(shù)組S和表示距離的數(shù)組dist元素值的變化如圖所示。2019年6月30感謝你的觀看94狄克斯特拉算法例子以圖所示2019年6月30感謝你的觀看95

算法動態(tài)執(zhí)行情況2019年6月30感謝你的觀看95算法動態(tài)執(zhí)行情況2019年6月30感謝你的觀看96

2019年6月30感謝你的觀看962019年6月30感謝你的觀看97小結(jié)圖圖的存儲結(jié)構(gòu)鄰接矩陣鄰接表圖的遍歷深度優(yōu)先搜索廣度優(yōu)先搜索圖的應(yīng)用最小生成樹最短路徑問題利用AOV網(wǎng)絡(luò)研究拓?fù)渑判騿栴}利用AOE網(wǎng)絡(luò)研究關(guān)鍵路徑的方法2019年6月30感謝你的觀看97小結(jié)圖2019年6月30感謝你的觀看98圖的應(yīng)用實(shí)例在地理信息系統(tǒng)中的應(yīng)用在“變電站故障定位及恢復(fù)處理智能系統(tǒng)”中的應(yīng)用在Internet路由器中的應(yīng)用見：陳向群.數(shù)據(jù)結(jié)構(gòu).北京：人民郵電出版社，2001：174-182.2019年6月30感謝你的觀看98圖的應(yīng)用實(shí)例在地理信息系統(tǒng)2019年6月30感謝你的觀看99思考題1.用深度悠閑搜索和廣度悠閑搜索對下圖進(jìn)行遍歷(從頂點(diǎn)1出發(fā)),給出遍歷序列.123645782019年6月30感謝你的觀看99思考題1.用深度悠閑搜索2019年6月30感謝你的觀看1002019年6月30感謝你的觀看1002019年6月30感謝你的觀看101思考題2.對下列所示的無向帶權(quán)圖，

(1)寫出它的鄰接矩陣，并按普里姆算法求其最小生成樹；

(2)寫出它的鄰接表，并按克魯斯卡爾算法求其最小生成樹。abcdefgh493265355576542019年6月30感謝你的觀看101思考題2.對下列所示的2019年6月30感謝你的觀看1022019年6月30感謝你的觀看1022019年6月30感謝你的觀看103第七章圖圖是一種比線性表和樹更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。在圖中，元素間的關(guān)系是多對多的，即任何兩個元素都有可能存在關(guān)系。圖的應(yīng)用非常廣泛，已滲入到諸如語言學(xué)、邏輯學(xué)、物理、化學(xué)、電訊工程、計(jì)算機(jī)科學(xué)以及數(shù)學(xué)的其它分支中(日常生活中的交通圖等)。在離散數(shù)學(xué)中，圖論是專門研究圖的性質(zhì)的數(shù)學(xué)分支。在數(shù)據(jù)結(jié)構(gòu)中對圖的討論主要側(cè)重于圖在計(jì)算機(jī)中的存儲方式和有關(guān)操作的算法。2019年6月30感謝你的觀看1第七章圖圖是一種比線性表和2019年6月30感謝你的觀看104

圖的基本內(nèi)容7.1圖的定義和術(shù)語7.2圖的存儲結(jié)構(gòu)7.3圖的遍歷7.4圖的連通性問題7.5有向無環(huán)圖及其應(yīng)用7.6最短路徑2019年6月30感謝你的觀看2圖的基本內(nèi)容7.1圖2019年6月30感謝你的觀看1057.1圖的定義和術(shù)語抽象數(shù)據(jù)類型圖的定義：

ADTGraph{

數(shù)據(jù)對象V:V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點(diǎn)集。數(shù)據(jù)關(guān)系R:R={VR}VR={<v,w>|v,wV且P(v,w),<v,w>表示從v到w的弧，謂詞

P(v,w)定義了弧<v,w>的意義或信息}

基本操作P:CreateGraph,DestroyGraph,LocateVex,GetVex,PutVex,FirstAdjVex,NextAdjVex,InsertVex,DeleteVex,InsertArc,DeleteArc,DFSTraverse,BFSTraverse}ADTGraph2019年6月30感謝你的觀看37.1圖的定義和術(shù)語抽象數(shù)2019年6月30感謝你的觀看106圖的定義(續(xù))圖中的數(shù)據(jù)元素稱為頂點(diǎn)(vertex),V是頂點(diǎn)的有窮非空集合；VR是V上頂點(diǎn)的序偶或無序?qū)Φ募?。?lt;v,w>VR，則<v,w>表示從v到w的一條弧(Arc),且稱v為弧尾(Tail)或初始點(diǎn)(Initialnode),稱w為弧頭(Head)或終端點(diǎn)(Terminalnode),此時(shí)的圖稱為有向圖(Digraph)。若<v,w>VR必有<w,v>VR，即VR是對稱的，則以無序?qū)?v,w)代替兩個有序?qū)Γ硎緑和w之間的一條邊(Edge),此時(shí)的圖稱為無向圖(Undigraph)?？梢哉f圖由非空頂點(diǎn)集和邊集所組成。2019年6月30感謝你的觀看4圖的定義(續(xù))圖中的數(shù)據(jù)元2019年6月30感謝你的觀看107

圖的示例無向圖G1有向圖G2圖的二元組表示參見教材P1572019年6月30感謝你的觀看5圖的示例無向圖G1有向圖2019年6月30感謝你的觀看108圖的基本術(shù)語完全圖、稠密圖、稀疏圖約定：用n表示圖中頂點(diǎn)的數(shù)目，用e表示邊或弧的數(shù)目若無向圖中的每兩個頂點(diǎn)之間都存在著一條邊，有向圖中的每兩個頂點(diǎn)之間都存在著方向相反的兩條邊，則稱此圖為完全圖。當(dāng)一個圖接近完全圖時(shí)，稱為稠密圖。當(dāng)一個圖含有較少的邊或弧(e<nlogn)時(shí)，稱為稀疏圖。2019年6月30感謝你的觀看6圖的基本術(shù)語完全圖、稠密圖、2019年6月30感謝你的觀看109圖的基本術(shù)語(續(xù))權(quán)和網(wǎng)：在一個圖中，每條邊可以標(biāo)上具有某種含義的數(shù)值，此數(shù)值稱為該邊的權(quán)。邊上帶有權(quán)的圖稱為網(wǎng)。子圖：設(shè)有兩個圖G=(V,{E})和G’=(V’,{E’}),如果V’V，E’E，則稱G’是G的子圖。端點(diǎn)和鄰接點(diǎn)：在一個無向圖中，若(v,v’)E,則稱v,v’為此邊的兩個端點(diǎn)，v,v’互為鄰接點(diǎn)。頂點(diǎn)的度、入度、出度：無向圖中頂點(diǎn)v的度定義為和v相關(guān)聯(lián)的邊的數(shù)目，記為TD(v)。有向圖中，頂點(diǎn)v的入度是該頂點(diǎn)入邊的數(shù)目，記為ID(v)，出度是該頂點(diǎn)出邊的數(shù)目，記為OD(v)。顯然TD(v)=ID(v)+OD(v)。一般地，e=TD(vi)/2。2019年6月30感謝你的觀看7圖的基本術(shù)語(續(xù))權(quán)和網(wǎng)：在2019年6月30感謝你的觀看110圖的基本術(shù)語(續(xù))路徑和回路：在一個圖中，從頂點(diǎn)v到頂點(diǎn)v’的一條路徑是一個頂點(diǎn)序列。路徑長度是路徑上邊或弧的數(shù)目。第一個頂點(diǎn)和最后一個頂點(diǎn)相同的路徑稱為回路或或環(huán)。序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑稱為簡單路徑。除了第一個頂點(diǎn)和最后一個頂點(diǎn)之外，其余頂點(diǎn)不重復(fù)出現(xiàn)的回路，稱為簡單回路或簡單環(huán)。連通圖和連通分量：在無向圖G中，若兩個頂點(diǎn)v和v’之間有路徑存在，則稱v和v’是連通的。若G中任意兩個頂點(diǎn)都是連通的，則稱G為連通圖，否則稱為非連通圖。非連通圖的極大連通子圖叫做連通分量。例子見P159。2019年6月30感謝你的觀看8圖的基本術(shù)語(續(xù))路徑和回路2019年6月30感謝你的觀看111圖的基本術(shù)語(續(xù))強(qiáng)連通圖與強(qiáng)連通分量：在有向圖中,若對于每一對頂點(diǎn)v和v’,都存在一條從v到v’和從v’到v的路徑,則稱此圖是強(qiáng)連通圖。非強(qiáng)連通圖的極大強(qiáng)連通子圖叫做強(qiáng)連通分量。例子見P159。生成樹：一個連通圖的生成樹是一個極小連通子圖，它含有圖中全部頂點(diǎn)，但只有足以構(gòu)成一棵樹的n-1條邊。如果一個有向圖恰有一個頂點(diǎn)的入度為0，其余頂點(diǎn)的入度為1，則是一棵有向樹。一個有向圖的生成森林是由若干棵有向樹組成，含有圖中全部頂點(diǎn)，但只有足以構(gòu)成若干棵不相交的有向樹的弧。例子見P159-160。2019年6月30感謝你的觀看9圖的基本術(shù)語(續(xù))強(qiáng)連通圖與2019年6月30感謝你的觀看1127.2圖的存儲結(jié)構(gòu)圖的存儲結(jié)構(gòu)又稱圖的存儲表示或圖的表示。它有多種方法，主要介紹鄰接矩陣、鄰接表，簡要介紹鄰接多重表和十字鏈表。鄰接矩陣：表示頂點(diǎn)之間相鄰關(guān)系的矩陣。所謂兩頂點(diǎn)的相鄰關(guān)系即它們之間有邊相連。鄰接矩陣是一個（n×n）階方陣，n為圖的頂點(diǎn)數(shù)，它的每一行分別對應(yīng)圖的各個頂點(diǎn)，它的每一列也分別對應(yīng)圖的各個頂點(diǎn)。我們規(guī)定矩陣的元素為：2019年6月30感謝你的觀看107.2圖的存儲結(jié)構(gòu)圖的存2019年6月30感謝你的觀看113

無向圖的鄰接矩陣2019年6月30感謝你的觀看11無向圖的鄰接矩陣2019年6月30感謝你的觀看114

有向圖的鄰接矩陣2019年6月30感謝你的觀看12有向圖的鄰接矩陣2019年6月30感謝你的觀看115無向圖的鄰接矩陣是對稱的，如果A[i，j]=1，必有A[j，i]=1。這說明，只輸入和存儲其上三角陣元素即可得到整個鄰接矩陣。一般有向圖的鄰接矩陣是不對稱的，A[i，j]不一定等于A[j，i]。鄰接矩陣用二維數(shù)組即可存儲，定義如下：

intadjmatrix=ARRAY[n][n];如果圖的各邊是帶權(quán)的，只需將矩陣中的各個1元素?fù)Q成相應(yīng)邊的權(quán)即可。

鄰接矩陣的若干說明2019年6月30感謝你的觀看13無向圖的鄰接矩陣是對稱的，2019年6月30感謝你的觀看116產(chǎn)生無向圖鄰接矩陣算法voidcreatgraph(intadjarray[][]){inti,j,v1,v2,num;scanf(“%d”,&num);/*輸入頂點(diǎn)數(shù)*/if(num>0){for(i=1;i<=num;i++)for(j=1;j<=num;j++)adjarry[i][j]=0;/*矩陣初始化*/do{2019年6月30感謝你的觀看14產(chǎn)生無向圖鄰接矩陣算法vo2019年6月30感謝你的觀看117

產(chǎn)生無向圖鄰接矩陣算法續(xù)

scanf(“%d,%d”,&v1,&v2);/*輸入邊*/adjarray[v1][v2]=1;adjarray[v2][v1]=1;}while(v1!=0&&v2!=0);}elsenum=0;retrunnum;}2019年6月30感謝你的觀看15產(chǎn)生無向圖鄰接矩陣算法續(xù)2019年6月30感謝你的觀看118

鄰接表鄰接表是圖的一種鏈?zhǔn)酱鎯Y(jié)構(gòu)。在鄰接表結(jié)構(gòu)中，對圖中每個頂點(diǎn)建立一個單鏈表，第i個單鏈表中的結(jié)點(diǎn)表示依附于該頂點(diǎn)Vi的邊，即對于無向圖每個結(jié)點(diǎn)表示與該頂點(diǎn)相鄰接的一個頂點(diǎn)；對于有向圖則表示以該頂點(diǎn)為起點(diǎn)的一條邊的終點(diǎn)。一個圖的鄰接矩陣表示是唯一的，但其鄰接表表示是不唯一的。因?yàn)樵卩徑颖淼拿總€單鏈表中，各結(jié)點(diǎn)的順序是任意的。2019年6月30感謝你的觀看16鄰接表鄰接表是圖的一種2019年6月30感謝你的觀看119無向圖、有向圖

2019年6月30感謝你的觀看17無向圖、有向圖2019年6月30感謝你的觀看120無向圖的鄰接表

2019年6月30感謝你的觀看18無向圖的鄰接表2019年6月30感謝你的觀看121

有向圖的鄰接表2019年6月30感謝你的觀看19有向圖的鄰接表2019年6月30感謝你的觀看122鄰接表中每個表結(jié)點(diǎn)均由兩個域組成，其一是鄰接點(diǎn)域（adjvex），用以存放與頂點(diǎn)Vi相鄰接的頂點(diǎn)在圖中的位置；其二是鏈域（next），用以指向依附于頂點(diǎn)Vi的下一條邊所對應(yīng)的結(jié)點(diǎn)。如果用鄰接表存放網(wǎng)絡(luò)中的信息，則還需要在結(jié)點(diǎn)中增加一個存放權(quán)值的域。在每個鏈表設(shè)一表頭結(jié)點(diǎn)，一般這些表頭結(jié)點(diǎn)本身以向量的形式存儲。鄰接表的若干說明2019年6月30感謝你的觀看20鄰接表中每個表結(jié)點(diǎn)均由兩個2019年6月30感謝你的觀看123對于無向圖的鄰接表來說，一條邊對應(yīng)兩個單鏈表結(jié)點(diǎn)，鄰接表結(jié)點(diǎn)總數(shù)是邊數(shù)的2倍。在無向圖的鄰接表中，各頂點(diǎn)對應(yīng)的單鏈表的結(jié)點(diǎn)數(shù)（不算表頭結(jié)點(diǎn)）就等于該頂點(diǎn)的度數(shù)。在有向圖鄰接表中，一條弧對應(yīng)一個表結(jié)點(diǎn)，表結(jié)點(diǎn)的數(shù)目和弧的數(shù)目相同。在有向圖鄰接表中，單鏈表的結(jié)點(diǎn)數(shù)就等于相應(yīng)頂點(diǎn)的出度數(shù)。要求有向圖中某頂點(diǎn)的入度數(shù)，需掃視鄰接表的所有單鏈表，統(tǒng)計(jì)與頂點(diǎn)標(biāo)號相應(yīng)的結(jié)點(diǎn)個數(shù)。鄰接表的若干說明2019年6月30感謝你的觀看21對于無向圖的鄰接表來說，一2019年6月30感謝你的觀看124鄰接表存儲結(jié)構(gòu)定義#defineMAXVEX30structedgenode{intadjvex;/*鄰接點(diǎn)域*/structedgenode*next;/*鏈域*/};structvexnode{chardata;/*頂點(diǎn)信息*/structedgenode*link;};typedefstructvexnodeadjlist[MAXVEX];2019年6月30感謝你的觀看22鄰接表存儲結(jié)構(gòu)定義#def2019年6月30感謝你的觀看125生成無向圖的鄰接表算法voidcreategraph(adjlistg){inte,i,s,d,n;structedgenode*p;printf(“請輸入結(jié)點(diǎn)數(shù)(n)和邊數(shù)(e):\n”);scanf(“%d,%d”,&n,&e);for(i=1;i<=n;i++){printf(“\n請輸入第%d個頂點(diǎn)信息：”,i);scanf(“%c”,&g[i].data);g[i].link=NULL;}for(i=1;i<=e;i++)

2019年6月30感謝你的觀看23生成無向圖的鄰接表算法vo2019年6月30感謝你的觀看126生成無向圖的鄰接表算法續(xù)

{printf(“\n請輸入第%d條邊起點(diǎn)序號，終點(diǎn)序號：”,i);scanf(“%d,%d”,&s,&d);p=(structedgenode*)malloc(sizeof(edgenode));p→adjvex=d;/*鄰接點(diǎn)序號為d*/

p→next=g[s].link;

g[s].link=p;