數(shù)據(jù)結(jié)構(gòu)中圖的教學(xué)課件

第6章圖圖作為一種非線性數(shù)據(jù)結(jié)構(gòu)，被廣泛應(yīng)用于多個技術(shù)領(lǐng)域，諸如系統(tǒng)工程、化學(xué)分析、統(tǒng)計力學(xué)、遺傳學(xué)、控制論、人二智能、編譯系統(tǒng)等領(lǐng)域，在這些技術(shù)領(lǐng)域中把圖結(jié)構(gòu)作為解決問題的數(shù)學(xué)手段之一。在離散數(shù)學(xué)中側(cè)重于對圖的理論進行系統(tǒng)的研究。在本章中，主要是應(yīng)用圖論的理論知識來討論如何在計算機上表示和處理圖，以及如何利用圖來解決一些實際問題。1

圖是一種比樹更為復(fù)雜的非線性結(jié)構(gòu)。在圖狀結(jié)構(gòu)中，任意兩個結(jié)點之間都可能具有鄰接關(guān)系，即在圖的數(shù)據(jù)元素之間存在多對多的關(guān)系。2

本章主要介紹以下幾個方面的內(nèi)容：圖的定義及常用術(shù)語；圖的各種存儲結(jié)構(gòu)；圖的遍歷；構(gòu)造最小生成樹的算法；求最短路徑的算法；拓?fù)渑判蚣捌渌惴ā?6.1圖的基本概念在講述圖時，習(xí)慣把數(shù)據(jù)元素統(tǒng)稱為是頂點?！皥D”是圖狀結(jié)構(gòu)的簡稱，它由一個非空的頂點集合V和一個描述頂點之間鄰接關(guān)系的邊集合E組成，E中每條邊連接的兩個頂點都必須屬于集合V。于是，一個圖可以記為：

G=（V，E）

6.1.1

圖的定義4 對于一個圖G來說，邊的集合E可以是空的。若vi、vj是V集合中的兩個頂點，且有邊連接，那么就用記號（vi，vj）表示頂點vi到頂點vj之間的邊。通常，邊是沒有方向的，即若圖G中有邊（vi，vj），那么也可以說有邊（vj，vi）。當(dāng)圖中的邊不帶有方向時，稱該圖為“無向圖”。5若圖中的邊是有向的，這樣的圖被稱為“有向圖”。在有向圖中，有邊（vi，vj），并不意味著也有邊（vj，vi）。常稱有向圖的邊為“弧”，把有向圖中從頂點vi到頂點vj的弧記為<vi，vj>，而把從頂點vj到頂點vi的弧記為<vj，vi>，這是兩條不同的弧。由于有向圖的弧是有方向的，因此常稱弧的起始頂點為“弧尾”，弧的終止頂點為“弧頭”。

6圖6-1無向圖和有向圖71．頂點的度、入度、出度6.1.2有關(guān)圖的常用術(shù)語無向圖中，若頂點vi和vj之間有一條邊（vi，vj）存在，則表明頂點vi和vj互為鄰接點，簡稱vi與vj相鄰接。所謂頂點vi的“度”，是指與它相鄰接的頂點的個數(shù)，記為D(vi)。

8注：1）

頂點的位置頂點在圖中的位置如何確定？從圖的邏輯結(jié)構(gòu)定義來看，圖中的頂點是非線性序列，不能像線性序列排列有唯一的序列。在圖中可以將任一個頂點看成是圖的第一個頂點，同理，對于任一頂點而言，它的鄰接點之間也不一定存在順序關(guān)系。9為了對圖的操作方便，需要將圖中的頂點按排列起來。所謂的“頂點在圖中的位置”是指該頂點在存儲中形成的位置序號，（如果是順序存儲可能是數(shù)組下標(biāo)，如果是鏈?zhǔn)酱鎯赡苁谴鎯Φ牡刂分羔槪?02）鄰接點對于無向圖G＝(V，{E})，如果邊（v1，v2）∈E，則稱頂點v1，v2互為鄰接點，即v1，v2相鄰接。邊（v1，v2）依附于頂點v1和v2

，或者說邊（v1，v2）與頂點v1和v2相關(guān)聯(lián)。

11在有向圖中，以頂點vi為弧尾的弧的個數(shù)，稱為頂點vi的“出度”，記為OD(vi)；以頂點vi為弧頭的弧的個數(shù)，稱為頂點vi的“入度”，記為ID(vi)。這時，一個頂點vi的度是指它的入度與出度之和，即：D(vi)=ID(vi)+OD(vi)。121314

在無向圖G中，所謂從頂點vi到頂點vj的一條“路徑”，是指在頂點vi與頂點vj之間存在有一個邊的序列：（vi,vi1），（vi1,vi2），…，（vim,vj）其中頂點vi、vi1、vi2、…、vim、vj屬于G的頂點集合V，邊（vi,vi1）、（vi1,vi2）、…、（vim,vj）屬于G的邊的集合E。2．路徑、路徑長度15對于有向圖G，所謂從頂點vi到頂點vj的一條“路徑”，是指在頂點vi與頂點vj之間存在有一個弧的序列：

<vi,vi1>，<vi1,vi2>，…，<vim,vj>

其中頂點vi、vi1、vi2、…、vim、vj屬于G的頂點集合V，弧<vi,vi1>、<vi1,vi2>、…、<vim,vj>屬于G的弧的集合E。16

所謂頂點vi到頂點vj的路徑“長度”，是指在這條路徑上擁有的邊的個數(shù)。V1V2V3V4G4V1V2V3V4G317在圖G＝(V，E)中，如果有結(jié)點序列：

Vp，Vi1，Vi2…，Vin，Vq，使得{(Vp，Vi1)，(Vi1，Vi2)，…，(Vin，Vq)}∈E（若對有向圖，則存在一系列弧）則稱從結(jié)點Vp到結(jié)點Vq存在一條路徑，路徑長度就為這條路徑上的邊數(shù)。如果一條路徑上的結(jié)點除Vp和Vq可以相同外，其它結(jié)點都不相同，則稱此路徑為一簡單路徑。

3．簡單路徑、回路18把路徑(V1，V2)，(V2，V3)，(V3，V4)縮寫成V1V2V3V4。在圖G3中V1，V2，V3和V1V3V4V1V3是兩條路徑，前者是一條簡單路徑，我們只研究簡單路徑。當(dāng)Vp=Vq時簡單路徑Vp，Vi1，Vi2…，Vin，Vp，稱為回路(也稱環(huán))。19若一個有n個頂點的無向圖，擁有n(n?1)/2條邊，那么就稱該圖為“無向完全圖”。對于一個無向完全圖來說，它的每個不同頂點對之間，都存在有一條邊。若一個有n個頂點的有向圖，擁有n(n?1)條弧，那么就稱該圖為“有向完全圖”。 對于一個有向完全圖來說，它的每個不同頂點對之間，都存在有兩條弧。

4．無向完全圖、有向完全圖20圖6-2（a）所示為一個無向完全圖，由于它有4個頂點，所以它有4

(4?1)/2=6條邊；圖6-2（b）所示為一個有向完全圖，由于它有4個頂點，所以它有4

(4?1)=12條弧。

21圖6-2無向、有向完全圖22

無論是無向圖還是有向圖，圖中的每一條邊或弧都與兩個頂點有關(guān)。 因此，在圖的頂點數(shù)n、邊數(shù)e以及各頂點的度D(vi)（1≤i≤n）三者之間，有如下的關(guān)系存在：23已知兩個圖G=（V，E），G′=（V′，E′）。若有V′是V的子集，E′是E的子集，且E′中的邊（或弧）都依附于V′中的頂點，那么就稱G′是G的一個“子圖”。

5．子圖24圖6-3子圖示例25

連通、連通圖、連通分量都是關(guān)于無向圖的概念。在無向圖中，若從頂點vi到頂點vj之間有路徑存在，則稱vi與vj是“連通”的。如果無向圖G中任意一對頂點之間都是連通的，則稱該圖G為“連通圖”，否則是非連通圖。6．連通、連通圖、連通分量26在無向圖G中，盡可能多地從集合V及E里收集頂點和邊，使它們成為該圖的一個極大的連通子圖，這個子圖就被稱為是無向圖G的一個“連通分量”。27圖6-4連通圖、非連通圖、連通分量2829有時，可以給圖的邊或弧依附上某種數(shù)值，這種與圖的邊或弧相關(guān)的數(shù)值被稱為“權(quán)”。邊或弧上帶有權(quán)的圖稱為“網(wǎng)圖”或“網(wǎng)絡(luò)”。7．邊的權(quán)、網(wǎng)絡(luò)30圖6-5無向網(wǎng)圖和有向網(wǎng)圖318.生成樹：n個頂點的連通圖的生成樹是一個極小連通子圖，它包含連通圖的全部頂點及n-1條邊，使所有頂點都連通但不構(gòu)成回路。生成樹具有兩個特點：1）n個頂點的生成樹包含n-1條邊；2）如果在生成樹中任意增加一條邊，則有一條回路。

3233課堂作業(yè)：選擇題：1.設(shè)無向圖G中頂點數(shù)為n,則圖G中最少有()條邊A.n(n-1)B.n-1C.n+1D.2n2.若圖G為n個頂點的有向圖,則圖G中最多有()條邊A.n(n-1)B.n-1C.n(n+1)D.n+13.在一個圖G中,所有頂點的度數(shù)之和等于所有邊數(shù)的()倍A.3B.1/2C.4D.2344.在具有n個頂點的無向完全圖G中邊的總數(shù)為()A.n+1

B.n(n-1)/2C.n(n+1)D.n-15.在具有6個頂點的無向圖G中至少應(yīng)有()條邊才能確保是一個連通圖.A.8B.7C.6

D.56.對于一個具有n個頂點的無向圖,若采用鄰接矩陣表示,則該矩陣的大小是()A.n-1B.n+1C.n2D.(n-1)235答案：BADBDC36

6.2

圖的存儲結(jié)構(gòu)圖是一種用途非常廣的數(shù)據(jù)結(jié)構(gòu)，存儲方法是多種多樣，對于不同的應(yīng)用問題有不同的表示方法。不論哪種數(shù)據(jù)結(jié)構(gòu)，在存儲時主要有兩方面：第一.如何存儲數(shù)據(jù)；第二.如何存儲數(shù)據(jù)間的關(guān)系。當(dāng)數(shù)據(jù)和關(guān)系都存儲在存儲器中，就可以按數(shù)據(jù)間的關(guān)系，實現(xiàn)對數(shù)據(jù)的各種操作。37圖有四種比較常用的存儲方法：①鄰接矩陣表示法；②鄰接表；③鄰接多重表；④十字鏈表。386.2.1

鄰接矩陣所謂“鄰接矩陣”，是表示頂點之間相鄰關(guān)系的矩陣，是指一種存儲結(jié)構(gòu)的組合。

用一個一維數(shù)組存儲圖中頂點的數(shù)據(jù)信息；用一個二維數(shù)組（即矩陣）存儲圖中各頂點間的鄰接關(guān)系。通常，簡略地只是把這個組合中的二維數(shù)組稱作是圖的“鄰接矩陣”。39假設(shè)圖G=（V，E）有n個頂點，為了表示n個頂點之間的鄰接關(guān)系，說明一個n

n的矩陣，并把其元素規(guī)定為：

40例6-1:對于下面所示的無向圖，請給出它的鄰接矩陣，并根據(jù)鄰接矩陣計算頂點v2的度。

4142圖6-6無向圖及相應(yīng)的鄰接矩陣43分析有向圖的鄰接矩陣圖6-7有向圖及相應(yīng)的鄰接矩陣44練習(xí):對于下面所示的無向圖和有向圖，判斷它們鄰接矩陣是否正確，并根據(jù)鄰接矩陣計算頂點v1的度。45對于一個網(wǎng)圖來說，不僅應(yīng)該通過鄰接矩陣反映出頂點之間的鄰接關(guān)系，還應(yīng)該利用它反映出依附于邊或弧的權(quán)值。因此，這時規(guī)定鄰接矩陣的元素為：

46圖6-8圖6-5中網(wǎng)圖的鄰接矩陣47對于鄰接矩陣，有如下特點。（1）無向圖的鄰接矩陣是對稱的對于無向圖來說，由于有邊（vi,vj）就意味著有邊（vj,vi），所以無向圖的鄰接矩陣關(guān)于其主對角線總是對稱的。48（2）鄰接矩陣與圖中頂點的度有密切關(guān)系對于無向（網(wǎng)）圖，其相應(yīng)的鄰接矩陣中第i行（或第i列）里非零（且非∞）元素的個數(shù)，正好是第i個頂點vi的度D(vi)。49對于有向（網(wǎng)）圖，其相應(yīng)的鄰接矩陣中第i行里非零（且非∞）元素的個數(shù)，正好是第i個頂點vi的出度OD(vi)；其相應(yīng)的鄰接矩陣中第i列里非零（且非∞）元素的個數(shù)，正好是第i個頂點vi的入度ID(vi)。50鄰接矩陣的類型描述#defineMAXVEX50 /*最大頂點個數(shù)*/typedefintweight; /*權(quán)值*/typedefcharDataType;typedefstruct{ weightarcs[MAXVEX][MAXVEX];/*鄰接矩陣*/ DataTypedata[MAXVEX];/*頂點信息*/ intvexs; /*頂點數(shù)*/}MGraph,*AdjMetrix;51鄰接矩陣表示下的基本操作

1．建立一個圖的鄰接矩陣voidCreateGraph(AdjMetrixg,intm[][MAXVEX],DataTyped[],intn){inti,j; g->vexs=n;for(i=0;i<n;i++){g->data[i]=d[i];for(j=0;j<n;j++)g->arcs[i][j]=m[i][j]; }}522.顯示鄰接矩陣voidDispGraph(AdjMetrixg){

inti,j; printf("項點：\n\t"); for(i=0;i<g->vexs;i++) printf("%c\t",g->data[i]); printf("\n\n矩陣:");for(i=0;i<g->vexs;i++){

printf("\n%c:\t",g->data[i]);for(j=0;j<g->vexs;j++) printf("%d:\t",g->arcs[i][j]);}printf("\n\n");}

533．取第一個鄰接點intGetFirst(AdjMetrixg,intk){inti;if(k<0||k>g->vexs){printf("參數(shù)k超出范圍！\n");return-1;}for(i=0;i<g->vexs;i++)if(g->arcs[k][i]==1)returni; return-1;}

544．下一個鄰接點intGetNext(AdjMetrixg,intk,intt){ inti;if(k<0||k>g->vexs||t<0||t>g->vexs){ printf("參數(shù)k或t超出范圍！\n"); returnNULL; } for(i=t+1;i<g->vexs;i++) if(g->arcs[k][i]==1)returni; return-1;}

55main(){MGraphgg; AdjMetrixg=≫ intpos,i; chard[]={'A','B','C','D','E'}; intm[][MAXVEX]={{0,1,0,1,1},{1,0,1,1,0},{0,1,0,0,0},{0,1,0,0,1},{1,0,0,1,0}}; CreateGraph(g,m,d,5); DispGraph(g); for(i=0;i<g->vexs;i++)

56{pos=GetFirst(g,i);if(pos!=-1)printf("\n[%c]\t%c",g->data[i],g->data[pos]);elseprintf("\n[%c]",g->data[i]);while(pos!=-1){pos=GetNext(g,i,pos); if(pos!=-1) printf("\t%c",g->data[pos]);}}printf("\n");}57課堂練習(xí):寫出下面所示圖的鄰接矩陣。58分析

用鄰接矩陣表示圖的不足之處：無論圖中實際包含多少條邊，圖的讀入、存儲空間初始化等需要O（n2）個單位時間，這對邊數(shù)較少（當(dāng)邊數(shù)m<<n2）的稀疏圖不是很經(jīng)濟的。對于邊數(shù)較多（如m>n*logn）的稠密圖，這種存儲方式是有效的。59鄰接表表示圖是由兩部分構(gòu)成，即頂點數(shù)據(jù)表和表示數(shù)據(jù)關(guān)系的邊（弧）構(gòu)成的表：

⑴頂點數(shù)據(jù)表：由所有頂點數(shù)據(jù)信息以順序結(jié)構(gòu)的向量表形式存儲，一個表目對應(yīng)于圖的一個結(jié)點，每個表目包括兩個部分，其一是表示數(shù)據(jù)的，可以是數(shù)據(jù)或指向結(jié)點數(shù)據(jù)的指針（data）；另一個是表示邊（?。┑闹羔?，該指針（firstarc）指向相鄰的第一條邊（?。?，通過這個指針便可以隨機訪問相鄰的任一頂點。表頭結(jié)點的結(jié)構(gòu)如圖(a)所示。

6.2.2

鄰接表6061

⑵表示邊的表：圖中有n個頂點，就有n個表示邊的鏈表，其中第i條鏈?zhǔn)怯膳c第i個頂點相鄰的邊構(gòu)成的鏈表。圖的每個結(jié)點都有一個邊鏈表，這個鏈表的表頭是頂點數(shù)據(jù)表中第i個表目的指針域。邊鏈表中結(jié)點的結(jié)構(gòu)如圖(b)所示。它由三部分組成，鄰接點域(adjvex)：用于存放與頂點vi相鄰接的頂點在頂點表中的位置；鏈指針域(nextarc)用于指向與頂點vi相關(guān)聯(lián)的下一條邊或弧的結(jié)點；數(shù)據(jù)域(info)用于存放與邊或弧相關(guān)的信息(權(quán)的信息)。6263把有關(guān)每一個頂點的單鏈表表頭結(jié)點匯集在一起，成為一個一維數(shù)組。這樣，這個一維數(shù)組、各頂點的單鏈表以及記錄圖頂點和邊（或?。﹤€數(shù)的變量，就統(tǒng)稱是圖的鄰接表。6465表示下面圖的鄰接表

DBACFE66

A14

B045

C35

D25

E01

F12301234567有向圖的鄰接表可見，在有向圖的鄰接表中不易找到指向該頂點的弧ABECF142301201234

ABCFE

68V5V1V2V3V4G869圖6-10無向圖（圖6-6）的鄰接表70圖6-11有向圖（圖6-7）的鄰接表71圖6-11無向網(wǎng)圖和有向網(wǎng)圖的鄰接表結(jié)構(gòu)72鄰接表的類型描述#defineMaxVertices20/*鏈表的結(jié)點結(jié)構(gòu)信息*/typedefstructArcNode{intadjvex;/*該弧所指向的頂點的位置*/

structArcNode*nextarc;/*指向下一條弧的指針*/InfoTypeinfo/*弧上的信息*/}ArcNode;73/*表頭向量的結(jié)點結(jié)構(gòu)信息*/typedefstructVnode{VertexTypedata;/*頂點信息*/

ArcNode*firstarc;/*指向第一條依附該頂點的的指針*/

}Vnode;74/*圖的結(jié)構(gòu)信息*/typedefstruct{Vnodevertex[MaxVertices];/*表頭向量*/

intvexnum,arcnum;/*圖的當(dāng)前頂點數(shù)和弧數(shù)*/

}AdjList;75基本操作的實現(xiàn) 1．建立圖的鄰接表函數(shù) 該函數(shù)包含兩部分內(nèi)容：頂點信息的輸入和邊信息的輸入。也可以理解為頂點的插入和邊的插入。 算法如下:76VoidCreateGraph(AdjList*G,intn,inte)/*輸入圖的數(shù)據(jù)信息，建立鄰接鏈表*/{ArcNode*q1,q2;G->arcnum=e;G->vexnum=n;Printf("\n輸入頂點的信息（整型）：");for(inti=1;i<=G->vernum;i++)G->Vertex[i].data=i;/*初始化*/77for(inti=1;i<=G->arcnum;i++) {printf("\n輸入邊的信息（頂點號i頂點號j邊的權(quán)值W）："); Scanf(“％d,%d,%d”,&i,&j,&w);/*對于無向圖*/if(i<1||i>G->vexnum||j<1||j>G->arnum){printf("參數(shù)1或2越界出錯!\n");return;}/*在第i條鏈表上，鏈入邊（i,j）的結(jié)點*/q1=(ArcNode*)malloc(sizeof(ArcNode));78

q1->adjvex=j;q1->infi=w;q1->nextarc=G->Vertex[i-1].firstarc;G->Vertex[i-1].firstarc=q1;q2=(ArcNode*)malloc(sizeof(ArcNode));q2->adjvex=i;q2->infi=w;q2->nextarc=G->Vertex[j-1].firstarc;G->Vertex[j-1].firstarc=q2;}}796.3圖的遍歷所謂“圖的遍歷”，即是指從圖的某一個頂點出發(fā)訪問圖中的所有頂點，且每個頂點只被訪問一次的這樣一個過程。80

遍歷圖比遍歷樹要繁雜，因為圖中的某一個頂點可能與圖中其余頂點相鄰接，即圖中允許有回路。所以當(dāng)從某一頂點訪問了其他頂點后有可能順著某一些邊又回到了該頂點。因此在遍歷圖時，為了保證圖中的各頂點在遍歷過程中訪問且僅訪問一次，需要為每個頂點設(shè)一個訪問標(biāo)志，設(shè)置一個數(shù)組，用于標(biāo)示圖中每個頂點是否被訪問過，它的初始值全部為0(“假”)，表示頂點均未被訪問過；某一個頂點被訪問后，置相應(yīng)訪問標(biāo)志數(shù)組中的值為1(“真”)，以表示該頂點已被訪問過。81按圖中結(jié)點的訪問順序，圖的遍歷分兩種：一種深度優(yōu)先遍歷，另一種是廣度優(yōu)先遍歷。

82深度優(yōu)先搜索(Depth_FirstSearch)是指按照深度方向搜索，它類似于樹的先根遍歷。深度優(yōu)先搜索的基本思想是：⑴從圖中某個頂點vi出發(fā)，首先訪問vi

。⑵找出頂點vi的第一個未被訪問的鄰接點vj，然后訪問頂點vj。找出頂點vj的第一個未被訪問的鄰接點vj1，……,重復(fù)本步驟，直到頂點vj1的所有的鄰接點都被訪問為止。6.3.1

圖的深度優(yōu)先搜索83⑶返回前一個訪問過的且仍有未被訪問的鄰接點的頂點，找出并訪問該頂點的下一個末被訪問的鄰接點，然后執(zhí)行步驟⑵。否則行步驟⑷。⑷若此時圖中還有頂點未被訪問，則另選圖中一個未被訪問的頂點作為起始點，重復(fù)上述搜索過程，直至圖中所有頂點均被訪問過為止。84深度優(yōu)先搜索的示例ACDEGBFIHACDEGBFIH123456789123456789前進回退深度優(yōu)先搜索過程深度優(yōu)先生成樹85圖的遍歷算法如下：

voidTraver(GraphG)/*Graph表示圖G的存儲結(jié)構(gòu),深度優(yōu)先遍歷圖G*/{for(vi=0;vi<G.vexnum;vi++)/*初始化*/visited[vi]=flase;for(vi=0;vi<G.vexnum;vi++)if(!visited[vi])DFS(G，vi);/*如果vi沒訪問，就從vi開始深度遍歷*/}其中從v0出發(fā)的遞歸過程如下：voidDFS(GraphG,intv0)/*從v0出發(fā)深度優(yōu)等遍歷圖G*/{visit[v0];visited[v0]=TRUE;w=Firstadj(G，v0);/*w為v0的鄰接點*/while(w>0)/*當(dāng)存在鄰接點*/{if(!visited[w])DFS(G，w);w=Nextadj(G，v0，w);/*找下一鄰接點*/}}86算法中對于Firstadj(G，v0)以及Nextadj(G，v0，w)并沒有具體實現(xiàn)。因為對于圖的不同存儲方法，兩個操作的實現(xiàn)方法不同，時間復(fù)雜度也不同。87⑴用鄰接矩陣方式實現(xiàn)voidDFS(MGraphG,intv0)/*圖G為鄰接矩陣類型*/{visit(v0);visited[v0]＝TRUE;for(vj＝0;vj<G.vexnum;vj++)if(!visited[vj]&&G.arc[v0][vj].adj==1)DFS(G，vj);/*找與v0相鄰沒訪問的所有點遍歷*/}88⑵用鄰接表方式實現(xiàn)深度優(yōu)先搜索voidDFS(ALGraph,intv0){visit(v0);visited(v0)=TRUE;p=G.vertices[v0].firstarc;/*找到與v0相鄰的第一個結(jié)點*/while(p){if(!visited(p->adjvex))DFS(G，p->adjvex);p=p->nextarc;}}89DFS

在訪問圖中某一起始頂點v

后,由

v

出發(fā),訪問它的任一鄰接頂點

w1;再從w1出發(fā),訪問與w1鄰

接但還沒有訪問過的頂點w2;然后再從w2出發(fā),進行類似的訪問,…如此進行下去,直至到達(dá)所有的鄰接頂點都被訪問過的頂點u為止。接著,退回一步,退到前一次剛訪問過的頂點,看是否還有其它沒有被訪問的鄰接頂點。如果有,則訪問此頂點,之后再從此頂點出發(fā),進行與前述類似的訪問;如果沒有,就再退回一步進行搜索。重復(fù)上述過程,直到連通圖中所有頂點都被訪問過為止。90例:圖6-12（a）所示為一個無向圖，圖6-12（b）是該圖的鄰接表。試求對該圖實施深度優(yōu)先搜索后，所得到的遍歷序列。91圖6-12基于鄰接表的無向圖深度優(yōu)先搜索92解：假定我們從頂點v1出發(fā)對圖進行深度優(yōu)先遍歷。遍歷的序列為：

v1→v2→v4→v5→v6→v393問題:深度優(yōu)先遍歷的訪問順序與圖的鄰接表存儲狀態(tài)有關(guān)，由于圖的鄰接表不是唯一的，因此對于同一個圖，其深度優(yōu)先遍歷輸出的結(jié)果也可能是不同的。但采用鄰接矩陣或鄰接表存儲結(jié)構(gòu)內(nèi)容已確定的圖的DFS序列將是確定的。例如：下面是同一個圖，但存儲結(jié)構(gòu)不同，因此深度優(yōu)先遍歷序列也不同，請大家動手做做。94BACDFEABFDCE請問為什么會出現(xiàn)這種現(xiàn)象？9596連通圖的深度優(yōu)先搜索遍歷

從圖中某個頂點V0

出發(fā)，訪問此頂點，然后依次從V0的各個未被訪問的鄰接點出發(fā)深度優(yōu)先搜索遍歷圖，直至圖中所有和V0有路徑相通的頂點都被訪問到。97V0w1w3w2w4w5w6w8w7w10w9w11G1G2G3V0w1w3w298由此可以看出:1.從深度優(yōu)先搜索遍歷連通圖的過程類似于樹的先根遍歷;2.如何判別V的鄰接點是否被訪問？解決的辦法是:為每個頂點設(shè)立一個“訪問標(biāo)志visited[w]”;99非連通圖的深度優(yōu)先搜索遍歷

以鄰接矩陣作為存儲結(jié)構(gòu),實現(xiàn)非連通圖的深度優(yōu)先搜索遍歷。對于非連通圖，一次遍歷僅能訪問開始頂點所在連通分量中的每個頂點，其他連通分量中的頂點則無法訪問到。因此，對于非連通圖，在遍歷完一個連通分量之后，還要再選擇一個開始頂點，遍歷下一個連通分量，重復(fù)這個過程，直到圖中的所有頂點…100abchdekfg812345670achkfedbg例如:訪問次序:achdkfebg101分析 采用鄰接鏈表來表示圖時，需要訪問表頭向量時間為O(n)。而外接的邊結(jié)點無向圖為2e（e為圖的邊數(shù)）個，有向圖為e個，時間消耗大約為O(e)。因此DFS算法的時間復(fù)雜度為O(n+e)。對于邊數(shù)很少的圖適合采用鄰接表存儲結(jié)構(gòu).102廣度優(yōu)先搜索(BreadthFirstSearch)

是指照廣度方向搜索，和深度優(yōu)先搜索不同的是：廣度優(yōu)先搜索先訪問完所有的鄰接點，再去尋找與鄰接點相鄰的下一層的其他頂點，它類似于樹的層次遍歷。廣度優(yōu)先搜索的基本思想是：⑴從圖中某個頂點v0出發(fā)，首先訪問v0。⑵依次訪問v0的各個末被訪問的鄰接點。6.3.2

廣度優(yōu)先搜索103⑶分別從這些鄰接點(端結(jié)點)出發(fā)，依次訪問它們的各個末被訪問的鄰接點(新的端結(jié)點)。訪問時應(yīng)保證：如果vi和vk為當(dāng)前結(jié)點，且vi在vk之前被訪問，則vi的所有末被訪問的鄰接點應(yīng)在vk的所有未被訪問的鄰接點之前訪問。重復(fù)步驟⑶，直到所有結(jié)點均沒有末被訪問的鄰接點為止。⑷若此時還有頂點末被訪問，則選一個未被訪問的頂點作為起始點，重復(fù)上述過程，直至所有頂點均被訪問過為止。104廣度優(yōu)先搜索的示例ACDEGBFIHACDEGBFH123456789123456789廣度優(yōu)先搜索過程廣度優(yōu)先生成樹I105BFS在訪問了起始頂點v之后,由v出發(fā),依次訪問v的各個未被訪問過的鄰接頂點w1,w2,…,wt,然后再順序訪問w1,w2,…,wt的所有還未被訪問過的鄰接頂點。再從這些訪問過的頂點出發(fā)，再訪問它們的所有還未被訪問過的鄰接頂點，…如此做下去，直到圖中所有頂點都被訪問到為止。106廣度優(yōu)先搜索是一種分層的搜索過程,每向前走一步可能訪問一批頂點,不像深度優(yōu)先搜索那樣有往回退的情況。因此,廣度優(yōu)先搜索不是一個遞歸的過程。107108注：采用鄰接鏈表存儲結(jié)構(gòu)，廣度優(yōu)先搜索遍歷圖的時間復(fù)雜度與深度優(yōu)先遍歷是相同的，其時間復(fù)雜度也是O(n2)。

109課堂練習(xí):對于下圖所示的無向圖，求：（1）鄰接矩陣、鄰接表。（2）給出從頂點A出發(fā)深度優(yōu)先搜索遍歷序列（3）給出從頂點C出發(fā)廣度優(yōu)先搜索遍歷序列110課堂練習(xí):1、n個頂點的連通圖最多有———條邊。2、在一個具有n個頂點的無向圖中，要連通全部頂點至少需要——條邊3、設(shè)圖G有n個頂點和e條邊，進行深度優(yōu)先遍歷的時間復(fù)雜度至多為——，進行廣度優(yōu)先遍歷的時間復(fù)雜度至多為——。1114、在無向圖G的鄰接矩陣A中，若A[i][j]等于1，則A[j][i]等于——5、已知圖G的鄰接表如圖所示，其從頂點v1出發(fā)的深度優(yōu)先遍歷序列為————，其從頂點v1出發(fā)的廣度優(yōu)先遍歷序列為——12＾34＾53244＾5＾24＾1121、對于如圖所示的有向圖，試給出（1）圖的鄰接矩陣；（2）鄰接表（出邊表）和逆鄰接表（入邊表）1131146.4生成樹與最小生成樹問題：假設(shè)要在n個城市之間建立通訊聯(lián)絡(luò)網(wǎng)，則連通n個城市只需要修建n-1條線路，如何在最節(jié)省經(jīng)費的前提下建立這個通訊網(wǎng)？115該問題等價于：構(gòu)造網(wǎng)的一棵最小生成樹，即：在e條帶權(quán)的邊中選取n-1條邊（不構(gòu)成回路），使“權(quán)值之和”為最小。1166.4.1生成樹與最小生成樹的概念有n個頂點的無向連通圖G=（V，E）的“生成樹”，是G的一個子圖S，它是包含G的所有n個頂點在內(nèi)的一個極小連通子圖。即S由V中的n個頂點、E中的n?1條邊組成。117作為無向連通圖的生成樹，有這樣的性質(zhì)：

只要往這個生成樹里添加一條屬于原圖中的邊，就會產(chǎn)生回路；

只要在這個生成樹里減少任意一條邊，它就成為了一個非連通圖；

無向連通圖的生成樹不是唯一的。118對于一個無向連通網(wǎng)圖G的生成樹S來說，稱各邊權(quán)值之和為該生成樹的權(quán)。所有生成樹中權(quán)值最小的那棵生成樹T，被稱作是圖G的最小代價生成樹，簡稱為“最小生成樹（MST）”。119算法的基本思想：設(shè)G=(V,E)是連通網(wǎng)，V是連通網(wǎng)中頂點集合，E是連通網(wǎng)中邊的集合。T=(U,D)是正在構(gòu)造的最小生成樹，U是最小生成樹的頂點的集合，D是最小生成樹的邊的集合。V-U表示屬于集合V，但不屬于集合U的頂點集合。6.4.2構(gòu)造最小生成樹的算法1．構(gòu)造最小生成樹的普里姆算法120（1）若從頂點v0開始構(gòu)造最小生成樹，則從集合V中取出頂點v0放入集合U中。此時，集合U={v0}，集合V-U={除v0以外的所有頂點}，集合D為空。（2）若在集合U中的頂點vi和集合V-U中的頂點vj之間存在邊，則尋找這些邊中權(quán)值最小的邊，但不構(gòu)成回路。將頂點vj加入集合U中，將邊(vi,vj)加入集合D中。（3）重復(fù)步驟（2），直至U與V相等為止。此時，D中必有n-1條邊，則T=(U,D)即是最小生成樹。121例6-15:已知一個如圖所示的帶權(quán)圖，請給出根據(jù)普里姆算法構(gòu)造的一顆最小生成樹（假設(shè)從頂點1開始構(gòu)造）。

122123圖6-14使用普里姆算法求網(wǎng)圖的最小生成樹過程124圖6-14使用Prim算法求網(wǎng)圖的最小生成樹過程125 克魯斯卡爾算法的思想是：設(shè)G=(V,E)是一個具有n個頂點的帶權(quán)連通圖，T=(U,D)是G的最小生成樹。初始時，U中包含G的全部n個頂點，D為空。

2．構(gòu)造最小生成樹的克魯斯卡爾算法1263.從E中選擇一條以前未選擇過的、邊上的權(quán)值最小的邊加入D中。但注意兩點:(1)若加入后，并未使T形成回路，則繼續(xù)選擇下一條邊；(2)若加入后，使T形成回路，則放棄選擇的邊。4.重復(fù)以上過程，直至D中包含了n-1條邊為止。此時，T即為G的最小生成樹。127 這樣，最小生成樹T中的各個頂點各自構(gòu)成一個連通分量。然后，按照邊的權(quán)值遞增的順序考察網(wǎng)G中的邊集E中的各條邊：若被考察的邊的兩個頂點屬于T的兩個不同的連通分量，則將此邊加入到最小生成樹T，同時把兩個連通分量連接為一個連同分量；128 若被考察的邊的兩個頂點屬于T的同一個連通分量，則將此邊舍去。如此下去，當(dāng)T中的連通分量個數(shù)為１時，此T中的該連通分量即為網(wǎng)G的一棵最小生成樹。129圖6-15使用Kruskal算法求網(wǎng)圖的最小生成樹過程130圖6-15使用Kruskal算法求網(wǎng)圖的最小生成樹過程131圖6-15使用Kruskal算法求網(wǎng)圖的最小生成樹過程132abcdegf195141827168213127aedcbgf1485316211336.5最短路徑

如果將交通網(wǎng)絡(luò)畫成帶權(quán)圖，假如用頂點表示城市，邊表示公路段，則由這些頂點和邊組成的圖可表示構(gòu)通各城市的公路網(wǎng)。邊的權(quán)用以表示兩個城市之間的距離、走過這段公路所需要的時間、通過這段朗的難易程度等。作為司機和乘汽車的人，自然關(guān)心如下兩個問題：⑴從甲地到乙地是否有公路？⑵從甲地到乙地有幾條公路，哪條公路最短或費用的代價最??？134這就是最短路徑所要討論的問題，所以下面探討有向圖的最短路徑。路徑的開始頂點：源點，路徑的最后一個頂點：終點或目標(biāo)點。除非特別說明，否則，所有的權(quán)大于零。設(shè)有帶權(quán)的有向圖G=(V，{E})，G中的邊權(quán)為w(e)。已知源點為v1，求v1到其它各頂點的最短路徑。135求最短路徑是圖的又一個典型應(yīng)用。圖6-16最短路徑136最短路徑分為單源最短路徑和每對頂點間的最短路徑兩類問題，前者討論的是圖中某個頂點到其他各頂點的最短路徑，后者討論的是圖中每對頂點間的最短路徑。137所謂“單源最短路徑”，即已知有向網(wǎng)圖G=（V，E）和一個源（頂）點V0，求V0到其他各頂點的最短路徑。求從源點V0到其余各點的最短路徑的算法的基本思想:依最短路徑的長度遞增的次序求得各條路徑

6.5.1單源最短路徑138源點v1…v2其中，從源點到頂點v1的最短路徑是所有最短路徑中長度最短者。139注意理解下面結(jié)論:1.路徑長度最短的最短路徑的特點:在這條路徑上，必定只含一條弧，并且這條弧是所有從源點出發(fā)的弧中權(quán)值最小。

2.下一條路徑長度次短的最短路徑的特點:它只可能有兩種情況:或者是直接從源點到該點(只含一條弧)；或者是，從源點經(jīng)過頂點v1，再到達(dá)該頂點(由兩條弧組成)。1403.再下一條路徑長度次短的最短路徑的特點:它可能有三種情況：或者是，直接從源點到該點(只含一條弧)；或者是，從源點經(jīng)過頂點v1，再到達(dá)該頂點(由兩條弧組成)；或者是，從源點經(jīng)過頂點v2，再到達(dá)該頂點。4.其余最短路徑的特點：它或者是直接從源點到該點(只含一條弧)；或者是，從源點經(jīng)過已求得最短路徑的頂點，再到達(dá)該頂點。141V4V0V1V2V3V5V6V8V76144248533912圖6.40有向帶權(quán)圖142源點終點最短路徑長度v0v1v0v16v2v0v24v3v0v35v4v0v2v46v5v0v2v4v57v6v0v2v4v5v7v613v7v0v2v4v5v7v611v8v0v2v4v5v7v6v815143求單源最短路徑的Dijkstra（迪杰斯特拉）算法思路:按路徑長度遞增的順序，逐個產(chǎn)生各最短路徑。把圖中的所有頂點分成兩組：第一組取名為U，里面包含的是那些從源點u到它們的最短路徑已經(jīng)確定的頂點；第二組取名V?U，里面包含的是那些從源點u到它們的最短路徑還未最后確定的頂點。具體步驟如下：

144算法思想：設(shè)集合S存放已經(jīng)求出的最短路徑的終點，初始狀態(tài)時，集合S中只有一個源點，不妨設(shè)為v1。以后每求得一條最短路徑（v1，…，vk），就將vk加入到集合S中，直到全部頂點全部都加入到集合S中為止。145（1）初始時，集合S里只含一個源點v1，集合V?S里是圖中除v1以外的所有頂點，v1到其他頂點的距離是它們間弧的權(quán)值（當(dāng)不存在弧時，長度為∞）；146（2）從V?S里挑選出一個與源點v1的距離為最小的頂點vi，把它從V?S移到S里，然后對V?S里剩下的頂點（比如vk）到源點v1的距離進行修改，方法是若圖中存在弧（vi,vk），且該弧的權(quán)值加上v1到vi的距離之和小于原先v1到vk的距離，那么就用此和代替原先v1到vk的距離，否則原先v1到vk的距離保持不變；147（3）不斷地對集合V?S實行操作 （2），當(dāng)V?S為空時，算法結(jié)束，所求得的v1到各頂點的距離即是源點到其他頂點的最短路徑長度。148例如用Dijkstra算法求有向網(wǎng)G的v0頂點到其余頂點v的最短路徑149

（1）初始時，S={1}，V-S={2，3，4，5}。各點的距離值及路徑為：

1502.從V-S中選擇距離值最小的頂點2，加入到S中。此時S={1，2}，V-S={3，4，5}。然后對V-S中各點的距離值進行修正，修正后各點的距離值及路徑為：

1513.再從V-S中選擇距離值最小的頂點4，加入到S中。此時S={1，2，4}，V-S={3，5}。修正V-S中的點的距離值為：1524.繼續(xù)從V-S中選擇距離值最小的頂點3，加入到S中。此時S={1，2，3，4}，V-S={5}。修正V-S中的點的距離值為：1535.最后從V-S中選擇距離值最小的頂點5，加入到S中。此時S={1，2，3，4，5}，V-S={}，算法結(jié)束。154課堂練習(xí):求有向網(wǎng)G的a頂點到其余頂點的最短路徑24158639735104afedbcg2155求解過程:1.初始時，S={a}，V-S={b,c,d,e,f,g,}。各點的距離值及路徑為：1組頂點:{a}2組頂點:{b,c,d,e,f,g}最短路徑:0距離值:24,8,15,∞,∞,∞經(jīng)過路徑:a->a經(jīng)過路徑:a->b,a->c,a->d,a->e,a->f,a->g1562.從V-S中選擇距離值最小的頂點c，加入到S中。此時S={a,c}，V-S={b,d,e,f,g}。然后對V-S中各點的距離值進行修正，修正后各點的距離值及路徑為：1組頂點:{a,c}2組頂點:{b,d,e,f,g}最短路徑:0,8距離值:24,15,15,11,∞經(jīng)過路徑:a->a,a->c經(jīng)過路徑:a->b,a->d,a->c->e,a->c->f,a->g

1573.從V-S中選擇距離值最小的頂點f，加入到S中。此時S={a,c,f}，V-S={b,d,e,g}。然后對V-S中各點的距離值進行修正，修正后各點的距離值及路徑為：1組頂點:{a,c,f}2組頂點:{b,d,e,g}最短路徑:0,8,11距離值:24,15,13,21經(jīng)過路徑:a->a,a->c,經(jīng)過路徑:a->b,a->d,a->c->fa->c->f->e,a->c->f->g1584.從V-S中選擇距離值最小的頂點e，加入到S中。此時S={a,c,f,e}，V-S={b,d,g}。然后對V-S中各點的距離值進行修正，修正后各點的距離值及路徑為：1組頂點:{a,c,f,e}2組頂點:{b,d,g}最短路徑:0,8,11,13距離值:24,15,21,經(jīng)過路徑:a->a,a->c,經(jīng)過路徑:a->b,a->d,a->c->fa->c->f->e,a->c->f->ga->c->f->e,

1595.從V-S中選擇距離值最小的頂點d，加入到S中。此時S={a,c,f,e,d}，V-S={b,g}。然后對V-S中各點的距離值進行修正，修正后各點的距離值及路徑為：1組頂點:{a,c,f,e,d}2組頂點: