第7章1(7172圖的定義及存儲結(jié)構(gòu))

第7章圖本章教學(xué)目的與要求：掌握圖的基本概念、存儲方法、基本操作。掌握與圖相關(guān)的一些算法，如遍歷、最短路徑、最小生成樹等。7.1圖的定義和術(shù)語圖的實例其中用圓圈標(biāo)示的是數(shù)據(jù)元素，在圖中稱為頂點。v1v2v3v4v1v2v3v4v5v1v2v4v3v5v616662345圖G1圖G2圖G37.1圖的定義和術(shù)語頂點之間的連線，表示數(shù)據(jù)元素之間的關(guān)系。v1v2v3v4v1v2v3v4v5v1v2v4v3v5v616662345圖G1圖G2圖G32023/2/44圖(Graph)——圖G是由兩個集合V(G)和E(G)組成

的,記為G=(V,E)其中：V(G)是頂點的非空有限集

E(G)是關(guān)系的有限集合，關(guān)系是頂點的無序?qū)蛴行驅(qū)τ邢驁D——有向圖G是由兩個集合V(G)和E(G)組成

V(G)是頂點的非空有限集，E(G)是有向邊（也稱弧）的有限集合，弧是頂點的有序?qū)?，記?lt;vi,vj>，vi,vj是頂點，vi為弧尾，vj為弧頭無向圖——無向圖G是由兩個集合V(G)和E(G)組成

V(G)是頂點的非空有限集，E(G)是邊的有限集合，邊是頂

點的無序?qū)Γ洖椋╲i,vj）或（vj,vi)，并且（vi,vj)=(vj,vi)

圖的概念v1v2v3v4v1v2v3v4v5圖G1圖G2G1=(V1,{A1})其中，V1={v1,v2,v3.v4}A1={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}G2=(V2,{E2})其中，V2={v1,v2,v3.v4,v5}E2={(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5)}7.1圖的定義和術(shù)語在G1中，連線上有箭頭表示方向，則該連線稱為弧。我們可以用<v1,v2>表示一條弧，v1稱為弧尾，v2稱為弧頭。相應(yīng)的，圖G1稱為有向圖。v1v2v3v4v1v2v3v4v5v1v2v4v3v5v616662345圖G1圖G2圖G37.1圖的定義和術(shù)語在G2中，沒有箭頭的連線稱為邊。圖G2稱為無向圖。v1v2v3v4v1v2v3v4v5v1v2v4v3v5v616662345圖G1圖G2圖G37.1圖的定義和術(shù)語在G3中，連線上標(biāo)有與之相關(guān)聯(lián)的數(shù)值（稱為權(quán)），這種形式的圖通常稱為網(wǎng)。v1v2v3v4v1v2v3v4v5v1v2v4v3v5v616662345圖G1圖G2圖G37.1圖的定義和術(shù)語有n個頂點，且每兩個頂點之間均有邊的無向圖，稱為完全圖。完全圖共有n*（n-1）/2條邊。幾個完全圖的例子如下：v1v2v3v4v1v1v2v1v2v37.1圖的定義和術(shù)語有n個頂點，且每兩個頂點之間均有邊的有向圖，稱為有向完全圖。有向完全圖共有n*（n-1）條邊。幾個有向完全圖的例子如下：v1v2v3v4v1v1v2v1v2v3子圖——如果圖G(V,E)和圖G’(V’,E’),滿足：V’V，E’E

則稱G’為G的子圖24513635621v1v3v4v2v1v3v2v3v47.1圖的定義和術(shù)語7.1圖的定義和術(shù)語在無向圖中，若(v,w)是一條邊，(v,w)∈E則v,w互為鄰接點uvw7.1圖的定義和術(shù)語在無向圖中，頂點v的度是指與v相連的邊的條數(shù)。uvw7.1圖的定義和術(shù)語在有向圖中，頂點v的出度是指v作為弧尾的弧的條數(shù)。記為OD(v)uvw7.1圖的定義和術(shù)語在有向圖中，頂點v的入度是指v作為弧頭的弧的條數(shù)。記為ID(v)uvw7.1圖的定義和術(shù)語在有向圖中，頂點v的度是指v的入度和出度之和。記為TD(v)TD(v)=ID(v)+OD(v)uvw7.1圖的定義和術(shù)語頂點v到頂點w的路徑指從v出發(fā)沿著邊或者弧到達(dá)w所經(jīng)過的頂點序列。如上圖中v-v2-w是從v到w的一條路經(jīng)路徑上邊或者弧的數(shù)目稱為路徑的長度。序列中頂點不重復(fù)的路徑稱為簡單路徑vv2v3v4w7.1圖的定義和術(shù)語第一個頂點和最后一個頂點相同的路徑稱為回路或者環(huán)。路徑v-v2-v3-v4-v就是一條回路除第一個頂點和最后一個頂點之外，其余頂點不重復(fù)出現(xiàn)的回路，稱為簡單回路或者簡單環(huán)vv2v3v4w7.1圖的定義和術(shù)語在無向圖中，如果從v到w之間有路徑，則稱頂點v和頂點w是連通的。如果圖中任意兩個頂點都是連通的，則稱該圖為連通圖。vv2v3v4w連通圖7.1圖的定義和術(shù)語上圖看作一個整體，不是連通圖。v1v2v3v4v5v6v77.1圖的定義和術(shù)語無向圖中的一個極大連通子圖，稱為該圖的連通分量。v1v2v3v4v5v6v3v6v1v2v4v52個連通分量G0上圖G0不是連通圖，有兩個連通分量.強(qiáng)連通圖——有向圖中，如果對每一對Vi,VjV,ViVj,從Vi到Vj

和從Vj到Vi都存在路徑，則稱G是強(qiáng)連通圖強(qiáng)連通圖356245136非強(qiáng)連通圖7.1圖的定義和術(shù)語v1v2v3v4v5v1v2v3v47.1圖的定義和術(shù)語上圖G1不是強(qiáng)連通圖，有兩個強(qiáng)連通分量：G1-1和G1-2v1v2v3v4圖G1v1v3v4圖G1-1v2圖G1-2有向圖中的極大強(qiáng)連通子圖稱為有向圖的強(qiáng)連通分量。7.1圖的定義和術(shù)語連通圖的生成樹是一個極小連通子圖。生成樹中包含圖的全部頂點（假定為n個），包含能夠連接起n個頂點的n-1條邊，使得生成樹也是一個連通圖。如上面圖G2-1為圖G2的一棵生成樹。v1v2v3v4v5圖G2v1v2v3v4v5圖G2-12023/2/425一個連通圖的生成樹是一個極小連通子圖，它含有圖中全部頂點，但只有足以構(gòu)成一棵樹的n-1條邊。一棵有n個頂點的生成樹有且僅有n-1條邊。15732461573246連通圖生成樹26抽象數(shù)據(jù)類型---圖ADTGraph{

數(shù)據(jù)對象V：V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點集。數(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：

GraphCreat(G,，V，VR)；//創(chuàng)建圖

GraphDestory(G)；//銷毀圖

GraphLocateVertex(G，v)；//尋找頂點v

GraphGetVertex(G，v)；//返回頂點v的值

GraphPutVertex(&G，v,value)；//為頂點v賦值

GraphFirstAdjVex(G，v)；//返回v的第一個鄰接頂點

GraphNextAdjVex(G，v，w)；//返回v的下一個鄰接頂點

GraphInsertVertex(G，v)；//在圖中添加新頂點v

GraphDeleteVertex(G，v)；//刪除頂點v及相關(guān)的弧

GraphInsertArc(G，v，w)；//在圖中增加弧<v,w>

GraphDeleteArc(G，v，w)；//刪除圖中v和w之間的弧

DFSTtraverse(G，v，Visit())；//深度優(yōu)先遍歷

BFSTtraverse(G，v，Visit())；//廣度優(yōu)先遍歷

}ADTGraph

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

由于圖的頂點之間存在多對多的關(guān)系，因此，圖的存儲結(jié)構(gòu)相應(yīng)的比較復(fù)雜。本節(jié)我們介紹兩種最常用的存儲結(jié)構(gòu)，鄰接矩陣表示法(數(shù)組表示法)和鄰接表表示法。十字鏈表表示法鄰接多重表表示法7.2.1鄰接矩陣表示法（數(shù)組表示法）用一個一維數(shù)組存儲頂點的信息。用一個二維數(shù)組存儲數(shù)據(jù)元素之間關(guān)系(邊或弧)的信息，這種表示方法我們稱之為鄰接矩陣法。7.2.1鄰接矩陣表示法（數(shù)組表示法）一、舉例說明鄰接矩陣表示法1.有向圖v1v2v3v4圖G1v1v2v3v4邊信息數(shù)組arcsv1v2v3v4v1v2v3v4頂點信息數(shù)組vexs7.2.1鄰接矩陣表示法（數(shù)組表示法）v1v2v3v4圖G1v1v2v3v4邊信息數(shù)組arcsv1v2v3v4v10110v20000v30001v41000頂點信息數(shù)組vexs7.2.1鄰接矩陣表示法（數(shù)組表示法）v1v2v3v4圖G1v1v2v3v4邊信息數(shù)組arcsv1v2v3v4v10110v20000v30001v41000思考：（1）如何從arcs尋找v1的出度、入度，鄰接點；（2）是否能從arcs判斷該圖是否有向圖。頂點信息數(shù)組vexs7.2.1鄰接矩陣表示法（數(shù)組表示法）邊信息數(shù)組arcsv1v2v3v4v10110v20000v30001v41000解答：（1）如何從arcs尋找v1的出度、入度，鄰接點；V1行所有1的個數(shù)為v1的出度；V1列所有1的個數(shù)為v1的入度；V1行所有1對應(yīng)的下標(biāo)在vexs中對應(yīng)的頂點。（2）能否從arcs判斷該圖的類型，（有向圖還是無向圖）。當(dāng)arcs數(shù)組關(guān)于主對角線不對稱時，可以肯定其是有向圖。否則不能判定。7.2.1鄰接矩陣表示法（數(shù)組表示法）2.無向圖v1v2v3v4v5邊信息數(shù)組arcsv1v2v3v4v5v1v2v3v4v5頂點信息數(shù)組vexsv1v2v3v4v5圖G27.2.1鄰接矩陣表示法（數(shù)組表示法）v1v2v3v4v5邊信息數(shù)組arcsv1v2v3v4v5v101010v210101v301011v41010001100v5頂點信息數(shù)組vexsv1v2v3v4v5圖G27.2.1鄰接矩陣表示法（數(shù)組表示法）思考：（1）如何從arcs尋找v1的度，鄰接點；（2）是否能從arcs判斷該圖是否有向圖。v1v2v3v4v5邊信息數(shù)組arcsv1v2v3v4v5v101010v210101v301011v41010001100v5頂點信息數(shù)組vexsv1v2v3v4v5圖G27.2.1鄰接矩陣表示法（數(shù)組表示法）解答：（1）如何從arcs尋找v1的度，鄰接點；V1行所有1的個數(shù)為v1的度；V1行所有1對應(yīng)的下標(biāo)在vexs中對應(yīng)的頂點。（2）能否從arcs判斷該圖的類型，（有向圖還是無向圖）。當(dāng)arcs數(shù)組關(guān)于主對角線不對稱時，可以肯定其是有向圖。否則不能判定。邊信息數(shù)組arcsv1v2v3v4v5v101010v210101v301011v41010001100v57.2.1鄰接矩陣表示法（數(shù)組表示法）3.網(wǎng)v1v2v3v4v5v61555346798v1v2v3v4v5v6頂點信息數(shù)組vexs7.2.1鄰接矩陣表示法（數(shù)組表示法）v1v2v3v4v5v61555346798邊信息數(shù)組arcsv1v2v3v4v5v6v157v24v389v4565v5v631二、用c語言描述圖的存儲結(jié)構(gòu)及其操作1.存儲結(jié)構(gòu)為了簡單起見，我們假設(shè)頂點所代表數(shù)據(jù)的數(shù)據(jù)類型是字符串，如“v1”、“v2”等；考慮到頂點之間的邊上可能帶有權(quán)值，則鄰接矩陣的類型設(shè)為double。當(dāng)然大家可以根據(jù)應(yīng)用問題的不同，適當(dāng)調(diào)整數(shù)據(jù)類型。structMGraph{ char*vexs[100];//存儲頂點信息

doublearcs[100][100];//存儲邊的信息

intvexnum,arcnum;//頂點數(shù)目和邊的數(shù)目};二、用c語言描述圖的存儲結(jié)構(gòu)及其操作2.基本操作圖的基本操作包括圖的初始化、查找頂點是否存在、查找邊是否存在、插入一個頂點，插入一條邊，刪除一個頂點，刪除一條邊，求頂點的鄰接點等。voidInitGraph(MGraph&mg){//圖的初始化

mg.arcnum=mg.vexnum=0;//頂點和邊的數(shù)目均為0 for(inti=1;i<100;i++) for(intj=1;j<100;j++) mg.arcs[i][j]=0;//各個頂點之間初始情況下沒有邊相連}二、用c語言描述圖的存儲結(jié)構(gòu)及其操作2.基本操作intFindVex(MGraphmg,char*vex){//查找頂點vex是否存在

for(inti=1;i<=mg.vexnum;i++){ if(strcmp(mg.vexs[i],vex)==0) returni;//頂點存在，返回i } return0;//頂點不存在，返回0}二、用c語言描述圖的存儲結(jié)構(gòu)及其操作2.基本操作intFindArc(MGraphmg,char*v1,char*v2){//查找邊或弧<v1,v2>是否存在

intx,y; x=FindVex(mg,v1); y=FindVex(mg,v2); if(x==0||y==0)return0;//某個頂點不存在,邊肯定不存在，返回0 if(mg.arcs[x][y]==1)return1;//邊存在，返回1}二、用c語言描述圖的存儲結(jié)構(gòu)及其操作2.基本操作voidInsertVex(MGraph&mg,char*vex){//插入一個頂點vex

if(FindVex(mg,vex)==0)//頂點不存在

{ mg.vexnum++;

mg.vexs[mg.vexnum]=newchar[strlen(vex)]; strcpy(mg.vexs[mg.vexnum],vex);//新頂點加入

}}二、用c語言描述圖的存儲結(jié)構(gòu)及其操作2.基本操作voidInsertArc(MGraph&mg,char*v1,char*v2){//插入一條邊或弧<v1,v2> intx,y; x=FindVex(mg,v1); y=FindVex(mg,v2);

if(x&&y){mg.arcs[x][y]=1; mg.arcnum++; }}二、用c語言描述圖的存儲結(jié)構(gòu)及其操作2.基本操作intFirstAdjVex(MGraphmg,intv){//在圖mg中，求頂點v的第一個鄰接點 //使用頂點的下標(biāo)代替字符串，

//如頂點“v1“對應(yīng)下標(biāo)為v,則使用v代表“v1“

for(inti=1;i<=mg.vexnum;i++){if(mg.arcs[v][i]!=0) returni; } return0;//不存在鄰接點時，返回0}二、用c語言描述圖的存儲結(jié)構(gòu)及其操作2.基本操作intNextAdjVex(MGraphmg,intv,intw){//在圖mg中，求頂點v的相對于頂點w的下一個鄰接點

for(inti=w+1;i<=mg.vexnum;i++) if(mg.arcs[v][i]!=0) returni; return0;}二、用c語言描述圖的存儲結(jié)構(gòu)及其操作2.基本操作對于左圖，可以用右面代碼來構(gòu)造v1v2v3v4圖G1intmain(intargc,char*argv[]){MGraphmg;InitGraph(mg);//圖的初始化

InsertVex(mg,"v1");//插入頂點

InsertVex(mg,"v2"); InsertVex(mg,"v3"); InsertVex(mg,"v4"); InsertArc(mg,"v1","v2");//插入邊

InsertArc(mg,"v1","v3"); InsertArc(mg,"v3","v4"); InsertArc(mg,"v4","v1");return0;}7.2.2鄰接表表示法一、舉例說明鄰接表表示法1.有向圖v1v2v3v4圖G11v12v2^3v34v42^3^4^1^思考：根據(jù)右圖1.如何求v1的出度、入度、以v1為弧尾的鄰接點？2.如何求圖中共有幾條邊？7.2.2鄰接表表示法一、舉例說明鄰接表表示法1.有向圖1v12v2^3v34v42^3^4^1^思考：1.如何求v1的出度、入度、以v1為弧尾的鄰接點？解答：v1的出度是v1后面鏈表的長度。

V1的入度為所有鏈表中數(shù)據(jù)域為1的結(jié)點的個數(shù)。V1的鄰接點就是v1后鏈表上的所有結(jié)點。2.如何求圖中共有幾條邊？所有鏈表中所有結(jié)點的個數(shù)。7.2.2鄰接表表示法一、舉例說明鄰接表表示法2.無向圖1v12v23v34v45v524^41v1v2v3v4v5圖G2135^25^3^23^思考：根據(jù)右圖1.如何求v1的度、v1的鄰接點？2.如何求圖中共有幾條邊？7.2.2鄰接表表示法一、用c語言描述圖的鄰接表存儲結(jié)構(gòu)及其操作1.存儲結(jié)構(gòu)從上面的例子可以看出，鄰接表中存在兩種結(jié)點，一種是鏈表的頭結(jié)點，用來存儲頂點信息；一種是表結(jié)點，用來存放鄰接點以及邊的信息。1v12v23v34v45v524^41135^25^3^23^7.2.2鄰接表表示法一、用c語言描述圖的鄰接表存儲結(jié)構(gòu)及其操作1v12v23v34v45v524^41135^25^3^23^datafirstarc表頭結(jié)點：頂點信息指向第1個鄰接點的指針表結(jié)點adjvexinfonextarc鄰接點邊或弧的信息（如權(quán)值）指向下一條邊或弧的結(jié)點7.2.2鄰接表表示法一、用c語言描述圖的鄰接表存儲結(jié)構(gòu)及其操作//表結(jié)點-結(jié)構(gòu)體類型structArcNode{ intadjvex;//鄰接點

doubleweight;//邊的信息(權(quán))

ArcNode*nextarc;//指向下一條邊的指針};7.2.2鄰接表表示法一、用c語言描述圖的鄰接表存儲結(jié)構(gòu)及其操作//頭結(jié)點-結(jié)構(gòu)體類型typedefstructVexNode{ chardata[5];//頂點信息（字符串）

ArcNode*firstarc;//指向第一條邊的指針}VexNode;//圖-結(jié)構(gòu)體類型typedefstruct{ VexNodevexs[100];//頂點的集合

intvexnum,arcnum;//頂點的數(shù)目，邊的數(shù)目}ALGraph;7.2.2鄰接表表示法一、用c語言描述圖的鄰接表存儲結(jié)構(gòu)及其操作

圖的基本操作包括圖的初始化、查找頂點是否存在、查找邊是否存在、插入一個頂點，插入一條邊，刪除一個頂點，刪除一條邊，求頂點的鄰接點等。

voidInitGraph(ALGraph&mg){//圖的初始化

mg.arcnum=mg.vexnum=0; for(inti=1;i<100;i++) { strcpy(mg.vexs[i].data,""); mg.vexs[i].firstarc=0; }}intFindVex(ALGraphmg,char*vex){//查找頂點vex是否存在

for(inti=1;i<=mg.vexnum;i++) if(strcmp(mg.vexs[i].data,vex)==0) returni; return0;//不存在}intFindArc(ALGraphmg,char*v,char*w){//查找邊或弧<v,w>是否存在

intv1=FindVex(mg,v); intw1=FindVex(mg,w); if(v1*w1==0)return0;//不存在

ArcNode*p=mg.vexs[v1].firstarc;//表結(jié)點p

while(p) { if(p->adjvex==w1)return1;//找到了

p=p->nextarc;//指向下一條邊(下一個鄰接點) } return0;//不存在 }voidInsertVex(ALGraph&mg,char*vex){//插入一個頂點vex intv=FindVex(mg,vex);

if(v!=0)return;//該頂點已經(jīng)存在

mg.vexnum++; strcpy(mg.vexs[mg.vexnum].data,vex);return; }voidInsertArc(ALGraph&mg,char*v1,char*v2){//插入一條邊或弧<v1,v2>

if(FindArc(mg,v1,v2)==0)//邊不存在

{//此時我們假定頂點已經(jīng)存在

ArcNode*p=newArcNode;//定義表結(jié)點

//生成一個新的結(jié)點p->adjvex=FindVex(mg,v2); p->nextarc=0; p->weight=0;

intv=FindVex(mg,v1);

//新結(jié)點作為鏈表第一個結(jié)點

p->nextarc=mg.vexs[v].firstarc; mg.vexs[v].firstarc=p; }}intFirstAdjVex(ALGraphmg,intv){//在圖mg中，求頂點v的第一個鄰接點

//使用頂點的下標(biāo)代替字符串，如頂點“v1”對應(yīng)下標(biāo)為v,//則使用v代表“v1”,假定v存在

if(mg.vexs[v].firstarc!=0) returnmg.vexs[v].firstarc->adjvex; elsereturn0; }intNextAdjVex(ALGraphmg,intv,intw