7￥-seven(天津科技大學(xué))

第七章圖圖是一種比線性表和樹更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。在圖中，元素間的關(guān)系是多對(duì)多的，即任何兩個(gè)元素都有可能存在關(guān)系。圖的應(yīng)用非常廣泛，已滲入到諸如語(yǔ)言學(xué)、邏輯學(xué)、物理、化學(xué)、電訊工程、計(jì)算機(jī)科學(xué)以及數(shù)學(xué)的其它分支中(日常生活中的交通圖等)。在離散數(shù)學(xué)中，圖論是專門研究圖的性質(zhì)的數(shù)學(xué)分支。在數(shù)據(jù)結(jié)構(gòu)中對(duì)圖的討論主要側(cè)重于圖在計(jì)算機(jī)中的存儲(chǔ)方式和有關(guān)操作的算法。10/6/20241第七章圖圖的基本內(nèi)容7.1圖的定義和術(shù)語(yǔ)7.2圖的存儲(chǔ)結(jié)構(gòu)7.3圖的遍歷7.4圖的連通性問(wèn)題7.5有向無(wú)環(huán)圖及其應(yīng)用7.6最短路徑10/6/20242第七章圖7.1圖的定義和術(shù)語(yǔ)抽象數(shù)據(jù)類型圖的定義：

ADTGraph{

數(shù)據(jù)對(duì)象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}ADTGraph10/6/20243第七章圖圖的定義(續(xù))圖中的數(shù)據(jù)元素稱為頂點(diǎn)(vertex),V是頂點(diǎn)的有窮非空集合；VR是V上頂點(diǎn)的序偶或無(wú)序?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是對(duì)稱的，則以無(wú)序?qū)?v,w)代替兩個(gè)有序?qū)Γ硎緑和w之間的一條邊(Edge),此時(shí)的圖稱為無(wú)向圖(Undigraph)。可以說(shuō)圖由非空頂點(diǎn)集和邊集所組成。10/6/20244第七章圖圖的示例無(wú)向圖G1有向圖G2圖的二元組表示參見教材P15710/6/20245第七章圖圖的基本術(shù)語(yǔ)完全圖、稠密圖、稀疏圖約定：用n表示圖中頂點(diǎn)的數(shù)目，用e表示邊或弧的數(shù)目若無(wú)向圖中的每?jī)蓚€(gè)頂點(diǎn)之間都存在著一條邊，有向圖中的每?jī)蓚€(gè)頂點(diǎn)之間都存在著方向相反的兩條邊，則稱此圖為完全圖。當(dāng)一個(gè)圖接近完全圖時(shí)，稱為稠密圖。當(dāng)一個(gè)圖含有較少的邊或弧(e<nlogn)時(shí)，稱為稀疏圖。10/6/20246第七章圖圖的基本術(shù)語(yǔ)(續(xù))權(quán)和網(wǎng)：在一個(gè)圖中，每條邊可以標(biāo)上具有某種含義的數(shù)值，此數(shù)值稱為該邊的權(quán)。邊上帶有權(quán)的圖稱為網(wǎng)。子圖：設(shè)有兩個(gè)圖G=(V,{E})和G’=(V’,{E’}),如果V’

V，E’

E，則稱G’是G的子圖。端點(diǎn)和鄰接點(diǎn)：在一個(gè)無(wú)向圖中，若(v,v’)E,則稱v,v’為此邊的兩個(gè)端點(diǎn)，v,v’互為鄰接點(diǎn)。頂點(diǎn)的度、入度、出度：無(wú)向圖中頂點(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。10/6/20247第七章圖圖的基本術(shù)語(yǔ)(續(xù))路徑和回路：在一個(gè)圖中，從頂點(diǎn)v到頂點(diǎn)v’的一條路徑是一個(gè)頂點(diǎn)序列。路徑長(zhǎng)度是路徑上邊或弧的數(shù)目。第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑稱為回路或或環(huán)。序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑稱為簡(jiǎn)單路徑。除了第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)之外，其余頂點(diǎn)不重復(fù)出現(xiàn)的回路，稱為簡(jiǎn)單回路或簡(jiǎn)單環(huán)。連通圖和連通分量：在無(wú)向圖G中，若兩個(gè)頂點(diǎn)v和v’之間有路徑存在，則稱v和v’是連通的。若G中任意兩個(gè)頂點(diǎn)都是連通的，則稱G為連通圖，否則稱為非連通圖。非連通圖的極大連通子圖叫做連通分量。例子見P159。10/6/20248第七章圖圖的基本術(shù)語(yǔ)(續(xù))強(qiáng)連通圖與強(qiáng)連通分量：在有向圖中,若對(duì)于每一對(duì)頂點(diǎn)v和v’,都存在一條從v到v’和從v’到v的路徑,則稱此圖是強(qiáng)連通圖。非強(qiáng)連通圖的極大強(qiáng)連通子圖叫做強(qiáng)連通分量。例子見P159。生成樹：一個(gè)連通圖的生成樹是一個(gè)極小連通子圖，它含有圖中全部頂點(diǎn)，但只有足以構(gòu)成一棵樹的n-1條邊。如果一個(gè)有向圖恰有一個(gè)頂點(diǎn)的入度為0，其余頂點(diǎn)的入度為1，則是一棵有向樹。一個(gè)有向圖的生成森林是由若干棵有向樹組成，含有圖中全部頂點(diǎn)，但只有足以構(gòu)成若干棵不相交的有向樹的弧。例子見P159-160。10/6/20249第七章圖7.2圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu)又稱圖的存儲(chǔ)表示或圖的表示。它有多種方法，主要介紹鄰接矩陣、鄰接表，簡(jiǎn)要介紹鄰接多重表和十字鏈表。鄰接矩陣：表示頂點(diǎn)之間相鄰關(guān)系的矩陣。所謂兩頂點(diǎn)的相鄰關(guān)系即它們之間有邊相連。鄰接矩陣是一個(gè)（n×n）階方陣，n為圖的頂點(diǎn)數(shù)，它的每一行分別對(duì)應(yīng)圖的各個(gè)頂點(diǎn)，它的每一列也分別對(duì)應(yīng)圖的各個(gè)頂點(diǎn)。我們規(guī)定矩陣的元素為：10/6/202410第七章圖無(wú)向圖的鄰接矩陣10/6/202411第七章圖有向圖的鄰接矩陣10/6/202412第七章圖無(wú)向圖的鄰接矩陣是對(duì)稱的，如果A[i，j]=1，必有A[j，i]=1。這說(shuō)明，只輸入和存儲(chǔ)其上三角陣元素即可得到整個(gè)鄰接矩陣。一般有向圖的鄰接矩陣是不對(duì)稱的，A[i，j]不一定等于A[j，i]。鄰接矩陣用二維數(shù)組即可存儲(chǔ)，定義如下：

int

adjmatrix=ARRAY[n][n];如果圖的各邊是帶權(quán)的，只需將矩陣中的各個(gè)1元素?fù)Q成相應(yīng)邊的權(quán)即可。鄰接矩陣的若干說(shuō)明10/6/202413第七章圖產(chǎn)生無(wú)向圖鄰接矩陣算法voidcreatgraph(int

adjarray[][]){

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{10/6/202414第七章圖產(chǎn)生無(wú)向圖鄰接矩陣算法續(xù)

scanf(“%d,%d”,&v1,&v2);/*輸入邊*/adjarray[v1][v2]=1;adjarray[v2][v1]=1;}while(v1!=0&&v2!=0);}elsenum=0;

retrunnum;}10/6/202415第七章圖鄰接表鄰接表是圖的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。在鄰接表結(jié)構(gòu)中，對(duì)圖中每個(gè)頂點(diǎn)建立一個(gè)單鏈表，第i個(gè)單鏈表中的結(jié)點(diǎn)表示依附于該頂點(diǎn)Vi的邊，即對(duì)于無(wú)向圖每個(gè)結(jié)點(diǎn)表示與該頂點(diǎn)相鄰接的一個(gè)頂點(diǎn)；對(duì)于有向圖則表示以該頂點(diǎn)為起點(diǎn)的一條邊的終點(diǎn)。一個(gè)圖的鄰接矩陣表示是唯一的，但其鄰接表表示是不唯一的。因?yàn)樵卩徑颖淼拿總€(gè)單鏈表中，各結(jié)點(diǎn)的順序是任意的。10/6/202416第七章圖無(wú)向圖、有向圖

10/6/202417第七章圖無(wú)向圖的鄰接表

10/6/202418第七章圖

有向圖的鄰接表10/6/202419第七章圖鄰接表中每個(gè)表結(jié)點(diǎn)均由兩個(gè)域組成，其一是鄰接點(diǎn)域（adjvex），用以存放與頂點(diǎn)Vi相鄰接的頂點(diǎn)在圖中的位置；其二是鏈域（next），用以指向依附于頂點(diǎn)Vi的下一條邊所對(duì)應(yīng)的結(jié)點(diǎn)。如果用鄰接表存放網(wǎng)絡(luò)中的信息，則還需要在結(jié)點(diǎn)中增加一個(gè)存放權(quán)值的域。在每個(gè)鏈表設(shè)一表頭結(jié)點(diǎn)，一般這些表頭結(jié)點(diǎn)本身以向量的形式存儲(chǔ)。鄰接表的若干說(shuō)明10/6/202420第七章圖對(duì)于無(wú)向圖的鄰接表來(lái)說(shuō)，一條邊對(duì)應(yīng)兩個(gè)單鏈表結(jié)點(diǎn)，鄰接表結(jié)點(diǎn)總數(shù)是邊數(shù)的2倍。在無(wú)向圖的鄰接表中，各頂點(diǎn)對(duì)應(yīng)的單鏈表的結(jié)點(diǎn)數(shù)（不算表頭結(jié)點(diǎn)）就等于該頂點(diǎn)的度數(shù)。在有向圖鄰接表中，一條弧對(duì)應(yīng)一個(gè)表結(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)號(hào)相應(yīng)的結(jié)點(diǎn)個(gè)數(shù)。鄰接表的若干說(shuō)明10/6/202421第七章圖鄰接表存儲(chǔ)結(jié)構(gòu)定義#defineMAXVEX30

struct

edgenode{int

adjvex;/*鄰接點(diǎn)域*/

struct

edgenode*next;/*鏈域*/};struct

vexnode{chardata;/*頂點(diǎn)信息*/

struct

edgenode*link;};

typedef

struct

vexnode

adjlist[MAXVEX];10/6/202422第七章圖生成無(wú)向圖的鄰接表算法voidcreategraph(adjlistg){

inte,i,s,d,n;

struct

edgenode*p;

printf(“請(qǐng)輸入結(jié)點(diǎn)數(shù)(n)和邊數(shù)(e):\n”);

scanf(“%d,%d”,&n,&e);for(i=1;i<=n;i++){

printf(“\n請(qǐng)輸入第%d個(gè)頂點(diǎn)信息：”,i);

scanf(“%c”,&g[i].data);g[i].link=NULL;}for(i=1;i<=e;i++)

10/6/202423第七章圖生成無(wú)向圖的鄰接表算法續(xù)

{printf(“\n請(qǐng)輸入第%d條邊起點(diǎn)序號(hào)，終點(diǎn)序號(hào)：”,i);

scanf(“%d,%d”,&s,&d);p=(struct

edgenode*)malloc(sizeof(edgenode));

p→adjvex=d;/*鄰接點(diǎn)序號(hào)為d*/

p→next=g[s].link;

g[s].link=p;

/*將新結(jié)點(diǎn)插入頂點(diǎn)Vs邊表的頭部*/p=(struct

edgenode*)malloc(sizeof(edgenode));

p→adjvex=s;/*鄰接點(diǎn)序號(hào)為s*/p→next=g[d].link;g[d].link=p;/*將新結(jié)點(diǎn)插入頂點(diǎn)Vd邊表的頭部*/}}10/6/202424第七章圖十字鏈表和鄰接多重表簡(jiǎn)介十字鏈表是將有向圖的鄰接表和逆鄰接表結(jié)合起來(lái)得到的一種鏈表。鄰接多重表是無(wú)向圖的另一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。在鄰接多重表中，每一條邊用一個(gè)結(jié)點(diǎn)表示，它由五個(gè)域組成；每一個(gè)頂點(diǎn)也用一個(gè)結(jié)點(diǎn)表示，它由兩個(gè)域組成。10/6/202425第七章圖思考題1.已知如下圖所示的有向圖，請(qǐng)給出該圖的（1）每個(gè)頂點(diǎn)的入/出度；（2）鄰接矩陣；（3）鄰接表。15624310/6/202426第七章圖7.3圖的遍歷從圖中某一頂點(diǎn)出發(fā)訪遍圖中其余結(jié)點(diǎn)，且使每一個(gè)頂點(diǎn)僅被訪問(wèn)一次，這一過(guò)程稱為圖的遍歷(TraversingGraph).圖的遍歷算法是求解圖的連通性、拓?fù)渑判蚝颓箨P(guān)鍵路徑等算法的基礎(chǔ)。為了避免同一頂點(diǎn)被訪問(wèn)多次，在遍歷圖的過(guò)程中，必須記下每個(gè)已訪問(wèn)過(guò)的頂點(diǎn)。圖的遍歷有兩種：深度優(yōu)先搜索和廣度優(yōu)先搜索。10/6/202427第七章圖深度優(yōu)先搜索(DFS)類似于樹的先根遍歷，是樹的先根遍歷的推廣。首先訪問(wèn)圖中某指定起始點(diǎn)Vi

，然后由Vi出發(fā)訪問(wèn)它的任一相鄰接頂點(diǎn)Vj,再?gòu)腣j出發(fā)訪問(wèn)Vj的任一未訪問(wèn)過(guò)的相鄰接頂點(diǎn)Vk,再?gòu)腣k出發(fā)進(jìn)行類似訪問(wèn)，如此進(jìn)行下去，直到某頂點(diǎn)已沒有未被訪問(wèn)過(guò)的相鄰接頂點(diǎn)時(shí)，則退回一步，退到前一個(gè)頂點(diǎn)，找前一個(gè)頂點(diǎn)的其它尚未被訪問(wèn)的相鄰接頂點(diǎn)。如有未訪問(wèn)過(guò)的相鄰接頂點(diǎn)，則訪問(wèn)此頂點(diǎn)后，再?gòu)脑擁旤c(diǎn)出發(fā)向前進(jìn)行與前述類似的訪問(wèn)；如退回一步后，前一頂點(diǎn)也沒有未被訪問(wèn)過(guò)的相鄰接頂點(diǎn)，則再向回退一步進(jìn)行搜索，重復(fù)上述過(guò)程，一直到所有頂點(diǎn)均被訪問(wèn)過(guò)為止。10/6/202428第七章圖圖的深度優(yōu)先遍歷例子深度優(yōu)先遍歷序列：1248536710/6/202429第七章圖由于圖中的路徑可能有環(huán)路，為了避免重復(fù)訪問(wèn)某些頂點(diǎn)，設(shè)計(jì)圖的搜索算法時(shí)，可設(shè)置一個(gè)表示頂點(diǎn)是否被訪問(wèn)過(guò)的輔助數(shù)組visited，初始時(shí)將數(shù)組元素置零，一旦某頂點(diǎn)Vi被訪問(wèn)過(guò)，則令visited[Vi]=1，以后此頂點(diǎn)即不再訪問(wèn)。深度優(yōu)先搜索算法10/6/202430第七章圖深度優(yōu)先搜索算法深度優(yōu)先搜索是一種遞歸的過(guò)程，可以簡(jiǎn)單地將其表示成遞歸的形式，其算法描述如下：

DFS(V0){

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

對(duì)所有與V0相鄰接的頂點(diǎn)wif(visited[w]==0)DFS(w);}10/6/202431第七章圖鄰接表表示的圖的DFS算法

intvisited[MAXVEX];voiddfsgraph(adjlist

adj,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);}10/6/202432第七章圖鄰接表存儲(chǔ)結(jié)構(gòu)定義#defineMAXVEX30

struct

edgenode{int

adjvex;/*鄰接點(diǎn)域*/

struct

edgenode*next;/*鏈域*/};struct

vexnode{chardata;/*頂點(diǎn)信息*/

struct

edgenode*link;};

typedef

struct

vexnode

adjlist[MAXVEX];10/6/202433第七章圖從Vi出發(fā)進(jìn)行DFS的遞歸算法voiddfs(adjlist

adj,intv){struct

edgenode*p;visited[v]=1;

printf(“%d”,v);p=adj[v]→link;while(p!=NULL){if(visited[p→adjvex]==0)

dfs(adjlist,p→adjvex);

/*從v未訪問(wèn)的鄰接點(diǎn)出發(fā)進(jìn)行DFS*/p=p→next;}}10/6/202434第七章圖時(shí)間復(fù)雜性分析一個(gè)有n個(gè)頂點(diǎn)、e條邊的圖，在深度優(yōu)先搜索圖的過(guò)程中，找鄰接點(diǎn)所需時(shí)間為O(e)。對(duì)輔助數(shù)組初始化時(shí)間為O(n)。因此，當(dāng)用鄰接表作為圖的存儲(chǔ)結(jié)構(gòu)時(shí)，深度優(yōu)先搜索圖的時(shí)間復(fù)雜性為O(e+n)。10/6/202435第七章圖非遞歸算法從頂點(diǎn)Vi出發(fā)進(jìn)行深度優(yōu)先遍歷的遞歸過(guò)程也可以寫成非遞歸的形式，此時(shí)需借助一個(gè)堆棧保存被訪問(wèn)過(guò)的結(jié)點(diǎn)，以便回溯時(shí)查找已被訪問(wèn)結(jié)點(diǎn)的未被訪問(wèn)過(guò)的鄰接點(diǎn)。設(shè)堆棧由一個(gè)一維數(shù)組構(gòu)成，數(shù)組名為stack，棧頂指針為top,假設(shè)此數(shù)組足夠大,不必考慮溢出的可能。10/6/202436第七章圖非遞歸算法#defineMAXVEX100voiddfs(adjlistg，int

v,intn)/*從頂點(diǎn)v出發(fā)進(jìn)行深度優(yōu)先遍歷*/{

struct

vexnode*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)10/6/202437第七章圖非遞歸算法續(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;}10/6/202438第七章圖非遞歸算法續(xù)

if(top>0){top--;/*退棧，回溯查找已被訪問(wèn)結(jié)點(diǎn)的未被訪問(wèn)過(guò)的鄰接點(diǎn)*/p=stack[top];p=p->next;}}}10/6/202439第七章圖廣度優(yōu)先搜索(BFS)圖的廣度優(yōu)先搜索（BFS）類似于樹的按層次遍歷。廣度優(yōu)先搜索的基本思想是：首先訪問(wèn)圖中某指定的起始點(diǎn)Vi并將其標(biāo)記為已訪問(wèn)過(guò)，然后由Vi出發(fā)訪問(wèn)與它相鄰接的所有頂點(diǎn)Vj、Vk……，并均標(biāo)記為已訪問(wèn)過(guò)，然后再按照Vj、Vk……的次序，訪問(wèn)每一個(gè)頂點(diǎn)的所有未被訪問(wèn)過(guò)的鄰接頂點(diǎn)，并均標(biāo)記為已訪問(wèn)過(guò)，下一步再?gòu)倪@些頂點(diǎn)出發(fā)訪問(wèn)與它們相鄰接的尚未被訪問(wèn)的頂點(diǎn)，如此做下去，直到所有的頂點(diǎn)均被訪問(wèn)過(guò)為止。10/6/202440第七章圖廣度優(yōu)先搜索(續(xù))在廣度優(yōu)先搜索中，若對(duì)頂點(diǎn)V1的訪問(wèn)先于頂點(diǎn)V2的訪問(wèn)，則對(duì)V1鄰接頂點(diǎn)的訪問(wèn)也先于V2鄰接頂點(diǎn)的訪問(wèn)。就是說(shuō)廣度優(yōu)先搜索中對(duì)鄰接點(diǎn)的尋找具有“先進(jìn)先出”的特性。因此，為了保證訪問(wèn)頂點(diǎn)的這種先后關(guān)系，需借助一個(gè)隊(duì)列暫存那些剛訪問(wèn)過(guò)的頂點(diǎn)。設(shè)此隊(duì)列由一個(gè)一維數(shù)組構(gòu)成，數(shù)組名為Queue，隊(duì)首指針和隊(duì)尾指針分別為front和rear。假設(shè)數(shù)組足夠大，不必考慮有溢出的可能性。廣度優(yōu)先搜索不是遞歸過(guò)程，不能用遞歸形式。10/6/202441第七章圖圖的廣度優(yōu)先遍歷例子廣度優(yōu)先遍歷序列：1234567810/6/202442第七章圖圖的遍歷舉例已知一有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如下頁(yè)圖所示，分別給出從頂點(diǎn)v1出發(fā)進(jìn)行深度優(yōu)先和廣度優(yōu)先遍歷所得到的頂點(diǎn)序列。10/6/202443第七章圖

一個(gè)有向圖的鄰接表10/6/202444第七章圖例子解答解：根據(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，v510/6/202445第七章圖B

F

S算法描述BFS(v0){訪問(wèn)v0頂點(diǎn)；

visited[v0]=1;

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

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

(b)visited[w]=1;(c)w入隊(duì);}}}10/6/202446第七章圖時(shí)間復(fù)雜性分析一個(gè)有n個(gè)頂點(diǎn)、e條邊的圖，在廣度優(yōu)先搜索圖的過(guò)程中，每個(gè)頂點(diǎn)至多進(jìn)一次隊(duì)列，圖的搜索過(guò)程實(shí)質(zhì)上是通過(guò)邊來(lái)找頂點(diǎn)的過(guò)程，找鄰接點(diǎn)所需時(shí)間為O(e)。對(duì)輔助數(shù)組初始化時(shí)間為O(n)。因此，當(dāng)用鄰接表作為圖的存儲(chǔ)結(jié)構(gòu)時(shí)，廣度優(yōu)先搜索圖的時(shí)間復(fù)雜性為O(e+n)。10/6/202447第七章圖7.4圖的連通性問(wèn)題無(wú)向圖的連通分量和生成樹深度優(yōu)先搜索或廣度優(yōu)先搜索在遍歷無(wú)向圖時(shí)，若無(wú)向圖是連通圖，則從圖中任一頂點(diǎn)出發(fā)，便可訪問(wèn)到圖中所有頂點(diǎn)。若無(wú)向圖是非連通圖，則需從多個(gè)頂點(diǎn)出發(fā)進(jìn)行搜索，每次調(diào)用搜索過(guò)程得到的頂點(diǎn)訪問(wèn)序列恰為其各個(gè)連通分量中的頂點(diǎn)集。遍歷過(guò)程中經(jīng)過(guò)的邊的集合和圖中所有頂點(diǎn)一起構(gòu)成連通圖的極小連通子圖，為連通圖的一棵生成樹。分別有深度優(yōu)先生成樹和廣度優(yōu)先生成樹。10/6/202448第七章圖生成樹的進(jìn)一步描述在一個(gè)無(wú)向連通圖G中，如果取它的全部頂點(diǎn)和一部分邊構(gòu)成一個(gè)子圖G’，若邊集E(G’)中的邊剛好將圖的所有頂點(diǎn)連通但又不形成環(huán)路，我們就稱子圖G’是原圖G的生成樹（Spanningtree）。生成樹有如下特點(diǎn)：任意兩個(gè)頂點(diǎn)之間有且僅有一條路徑；如果再增加一條邊就會(huì)出現(xiàn)環(huán)路；如果去掉一條邊此子圖就會(huì)變成非連通圖。一個(gè)有n個(gè)頂點(diǎn)的完全圖，一共存在n(n-2)種不同的生成樹。10/6/202449第七章圖非連通圖的生成森林對(duì)于非連通圖，每個(gè)連通分量中的頂點(diǎn)集，和遍歷時(shí)走過(guò)的邊一起構(gòu)成若干棵生成樹，這些連通分量的生成樹組成非連通圖的生成森林。生成樹和生成森林除依賴于遍歷算法外，還依賴于采用的存儲(chǔ)結(jié)構(gòu)。10/6/202450第七章圖最小生成樹對(duì)于帶權(quán)的連通圖（連通網(wǎng)）G，其生成樹也是帶權(quán)的。我們把生成樹各邊的權(quán)值總和稱為該生成樹的權(quán)。并且將權(quán)最小的生成樹稱為最小生成樹（MinimumSpanningTree）。具有n個(gè)頂點(diǎn)的連通圖的生成樹具有n-1條邊（少于此邊數(shù)不可能將各頂點(diǎn)連通，多于此邊數(shù)則必然要出現(xiàn)環(huán)路）。10/6/202451第七章圖無(wú)向連通圖

G及其生成樹無(wú)向連通圖G生成樹10/6/202452第七章圖圖G的其它生成樹生成樹最小生成樹10/6/202453第七章圖普里姆(prim)算法描述假設(shè)G=(V,E)是一個(gè)具有n個(gè)頂點(diǎn)的連通網(wǎng)絡(luò)，T=(U,TE)是G的最小生成樹，其中U是T的頂點(diǎn)集，TE是T的邊集，U和TE的初值均為空。算法開始時(shí)，首先從V中任取一個(gè)頂點(diǎn)（假定為V1），將此頂點(diǎn)并入U(xiǎn)中，此時(shí)最小生成樹頂點(diǎn)集U={V1}；然后從那些其一個(gè)端點(diǎn)已在U中，另一個(gè)端點(diǎn)仍在U外的所有邊中，找一條最短（即權(quán)值最?。┑倪?，假定該邊為(Vi,Vj),其中Vi∈U，Vj∈V-U,并把該邊(Vi,Vj)和頂點(diǎn)Vj分別并入T的邊集TE和頂點(diǎn)集U；10/6/202454第七章圖普里姆(prim)算法描述續(xù)如此進(jìn)行下去，每次往生成樹里并入一個(gè)頂點(diǎn)和一條邊，直到n-1次后，把所有n個(gè)頂點(diǎn)都并入生成樹T的頂點(diǎn)集U中，此時(shí)U=V，TE中包含有（n-1）條邊；這樣，T就是最后得到的最小生成樹。普里姆算法中每次選取的邊兩端，總是一個(gè)已連通頂點(diǎn)（在U集合內(nèi)）和一個(gè)未連通頂點(diǎn)（在U集合外），故這個(gè)邊選取后一定能將未連通頂點(diǎn)連通而又保證不會(huì)形成環(huán)路。10/6/202455第七章圖普里姆算法例子10/6/202456第七章圖普里姆算法為了便于在頂點(diǎn)集合U和V-U之間選擇權(quán)最小的邊，建立兩個(gè)數(shù)組closest和lowcost,closest[i]表示U中的一個(gè)頂點(diǎn)，該頂點(diǎn)與V-U中的一個(gè)頂點(diǎn)構(gòu)成的邊具有最小的權(quán)；lowcost表示該邊對(duì)應(yīng)的權(quán)值。開始，由于U的初值為{1}，所以，closest[i]的值為1，i=2,…n,而lowcost[i]為V1到各頂點(diǎn)的邊中最小的權(quán)值。10/6/202457第七章圖算法分析該算法中每一步執(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)。10/6/202458第七章圖克魯斯卡爾（Kruskal）算法假設(shè)G=（V，E）是一個(gè)具有n個(gè)頂點(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即為最小生成樹。10/6/202459第七章圖克魯斯卡爾算法例子(a)帶權(quán)圖10/6/202460第七章圖(c)最小生成樹10/6/202461第七章圖克魯斯卡爾算法續(xù)在選取某邊時(shí)如何判斷是否與已保留的邊形成環(huán)路？克魯斯卡爾算法是通過(guò)將各頂點(diǎn)劃分為集合的辦法來(lái)解決的。開始時(shí)假定n個(gè)頂點(diǎn)分屬于n個(gè)集合,即每個(gè)集合中有一個(gè)頂點(diǎn),當(dāng)確定某條邊保留作為生成樹的一條邊時(shí),就將該邊兩端點(diǎn)所屬的兩集合合并為一個(gè),表示原來(lái)屬于兩個(gè)集合的各個(gè)頂點(diǎn)已被這條新的邊連通.如果取到某條邊,發(fā)現(xiàn)它的兩個(gè)端點(diǎn)已屬于同一集合時(shí),此邊則應(yīng)當(dāng)舍去.因?yàn)閮蓚€(gè)頂點(diǎn)屬于同一集合說(shuō)明它們已連通,若再添上這條邊就會(huì)出現(xiàn)環(huán)路。如此進(jìn)行下去，到所有的頂點(diǎn)均已屬于一個(gè)集合時(shí)，此最小生成樹就構(gòu)成了。10/6/202462第七章圖

7.5

有向無(wú)環(huán)圖及其應(yīng)用在工程實(shí)踐中，一個(gè)工程項(xiàng)目往往由若干個(gè)子項(xiàng)目組成，這些子項(xiàng)目間往往有多種關(guān)系：①先后關(guān)系，即必須在一子項(xiàng)目完成后，才能開始實(shí)施另一個(gè)子項(xiàng)目；②子項(xiàng)目之間無(wú)次序要求，即兩個(gè)子項(xiàng)目可以同時(shí)進(jìn)行，互不影響。在工廠中，一件設(shè)備的生產(chǎn)包括許多工序，各工序之間也存在這兩種關(guān)系。學(xué)校里某個(gè)專業(yè)的課程學(xué)習(xí)，有些課程是基礎(chǔ)課，它們可以獨(dú)立于其它課程，即無(wú)前導(dǎo)課程；有些課程必須在一些課程學(xué)完后才能開始學(xué)。

10/6/202463第七章圖

AOV網(wǎng)絡(luò)這些類似的問(wèn)題都可以用有向圖來(lái)表示，我們把這些子項(xiàng)目、工序、課程看成一個(gè)個(gè)頂點(diǎn)稱之為活動(dòng)(Activity)。如果從頂點(diǎn)Vi到Vj之間存在有向邊<Vi，Vj>,則表示活動(dòng)i必須先于活動(dòng)j進(jìn)行。這種圖稱做頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)(ActivityOnVertexnetwork,簡(jiǎn)稱AOV網(wǎng)絡(luò))。例如某校計(jì)算機(jī)專業(yè)的課程及其相互之間的關(guān)系，它對(duì)應(yīng)的AOV網(wǎng)絡(luò)如下頁(yè)圖所示。10/6/202464第七章圖某專業(yè)課程設(shè)置10/6/202465第七章圖課程設(shè)置的AOV網(wǎng)絡(luò)10/6/202466第七章圖有向無(wú)環(huán)圖描述在AOV網(wǎng)絡(luò)中，如果頂點(diǎn)Vi的活動(dòng)必須在頂點(diǎn)Vj的活動(dòng)以前進(jìn)行，則稱Vi為Vj的前趨頂點(diǎn)，而稱Vj為Vi的后繼頂點(diǎn)。這種前趨后繼關(guān)系有傳遞性。AOV網(wǎng)絡(luò)中一定不能有有向環(huán)路。例如在下頁(yè)圖那樣的有向環(huán)路中，V2是V3的前趨頂點(diǎn)，V1是V2的前趨頂點(diǎn)，V3又是V1的前趨頂點(diǎn)，環(huán)路表示頂點(diǎn)之間的先后關(guān)系進(jìn)入了死循環(huán)。因此，對(duì)給定的AOV網(wǎng)絡(luò)首先要判定網(wǎng)絡(luò)中是否存在環(huán)路，只有有向無(wú)環(huán)路網(wǎng)絡(luò)在應(yīng)用中才有實(shí)際意義。一個(gè)無(wú)環(huán)的有向圖稱為有向無(wú)環(huán)圖，它是一類較有向樹更一般的特殊有向樹。10/6/202467第七章圖有向環(huán)路舉例10/6/202468第七章圖拓?fù)渑判蛩^“拓?fù)渑判颉本褪菍OV網(wǎng)絡(luò)中的各個(gè)頂點(diǎn)(各個(gè)活動(dòng))排列成一個(gè)線性有序序列，使得所有要求的前趨、后繼關(guān)系都能得到滿足。由于AOV網(wǎng)絡(luò)中有些頂點(diǎn)之間沒有次序要求，它們?cè)谕負(fù)溆行蛐蛄兄械奈恢每梢匀我忸嵉?，所以拓?fù)渑判虻慕Y(jié)果一般并不是唯一的。通過(guò)拓?fù)渑判蜻€可以判斷出此AOV網(wǎng)絡(luò)是否包含有有向環(huán)路，若有向圖G所有頂點(diǎn)都在拓?fù)渑判蛐蛄兄?，則AOV網(wǎng)絡(luò)必定不包含有有向環(huán)路。10/6/202469第七章圖拓?fù)渑判蚍椒?1)在網(wǎng)絡(luò)中選擇一個(gè)沒有前趨(入度為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)行到某一步，無(wú)法找到無(wú)前趨的頂點(diǎn)，則說(shuō)明此AOV網(wǎng)絡(luò)中存在有向環(huán)路，遇到這種情況，拓?fù)渑判蚓蜔o(wú)法進(jìn)行了。10/6/202470第七章圖拓?fù)渑判蜻^(guò)程AOV網(wǎng)絡(luò)輸出V3后10/6/202471第七章圖輸出V4后輸出V2后輸出V1后輸出V5后輸出拓?fù)湫蛄袨椋?421510/6/202472第七章圖

關(guān)鍵路徑法關(guān)鍵路徑法是采用邊表示活動(dòng)(ActivityOnEdge)的網(wǎng)絡(luò)，簡(jiǎn)稱為AOE網(wǎng)絡(luò)。AOE網(wǎng)絡(luò)是一個(gè)帶權(quán)的有向無(wú)環(huán)路圖，其中，每個(gè)頂點(diǎn)代表一個(gè)事件(Event)，事件說(shuō)明某些活動(dòng)或某一項(xiàng)活動(dòng)的完成，即階段性的結(jié)果。離開某頂點(diǎn)的各條邊所代表的活動(dòng)，只有在該頂點(diǎn)對(duì)應(yīng)的事件出現(xiàn)后才能開始。權(quán)值表示活動(dòng)持續(xù)的時(shí)間。10/6/202473第七章圖一個(gè)AOE網(wǎng)絡(luò)10/6/202474第七章圖AOE網(wǎng)絡(luò)通常利用AOE網(wǎng)絡(luò)可以研究以下兩個(gè)問(wèn)題：(1)完成整個(gè)工程至少需要多少時(shí)間？(2)哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵？10/6/202475第七章圖關(guān)鍵路徑完成工程所需的時(shí)間就是從開始點(diǎn)起進(jìn)行到結(jié)束點(diǎn)止所需的時(shí)間。路徑長(zhǎng)度是指沿路徑各邊的權(quán)值之和，也就是這些邊所代表的活動(dòng)所需時(shí)間之和。完成整個(gè)工程所需的時(shí)間取決于從開始點(diǎn)到結(jié)束點(diǎn)的最長(zhǎng)路徑長(zhǎng)度，此長(zhǎng)度最大的路徑叫做關(guān)鍵路徑。分析關(guān)鍵路徑的目的是辨別哪些是關(guān)鍵活動(dòng)，以便爭(zhēng)取提高關(guān)鍵活動(dòng)的效率，縮短整個(gè)工期。

10/6/202476第七章圖求關(guān)鍵路徑的算法描述在描述關(guān)鍵路徑的算法時(shí)，設(shè)活動(dòng)ai由弧<j,k>表示，要確定如下幾個(gè)相關(guān)的量：(1)事件Vj的最早出現(xiàn)時(shí)間和活動(dòng)的最早開始時(shí)間：從源點(diǎn)V1到某頂點(diǎn)Vj的最長(zhǎng)路徑長(zhǎng)度叫作事件j的最早出現(xiàn)時(shí)間，表示成ve[j]。頂點(diǎn)Vj的最早出現(xiàn)時(shí)間

ve[j]決定了從Vj指出的各條邊所代表活動(dòng)的最早開始時(shí)間，因?yàn)槭录不出現(xiàn)，它后面的各項(xiàng)活動(dòng)就不能開始。我們以e[i]表示活動(dòng)ai的最早開始時(shí)間。顯然e[i]=ve[j]。10/6/202477第七章圖求關(guān)鍵路徑的算法描述(續(xù))(2)活動(dòng)ai的最遲開始時(shí)間：在不影響整個(gè)工程按時(shí)完成的前提下，此項(xiàng)活動(dòng)最遲的必須開始時(shí)間，表示成L[i]。只要某活動(dòng)ai有L[i]=e[i]的關(guān)系，我們就稱ai為關(guān)鍵活動(dòng)。關(guān)鍵活動(dòng)只允許在一個(gè)確定的時(shí)間開始，再早，它前面的事件還沒出現(xiàn)，尚不能開始；再晚，又會(huì)延誤整個(gè)工程的按時(shí)完成。由于完成整個(gè)工程所需的時(shí)間是由關(guān)鍵路徑上各邊權(quán)值之和所決定的，顯然關(guān)鍵路徑上各條邊所對(duì)應(yīng)的活動(dòng)都是關(guān)鍵活動(dòng)。10/6/202478第七章圖求關(guān)鍵路徑的算法描述(續(xù))(3)事件j的最遲出現(xiàn)時(shí)間：即事件j在不延誤整個(gè)工程的前提下允許發(fā)生的最遲時(shí)間，表示為vl[j]。對(duì)某條指向頂點(diǎn)Vk的邊所代表的活動(dòng)ai可得到：

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

也就是活動(dòng)ai必須先于它后面事件的最遲出現(xiàn)時(shí)間開始，提前的時(shí)間為進(jìn)行此活動(dòng)所需的時(shí)間。下圖所示為活動(dòng)開始時(shí)間與事件出現(xiàn)時(shí)間的關(guān)系。VjaiVk10/6/202479第七章圖求關(guān)鍵路徑的算法描述(續(xù))確定關(guān)鍵路徑的方法就是要確定e[i]=L[i]的關(guān)鍵活動(dòng)。假設(shè)以w[j,k]表示有向邊<j,k>的權(quán)，即此邊對(duì)應(yīng)的活動(dòng)所需的時(shí)間，為了求AOE網(wǎng)絡(luò)中活動(dòng)ai的最早開始時(shí)間e[i]和活動(dòng)ai的最遲開始時(shí)間L[i]，先要求得頂點(diǎn)Vk的最早出現(xiàn)時(shí)間ve[k]和最遲出現(xiàn)時(shí)間vl[k]。10/6/202480第七章圖ve[k]和vl[k]可以采用下面的遞推公式計(jì)算：(1)向匯點(diǎn)遞推由源點(diǎn)的ve[1]=0開始，利用公式：向匯點(diǎn)的方向遞推，可逐個(gè)求出各頂點(diǎn)的ve

。式中p表示所有指向頂點(diǎn)的邊的集合。

10/6/202481第七章圖集合p此式的意義為：從指向頂點(diǎn)Vk的各邊的活動(dòng)中取最晚完成的一個(gè)活動(dòng)的完成時(shí)間作為Vk的最早出現(xiàn)時(shí)間ve[k]。10/6/202482第七章圖(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)的方向往回遞推，可逐個(gè)求出各頂點(diǎn)的最遲出現(xiàn)時(shí)間vl。式中s表示所有由Vj點(diǎn)指出的邊的集合，如下頁(yè)圖所示。

10/6/202483第七章圖集合s上述公式的意義為：由從Vj頂點(diǎn)指出的各邊所代表的活動(dòng)中取需最早開始的一個(gè)開始時(shí)間作為Vj的最遲出現(xiàn)時(shí)間。10/6/202484第七章圖無(wú)論是向匯點(diǎn)遞推還是向源點(diǎn)遞推，都必須按一定的頂點(diǎn)順序進(jìn)行。對(duì)所有的有向邊，向匯點(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)行即可，不必再重新排序。10/6/202485第七章圖

AOE網(wǎng)絡(luò)中的關(guān)鍵活動(dòng)10/6/202486第七章圖求關(guān)鍵路徑的算法描述(續(xù))由表可知時(shí)間余量為零的活動(dòng)都是關(guān)鍵活動(dòng)，即為a1，a4，a7，a8，a10，a11。這些關(guān)鍵活動(dòng)構(gòu)成兩條關(guān)鍵路徑，即關(guān)鍵路徑(V1，V2，V5，V7，V9)和(V1，V2，V5，V8，V9)。在安排工程時(shí)，對(duì)于關(guān)鍵活動(dòng)和余量小的活動(dòng)應(yīng)重點(diǎn)保證，余量較大