第7章網(wǎng)狀結(jié)構(gòu)

第7章圖第7章圖7.1圖的基本概念

7.2圖的存儲(chǔ)結(jié)構(gòu)

7.3

圖的遍歷

7.4圖的生成樹(shù)

7.5圖的應(yīng)用7.6圖的算法C語(yǔ)言程序?qū)崿F(xiàn)舉例7.1圖的基本概念定義及其基本運(yùn)算

1.圖的定義

圖是n(n≥0)個(gè)元素組成的有限集合。圖可以用二元組形式表示，即G=(V,E)其中，V是數(shù)據(jù)元素的集合，稱(chēng)為頂點(diǎn)集；E是數(shù)據(jù)元素之間關(guān)系的集合，稱(chēng)為邊集。（a）無(wú)向圖G1(b)有向圖G2圖7.1有向圖和無(wú)向圖圖7.2無(wú)向圖G1的部分子圖2圖的基本術(shù)語(yǔ)

1．圖的種類(lèi)（1）無(wú)向圖（2）有向圖（3）混合圖（4）稀疏圖與稠密圖（5）賦權(quán)圖（a）頂點(diǎn)賦權(quán)圖(b)邊賦權(quán)圖圖7.3賦權(quán)圖2．鄰接點(diǎn)與度（1）鄰接點(diǎn)

（2）頂點(diǎn)的度

3．路徑（1）路徑

（2）路徑長(zhǎng)度

（3）簡(jiǎn)單路徑

（4）簡(jiǎn)單圖

（5）連通圖（a）無(wú)向圖G3（b）G3的連通分量圖7.4非連通的無(wú)向圖及其連通分量鄰接矩陣7.2圖的存儲(chǔ)結(jié)構(gòu)圖的鄰接矩陣表示法是用一個(gè)一維數(shù)組來(lái)存放頂點(diǎn)的信息，再用一個(gè)二維數(shù)組來(lái)存放邊或弧的信息的表示方法，又稱(chēng)為數(shù)組表示法。圖7.1中有向圖和無(wú)向圖的表示分別為。

圖7-3（b）的邊賦權(quán)圖表示為：圖7-3（b）的邊賦權(quán)圖表示為：圖的鄰接矩陣表示法具有以下特點(diǎn)：（1）無(wú)向圖的n階矩陣一定是對(duì)稱(chēng)矩陣。（2）無(wú)向圖的n階矩陣的第i行（或第i列）非零元素的個(gè)數(shù)為第i個(gè)頂點(diǎn)的度。（3）有向圖的n階矩陣的第i行非零元素的個(gè)數(shù)為第i個(gè)頂點(diǎn)的出度，第i列非零元素的個(gè)數(shù)就是第i個(gè)頂點(diǎn)的入度。（4）鄰接矩陣表示法可以很容易確定圖中任意兩個(gè)頂點(diǎn)之間是否有邊相連。

【例7.1】建立無(wú)向圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)。voidcreate_MGraph(Mgraph*g,inte)/*建立無(wú)向圖的鄰接矩陣，e為邊數(shù)*/{for(i=0;i<VEX_NUM;i++)g->vexs[i]=i;/*頂點(diǎn)信息*/for(i=0;i<VEX_NUM;i++)

for(j=0;j<VEX_NUM;j++)g->arcs[i][j]=0;/*二維數(shù)組先賦

0*/for(k=0;k<e;k++){scanf("%d,%d",&i,&j);/*i為邊的一端頂點(diǎn)，j為邊的另一端頂點(diǎn)*/g->arcs[i][j]=1;g->arcs[j][i]=1;}}7.2.2鄰接表圖的鄰接表是一種順序分配和鏈?zhǔn)椒峙湎嘟Y(jié)合的存儲(chǔ)結(jié)構(gòu)。在鄰接表中，對(duì)圖中每個(gè)頂點(diǎn)建立一個(gè)單鏈表，第i個(gè)單鏈表中的結(jié)點(diǎn)表示依附于頂點(diǎn)vi的邊。每個(gè)鏈表中附設(shè)頭結(jié)點(diǎn)，其數(shù)據(jù)域存放的是該結(jié)點(diǎn)的信息，指針域存放第一個(gè)與之相鄰接的頂點(diǎn)的地址。212345V1V2V3V4V545∧3∧13∧∧54鄰接表的特點(diǎn)如下：（1）若無(wú)向圖G有n個(gè)頂點(diǎn)，e條邊，則鄰接表需要n個(gè)表頭結(jié)點(diǎn)和2e個(gè)表結(jié)點(diǎn)。顯然，對(duì)于邊很少的圖，用鄰接表比用鄰接矩陣要節(jié)省存儲(chǔ)空間。（2）在無(wú)向圖的鄰接表中，頂點(diǎn)vi的度為第i個(gè)鏈表中表結(jié)點(diǎn)的個(gè)數(shù)。（3）在有向圖的鄰接鏈表中，第i個(gè)鏈表中的表結(jié)點(diǎn)的個(gè)數(shù)只是頂點(diǎn)vi的出度。如果要統(tǒng)計(jì)vi的入度，必須掃描整個(gè)鄰接表，顯然比較費(fèi)時(shí)間?？梢粤硗庠俳⒁粋€(gè)逆鄰接表，使第i個(gè)鏈表表示以vi為頭的所有的弧。有向圖G2的鄰接表和逆鄰接表如圖7.6、7.7所示。121345V1V2V3∧V4∧V54∧25∧35∧圖7.6有向圖G2的鄰接表表示（4）在鄰接表中，若要判斷兩個(gè)頂點(diǎn)vi和vj之間是否有邊或弧相連，需要遍歷第i個(gè)或第j個(gè)單鏈表，不如鄰接矩陣方便。【例7.2】建立有向圖的鄰接表表示法。voidcreate_ALgraph(ALgraph

g,inte)/*建立有向圖的鄰接表，e為弧的數(shù)目*/{for(i=1;i<=VEX_NUM;i++)/*結(jié)點(diǎn)下標(biāo)從1開(kāi)始*/{scanf("%d",&g[i].data);/*輸入表結(jié)點(diǎn)的信息*/g[i].firstarc=NULL;}for(k=1;k<=e;k++)/*建立邊表*/{scanf("%d,%d",&i,&j);/*輸入邊的弧尾和弧頭*/p=(struct

arcnode*)malloc(sizeof(struct

arcnode));p->adjvex=j;p->nextarc=g[i].firstarc;/*插入下標(biāo)為i的邊表的第一個(gè)結(jié)點(diǎn)的位置*/g[i].firstarc=p;}}圖的遍歷就是按照某種順序依次訪(fǎng)問(wèn)圖中所有頂點(diǎn)，而且每個(gè)頂點(diǎn)僅訪(fǎng)問(wèn)一次。若圖是連通圖或強(qiáng)連通圖，則從圖中任一頂點(diǎn)出發(fā)都可以沿某一路徑找到圖中其他頂點(diǎn)，否則就不然。由于圖中每個(gè)頂點(diǎn)都可能與圖中其他頂點(diǎn)鄰接并存在回路，為了避免重復(fù)訪(fǎng)問(wèn)已訪(fǎng)問(wèn)過(guò)的頂點(diǎn)，在圖遍歷的過(guò)程中，通常要對(duì)已訪(fǎng)問(wèn)的頂點(diǎn)作標(biāo)記。圖的遍歷有兩種基本方法：深度優(yōu)先搜索和廣度優(yōu)先搜索。7.3圖的遍歷

7.3.1深度優(yōu)先搜索深度優(yōu)先搜索是指在圖中任選一個(gè)頂點(diǎn)v作為出發(fā)點(diǎn)，并訪(fǎng)問(wèn)它，將其標(biāo)記為已訪(fǎng)問(wèn)過(guò)，然后依次從頂點(diǎn)v未訪(fǎng)問(wèn)過(guò)的鄰接頂點(diǎn)w出發(fā)進(jìn)行深度優(yōu)先搜索；若頂點(diǎn)w的所有鄰接點(diǎn)均已訪(fǎng)問(wèn)過(guò)，則進(jìn)行回溯到前一個(gè)訪(fǎng)問(wèn)過(guò)的頂點(diǎn)繼續(xù)進(jìn)行深度優(yōu)點(diǎn)搜索，直到圖中相連通的所有頂點(diǎn)都被訪(fǎng)問(wèn)。如果圖中還有未訪(fǎng)問(wèn)的頂點(diǎn)，則從另一未被訪(fǎng)問(wèn)過(guò)的頂點(diǎn)出發(fā)重復(fù)上述過(guò)程，直到圖中所有頂點(diǎn)都被訪(fǎng)問(wèn)過(guò)為止。顯然這是一個(gè)遞歸的搜索過(guò)程?！纠?.3】對(duì)鄰接表存儲(chǔ)圖結(jié)構(gòu)的深度優(yōu)先搜索算法。intvisitied[VEX_NUM+1]={0};/*visited數(shù)組存頂點(diǎn)被訪(fǎng)問(wèn)否，0表示未被訪(fǎng)問(wèn)*/voiddfs(ALgraph

g,inti){printf("%3d",g[i].data);/*輸出已經(jīng)訪(fǎng)問(wèn)的結(jié)點(diǎn)信息*/visited[i]=1;/*設(shè)置標(biāo)志位訪(fǎng)問(wèn)過(guò)*/p=g[i].firstarc;/*p指向第一個(gè)邊表的結(jié)點(diǎn)*/while(p!=NULL){if(visited[p->adjvex]==0)/*從未訪(fǎng)問(wèn)過(guò)的鄰接點(diǎn)出發(fā)*/

dfs(g,p->adjvex);p=p->nextarc;/*找下一個(gè)鄰接點(diǎn)*/}}廣度優(yōu)先搜索是指在圖中任選一個(gè)出發(fā)點(diǎn)v，并訪(fǎng)問(wèn)它之后，依次訪(fǎng)問(wèn)v的各個(gè)未曾訪(fǎng)問(wèn)過(guò)的鄰接點(diǎn)；然后分別從這些鄰接點(diǎn)出發(fā)，依次訪(fǎng)問(wèn)它們的未曾訪(fǎng)問(wèn)過(guò)的鄰接點(diǎn)，直至所有頂點(diǎn)都被訪(fǎng)問(wèn)過(guò)。通常是使用隊(duì)列來(lái)存儲(chǔ)頂點(diǎn)的訪(fǎng)問(wèn)序列，先將初始頂點(diǎn)入隊(duì)列，以后每次出隊(duì)列一個(gè)元素則訪(fǎng)問(wèn)之，同時(shí)將其所有鄰接點(diǎn)順序入對(duì)列，直到隊(duì)列為空時(shí)結(jié)束廣度優(yōu)先搜索的過(guò)程。7.3.2廣度優(yōu)先搜索

【例7.4】對(duì)鄰接表存儲(chǔ)圖結(jié)構(gòu)的廣度優(yōu)先搜索算法。intvisitied[VEX_NUM+1]={0};/*visited數(shù)組存頂點(diǎn)被訪(fǎng)問(wèn)否，0表示未被訪(fǎng)問(wèn)*/voidbfs(ALgraph

g,inti){InitQueue(q);/*隊(duì)列初始化*/printf("%3d",g[i].data);/*輸出已經(jīng)訪(fǎng)問(wèn)的結(jié)點(diǎn)信息*/visited[i]=1;/*設(shè)置標(biāo)志位訪(fǎng)問(wèn)過(guò)*/InQueue(q,i);/*將i入隊(duì)列*/while(!QueueEmpty(q)){DelQueue(q,i);/*出隊(duì)列*/p=g[i].firstarc;

while(p!=NULL){if(visited(p->adjvex)==0)

{printf("%3d",g[i].data);visited[p->adjvex]=1;InQueue(q,p->adjvex);}p=p->nextarc;}}}7.3.3求圖的連通分量

求圖的連通分量是圖遍歷的一種簡(jiǎn)單應(yīng)用。當(dāng)無(wú)向圖是連通時(shí)，只需調(diào)用一次dfs（或bfs）算法，便可訪(fǎng)問(wèn)圖中的所有頂點(diǎn)。當(dāng)無(wú)向圖是非連通圖時(shí)，從圖中某頂點(diǎn)v出發(fā)遍歷圖，不能訪(fǎng)問(wèn)到圖的所有頂點(diǎn)，而只能訪(fǎng)問(wèn)到包含v所在的最大連通子圖（連通分量）中的所有頂點(diǎn)。若從非連通圖中每個(gè)連通分量中的一個(gè)頂點(diǎn)出發(fā)遍歷圖，則可求出無(wú)向圖的所有連通分量?！纠?.5】對(duì)鄰接表存儲(chǔ)結(jié)構(gòu)的圖通過(guò)深度優(yōu)先搜索算法實(shí)現(xiàn)求非連通圖的連通分量的算法。intvisitied[VEX_NUM+1]={0};/*visited數(shù)組存頂點(diǎn)被訪(fǎng)問(wèn)否，0表示未被訪(fǎng)問(wèn)*/voidcon(ALgraphg){count=0;/*非連通圖的連通分量的個(gè)數(shù)*/for(i=1;i<=VEX_NUM;i++)

if(!visited(i)){count++;dfs(g,i);/*調(diào)用深度優(yōu)先搜索算法*/}

printf("\n共有%d個(gè)連通分量。\n",count);}7.4圖的生成樹(shù)

7.4.1生成樹(shù)的概念對(duì)于連通圖或強(qiáng)連通圖，從任一頂點(diǎn)出發(fā)遍歷，或是對(duì)于有根的有向圖，從圖的根頂點(diǎn)出發(fā)遍歷，可以訪(fǎng)問(wèn)到所有的頂點(diǎn)。遍歷時(shí)經(jīng)過(guò)的邊加上所有頂點(diǎn)構(gòu)成圖的一個(gè)連通子圖，稱(chēng)為圖的生成樹(shù)。圖7.8無(wú)向圖G4及生成樹(shù)7.4.2最小生成樹(shù)在邊賦權(quán)圖中，權(quán)值總和最小的生成樹(shù)稱(chēng)為最小生成樹(shù)。比如，我們要建一個(gè)能連接5幢大樓的局域網(wǎng)絡(luò)，經(jīng)過(guò)初步測(cè)量后，得到了各樓之間的距離如圖7.9所示。其中邊上的權(quán)值表示樓間的距離。如果能找出這張圖的最小生成樹(shù)，就可以用最少的網(wǎng)絡(luò)連線(xiàn)連接5幢大樓，完成局域網(wǎng)絡(luò)的構(gòu)建。圖7.9邊賦權(quán)圖G5及鄰接矩陣31359867396132547.4.3普里姆（Prim）算法和克魯斯卡爾(Kruskal)算法

1．普里姆（Prim）算法Prim算法的時(shí)間主要花費(fèi)在選擇最小生成樹(shù)的n-1條邊上。整個(gè)算法的時(shí)間復(fù)雜度是O(n2)。2．克魯斯卡爾（Kruskal）算法Kruskal算法是根據(jù)邊的權(quán)值以遞增的方式逐漸建立最小生成樹(shù)的方法。與Prim算法不同，Kruskal算法在一開(kāi)始就把所有頂點(diǎn)都放到最小生成樹(shù)中。每次循環(huán)只根據(jù)MST性質(zhì)，選擇一條合適的邊加到最小生成樹(shù)，直到?jīng)]有合適的邊為止。7.5圖的應(yīng)用

圖有很多實(shí)際的應(yīng)用，在此僅介紹拓?fù)渑判?、關(guān)鍵路徑和最短路徑問(wèn)題。拓?fù)渑判蜓芯康氖枪こ淌欠耥樌M(jìn)行；關(guān)鍵路徑討論的是工程能否縮短工期，提前完工；最短路徑商討的是如何降低工程成本。7.5.1拓?fù)渑判?/p>

1．AOV網(wǎng)AOV網(wǎng)不能有回路，否則工程無(wú)法進(jìn)行，稱(chēng)為死鎖。如圖7.13所示，A、B、C三個(gè)活動(dòng)互為其他活動(dòng)能進(jìn)行下去的前提，所以哪個(gè)活動(dòng)也不能繼續(xù)下去，造成死鎖。在實(shí)際應(yīng)用中應(yīng)避免死鎖現(xiàn)象的發(fā)生。ACB圖7.13

帶回路的AOV圖2．拓?fù)渑判驅(qū)τ谝粋€(gè)AOV網(wǎng)，其所有頂點(diǎn)可以排成一個(gè)線(xiàn)性序列，該序列具有以下的性質(zhì)：如果在AOV網(wǎng)中，從頂點(diǎn)vi到頂點(diǎn)vj存在一條路徑，則在線(xiàn)性序列中，頂點(diǎn)vi一定排在頂點(diǎn)vj之前。具有這樣性質(zhì)的線(xiàn)性序列稱(chēng)為拓?fù)湫蛄?，?gòu)造拓?fù)湫蛄械牟僮鞣Q(chēng)為拓?fù)渑判颉?.5.2關(guān)鍵路徑

AOE網(wǎng)是另一類(lèi)系統(tǒng)工程中經(jīng)常使用的圖的模型，使用該模型可以很方便地分析和計(jì)算工程中的關(guān)鍵路徑，從而可以有效地實(shí)現(xiàn)對(duì)工程進(jìn)度的管理。1．AOE網(wǎng)

一個(gè)有向圖可以用來(lái)估算工程的計(jì)劃完成時(shí)間，這時(shí)它的頂點(diǎn)表示事件，邊表示活動(dòng)，邊上權(quán)值表示活動(dòng)持續(xù)的時(shí)間。這樣帶權(quán)的有向圖稱(chēng)為AOE網(wǎng)。頂點(diǎn)表示的事件實(shí)際上就是它的入邊所表示的活動(dòng)已完成，它的出邊所表示的活動(dòng)可以開(kāi)始的一種狀態(tài)。2．關(guān)鍵路徑

AOE網(wǎng)中有些活動(dòng)可以并行進(jìn)行，所以完成整個(gè)工程的最短時(shí)間是從開(kāi)始頂點(diǎn)到完成頂點(diǎn)的最長(zhǎng)路徑長(zhǎng)度，路徑長(zhǎng)度為路徑上各邊的權(quán)值之和。從源點(diǎn)到匯點(diǎn)最長(zhǎng)的帶權(quán)路徑稱(chēng)為關(guān)鍵路徑，關(guān)鍵路徑的帶權(quán)路徑長(zhǎng)度是完成整個(gè)工程的最短時(shí)間。（1）事件最早發(fā)生時(shí)間（ve）事件最早發(fā)生時(shí)間是從源點(diǎn)到該事件頂點(diǎn)的最長(zhǎng)路徑長(zhǎng)度。計(jì)算方法為：

ve(v1)=0ve(vj)=max{ve(vi)+weight(<vi,vj>)}（2）事件最遲發(fā)生時(shí)間（le）最遲發(fā)生時(shí)間等于匯點(diǎn)最早發(fā)生時(shí)間減去該頂點(diǎn)到匯點(diǎn)的最長(zhǎng)帶權(quán)路徑長(zhǎng)度。比如事件E，最遲發(fā)生時(shí)間le(v5)=18-11=7。計(jì)算方法為：

le(vn)=ve(vn)le(vi)=min{le(vj)-weight(<vi,vj>)}（3）活動(dòng)最早開(kāi)始時(shí)間（e）（4）活動(dòng)最晚開(kāi)始時(shí)間

7.5.2最短路徑

假設(shè)有一張地區(qū)圖，如圖7.16所示，邊上的權(quán)值表示城市之間的距離。我們討論兩種最常見(jiàn)的最短路徑問(wèn)題。601050101000123455

3020圖7.16

賦權(quán)有向圖1．單源頂點(diǎn)最短路徑問(wèn)題求解2．求有向網(wǎng)中每對(duì)頂點(diǎn)間的路徑7.6圖的算法C語(yǔ)言程序?qū)崿F(xiàn)舉例

7.7.1無(wú)向圖的鄰接表的建立和遍歷7.7.2有向無(wú)環(huán)圖的拓?fù)渑判蚝颓箨P(guān)鍵路徑1．有向無(wú)環(huán)圖的拓?fù)渑判?．有向無(wú)環(huán)圖的關(guān)鍵路徑1.填空題（1）有向圖G用鄰接矩陣存儲(chǔ)，其第i行的所有元素之和等于頂點(diǎn)i的

。（2）圖的逆鄰接表存儲(chǔ)結(jié)構(gòu)只適用于

圖。（3）圖的深度優(yōu)先遍歷序列

唯一的。（4）圖的BFS生成樹(shù)的樹(shù)高比DFS生成樹(shù)的數(shù)高

。（5）拓?fù)渑判蜉敵龅捻旤c(diǎn)數(shù)小于有向圖的頂點(diǎn)數(shù)，則該圖一定存在

。（6）若要求一個(gè)稀疏圖G的最小生成樹(shù)，最好用

算法來(lái)求解。習(xí)題72.選擇題（1）在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的（）倍。A.1/2B.1C.2D.4（2）用鄰接表表示圖進(jìn)行廣度優(yōu)先遍歷時(shí)，通常采用（）來(lái)實(shí)現(xiàn)算法。A.棧B.隊(duì)列C.樹(shù)D.圖（3）具有n個(gè)頂點(diǎn)的無(wú)向完全圖，邊的總數(shù)為（）。A.nB.n+1C.2n-1D.n(n-1)/2（4）有n個(gè)頂點(diǎn)的連通圖G的最小生成樹(shù)有（）條邊。A.n-1B.nC.n+1D.不確定（5）一個(gè)有向無(wú)環(huán)圖的拓?fù)湫蛄袀€(gè)數(shù)是（）。A.