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

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

E(G)是關系的有限集合，關系是頂點的無序對或有序對有向圖——有向圖G是由兩個集合V(G)和E(G)組成

V(G)是頂點的非空有限集，E(G)是有向邊（也稱?。┑挠邢藜希∈琼旤c的有序對，記為<vi,vj>，vi,vj是頂點，vi為弧尾，vj為弧頭無向圖——無向圖G是由兩個集合V(G)和E(G)組成

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

點的無序對，記為（vi,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圖的定義和術語在G1中，連線上有箭頭表示方向，則該連線稱為弧。我們可以用<v1,v2>表示一條弧，v1稱為弧尾，v2稱為弧頭。相應的，圖G1稱為有向圖。v1v2v3v4v1v2v3v4v5v1v2v4v3v5v616662345圖G1圖G2圖G37.1圖的定義和術語在G2中，沒有箭頭的連線稱為邊。圖G2稱為無向圖。v1v2v3v4v1v2v3v4v5v1v2v4v3v5v616662345圖G1圖G2圖G37.1圖的定義和術語在G3中，連線上標有與之相關聯(lián)的數值（稱為權），這種形式的圖通常稱為網。v1v2v3v4v1v2v3v4v5v1v2v4v3v5v616662345圖G1圖G2圖G37.1圖的定義和術語有n個頂點，且每兩個頂點之間均有邊的無向圖，稱為完全圖。完全圖共有n*（n-1）/2條邊。幾個完全圖的例子如下：v1v2v3v4v1v1v2v1v2v37.1圖的定義和術語有n個頂點，且每兩個頂點之間均有邊的有向圖，稱為有向完全圖。有向完全圖共有n*（n-1）條邊。幾個有向完全圖的例子如下：v1v2v3v4v1v1v2v1v2v3子圖——如果圖G(V,E)和圖G’(V’,E’),滿足：V’V，E’E

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

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

數據對象V：V是具有相同特性的數據元素的集合，稱為頂點集。數據關系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及相關的弧

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

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

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

mg.arcnum=mg.vexnum=0;//頂點和邊的數目均為0 for(inti=1;i<100;i++) for(intj=1;j<100;j++) mg.arcs[i][j]=0;//各個頂點之間初始情況下沒有邊相連}二、用c語言描述圖的存儲結構及其操作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語言描述圖的存儲結構及其操作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語言描述圖的存儲結構及其操作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語言描述圖的存儲結構及其操作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語言描述圖的存儲結構及其操作2.基本操作intFirstAdjVex(MGraphmg,intv){//在圖mg中，求頂點v的第一個鄰接點 //使用頂點的下標代替字符串，

//如頂點“v1“對應下標為v,則使用v代表“v1“

for(inti=1;i<=mg.vexnum;i++){if(mg.arcs[v][i]!=0) returni; } return0;//不存在鄰接點時，返回0}二、用c語言描述圖的存儲結構及其操作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語言描述圖的存儲結構及其操作2.基本操作對于左圖，可以用右面代碼來構造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^思考：根據右圖1.如何求v1的出度、入度、以v1為弧尾的鄰接點？2.如何求圖中共有幾條邊？7.2.2鄰接表表示法一、舉例說明鄰接表表示法1.有向圖1v12v2^3v34v42^3^4^1^思考：1.如何求v1的出度、入度、以v1為弧尾的鄰接點？解答：v1的出度是v1后面鏈表的長度。

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

doubleweight;//邊的信息(權)

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

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

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

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

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;//表結點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;//該頂點已經存在

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)//邊不存在

{//此時我們假定頂點已經存在

ArcNode*p=newArcNode;//定義表結點

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

intv=FindVex(mg,v1);

//新結點作為鏈表第一個結點

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

//使用頂點的下標代替字符串，如頂點“v1”對應下標為v,//則使用v代表“v1”,假定v存在

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