(13)第六章 圖及其存儲(chǔ)結(jié)構(gòu)

1、1第六 章 圖定義、概念、存儲(chǔ)結(jié)構(gòu)、輸入2圖圖(Graph)的的ADT定義：定義：圖圖是是n( n0 0 )個(gè)個(gè)結(jié)點(diǎn)的有限集結(jié)點(diǎn)的有限集合。在任意一個(gè)圖中合。在任意一個(gè)圖中任意兩個(gè)結(jié)點(diǎn)之間都可能相關(guān)任意兩個(gè)結(jié)點(diǎn)之間都可能相關(guān)。圖。圖的的ADT定義如下：定義如下：一、基本概念一、基本概念數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象V： V是具有相同特性的數(shù)據(jù)元素的集合，并稱(chēng)為頂點(diǎn)集是具有相同特性的數(shù)據(jù)元素的集合，并稱(chēng)為頂點(diǎn)集合。合。數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系R： R=E E=|v,wV , （或（或（v, w)表示從表示從v到到w的弧的弧 (或邊）或邊）,且有函數(shù)且有函數(shù) P(v,w)定義了弧定義了弧上的信息或權(quán)值上的信息或權(quán)值基本

2、操作基本操作P： 詳見(jiàn)詳見(jiàn) P127圖的二元組表示：圖的二元組表示：G=(V，E)E即為圖中邊或弧的集合。即為圖中邊或弧的集合。3圖的有關(guān)術(shù)語(yǔ)：圖的有關(guān)術(shù)語(yǔ)：一、基本概念一、基本概念 圖中的數(shù)據(jù)元素稱(chēng)為圖中的數(shù)據(jù)元素稱(chēng)為頂點(diǎn)；頂點(diǎn)； 有向圖；有向圖； 弧；?。?弧頭；弧頭； 弧尾；弧尾； 無(wú)向圖；無(wú)向圖； 邊；邊； *定理定理：若用：若用e表示有向圖或無(wú)向圖中弧或邊的條數(shù)，表示有向圖或無(wú)向圖中弧或邊的條數(shù)，即即e=|E|,則有：則有： 在有向圖中：在有向圖中： 0en(n-1) 在無(wú)向圖中：在無(wú)向圖中： 0en(n-1)/2 具有具有n(n-1)/2條邊的無(wú)向圖稱(chēng)為條邊的無(wú)向圖稱(chēng)為無(wú)向無(wú)向完全

3、圖：完全圖： 具有具有n(n-1)條邊的有向圖稱(chēng)為條邊的有向圖稱(chēng)為有向完全圖：有向完全圖：abcd01234圖的有關(guān)術(shù)語(yǔ)：圖的有關(guān)術(shù)語(yǔ)：一、基本概念一、基本概念頂點(diǎn)的度；頂點(diǎn)的度； 有向圖中頂點(diǎn)的度有向圖中頂點(diǎn)的度是該頂點(diǎn)的是該頂點(diǎn)的入度入度與與出度出度之和之和。 無(wú)向圖中頂點(diǎn)的度無(wú)向圖中頂點(diǎn)的度是與該是與該頂點(diǎn)頂點(diǎn)相關(guān)聯(lián)的邊的條數(shù)相關(guān)聯(lián)的邊的條數(shù)。 子圖：子圖：對(duì)于對(duì)于G1=(V1,E1),G2=(V2,E2),若若V2 V1，E2 E1，則稱(chēng)，則稱(chēng)G2是是G1的子圖。的子圖。 回路（環(huán)）：回路（環(huán)）：若一條路徑上的頂點(diǎn)均不相同則該路徑稱(chēng)為若一條路徑上的頂點(diǎn)均不相同則該路徑稱(chēng)為簡(jiǎn)單路徑簡(jiǎn)單路

4、徑；除了除了第一頂點(diǎn)第一頂點(diǎn)和和終點(diǎn)終點(diǎn)相同外，路徑上的其他頂點(diǎn)均不相同的路徑相同外，路徑上的其他頂點(diǎn)均不相同的路徑稱(chēng)為稱(chēng)為簡(jiǎn)單回路簡(jiǎn)單回路或或簡(jiǎn)單環(huán)簡(jiǎn)單環(huán)。第一頂點(diǎn)第一頂點(diǎn)和和最后頂點(diǎn)最后頂點(diǎn)相同的路徑叫相同的路徑叫回路回路或環(huán)或環(huán)。abcd01235圖的有關(guān)術(shù)語(yǔ)：圖的有關(guān)術(shù)語(yǔ)：一、基本概念一、基本概念 無(wú)向圖中任意兩個(gè)頂點(diǎn)都是連通的，則該圖為無(wú)向圖中任意兩個(gè)頂點(diǎn)都是連通的，則該圖為連通圖連通圖。有向圖中任何有序頂點(diǎn)對(duì)之間都有有向路徑，則稱(chēng)該圖是有向圖中任何有序頂點(diǎn)對(duì)之間都有有向路徑，則稱(chēng)該圖是強(qiáng)連通的強(qiáng)連通的。無(wú)向圖中最大的連通子圖稱(chēng)為該圖的。無(wú)向圖中最大的連通子圖稱(chēng)為該圖的連通分量連通分

5、量；有向圖中相應(yīng)地稱(chēng)為有向圖中相應(yīng)地稱(chēng)為強(qiáng)連通分量強(qiáng)連通分量。abcd01236圖的有關(guān)術(shù)語(yǔ)：圖的有關(guān)術(shù)語(yǔ)：一、基本概念一、基本概念 一個(gè)連通無(wú)向圖的一個(gè)連通無(wú)向圖的生成樹(shù)生成樹(shù)是該圖的一個(gè)極小連通子圖，是該圖的一個(gè)極小連通子圖，它包含有該圖的所有它包含有該圖的所有n個(gè)頂點(diǎn)以及連接這個(gè)頂點(diǎn)以及連接這n個(gè)頂點(diǎn)的（個(gè)頂點(diǎn)的（n-1）條邊。條邊。 邊或弧上帶權(quán)值的圖稱(chēng)為邊或弧上帶權(quán)值的圖稱(chēng)為網(wǎng)網(wǎng)（分為（分為無(wú)向網(wǎng)無(wú)向網(wǎng)和和有向網(wǎng)有向網(wǎng)）。）。 一個(gè)無(wú)向圖的所有生成樹(shù)中，邊上的權(quán)值之和最小的一個(gè)無(wú)向圖的所有生成樹(shù)中，邊上的權(quán)值之和最小的生成樹(shù)稱(chēng)為該圖的生成樹(shù)稱(chēng)為該圖的最小生成樹(shù)最小生成樹(shù)或或最小代價(jià)生

6、成樹(shù)最小代價(jià)生成樹(shù)。abcdef65512564637圖的有關(guān)術(shù)語(yǔ)：圖的有關(guān)術(shù)語(yǔ)：一、基本概念一、基本概念圖中頂點(diǎn)的圖中頂點(diǎn)的“序號(hào)序號(hào)”及其鄰接點(diǎn)的及其鄰接點(diǎn)的“序號(hào)序號(hào)”： 由于圖中頂點(diǎn)之間不存在全序關(guān)系，所以無(wú)法將圖中由于圖中頂點(diǎn)之間不存在全序關(guān)系，所以無(wú)法將圖中頂點(diǎn)進(jìn)行線(xiàn)性排序。但為了實(shí)現(xiàn)圖的存儲(chǔ)結(jié)構(gòu)，我們必須頂點(diǎn)進(jìn)行線(xiàn)性排序。但為了實(shí)現(xiàn)圖的存儲(chǔ)結(jié)構(gòu)，我們必須給每個(gè)頂點(diǎn)附加一個(gè)人為規(guī)定的給每個(gè)頂點(diǎn)附加一個(gè)人為規(guī)定的“序號(hào)序號(hào)”。這個(gè)序號(hào)即稱(chēng)。這個(gè)序號(hào)即稱(chēng)為該為該頂點(diǎn)在圖中的位置頂點(diǎn)在圖中的位置。 對(duì)于任意一個(gè)頂點(diǎn)而言，若它有兩個(gè)以上的鄰接點(diǎn)，對(duì)于任意一個(gè)頂點(diǎn)而言，若它有兩個(gè)以上的鄰接點(diǎn)

7、，則它的鄰接點(diǎn)也有所謂則它的鄰接點(diǎn)也有所謂“第一個(gè)鄰接點(diǎn)第一個(gè)鄰接點(diǎn)”， “第二個(gè)鄰第二個(gè)鄰接點(diǎn)接點(diǎn)”，.，這個(gè)順序也稱(chēng)為，這個(gè)順序也稱(chēng)為鄰接順序鄰接順序。8一、基本概念一、基本概念圖的遍歷圖的遍歷：從圖中某一頂點(diǎn)出發(fā)按一定規(guī)律沿著圖中的邊：從圖中某一頂點(diǎn)出發(fā)按一定規(guī)律沿著圖中的邊或弧訪(fǎng)問(wèn)每一頂點(diǎn)一次且僅一次的操作稱(chēng)為對(duì)圖的遍歷?；蚧≡L(fǎng)問(wèn)每一頂點(diǎn)一次且僅一次的操作稱(chēng)為對(duì)圖的遍歷。 *圖的遍歷有兩種方法：圖的遍歷有兩種方法：深度優(yōu)先遍歷深度優(yōu)先遍歷和和廣度優(yōu)先遍歷廣度優(yōu)先遍歷 *若圖是連通的或是強(qiáng)連通的，則遍歷過(guò)程所經(jīng)過(guò)的邊若圖是連通的或是強(qiáng)連通的，則遍歷過(guò)程所經(jīng)過(guò)的邊（或?。┘八闅v的頂點(diǎn)就得

8、到圖中的一棵（或?。┘八闅v的頂點(diǎn)就得到圖中的一棵生成樹(shù)生成樹(shù)。 *對(duì)于非連通圖而言，從某一連通分量中的某一頂點(diǎn)出對(duì)于非連通圖而言，從某一連通分量中的某一頂點(diǎn)出發(fā)執(zhí)行一次發(fā)執(zhí)行一次“遍歷遍歷”算法可得該連通分量的生成樹(shù)，該生算法可得該連通分量的生成樹(shù)，該生成樹(shù)是非連通圖的一顆成樹(shù)是非連通圖的一顆生成子樹(shù)生成子樹(shù)；分別對(duì)各連通分量執(zhí)行；分別對(duì)各連通分量執(zhí)行一次一次“遍歷遍歷”算法可得到非連通圖的算法可得到非連通圖的生成森林生成森林。 9二、存儲(chǔ)結(jié)構(gòu)二、存儲(chǔ)結(jié)構(gòu)*思想思想： 用兩個(gè)數(shù)組分別存儲(chǔ)數(shù)據(jù)元素(頂點(diǎn))的信息和數(shù)據(jù)元素之間的關(guān)系： 一個(gè)一維數(shù)組vexs: 存放各頂點(diǎn)的有關(guān)信息； 一個(gè)二維數(shù)組

9、arcs: 存放各條邊或弧的有關(guān)信息Arcs : 一般情況下存放邊或弧上的權(quán)值； 對(duì)于邊或弧上無(wú)權(quán)值的圖而言，邊或弧上的權(quán)值 為1時(shí)表示該條弧或邊的存在，若兩頂點(diǎn)之間沒(méi)有邊或弧，則設(shè)置該條邊或弧上的權(quán)值為0。10二、存儲(chǔ)結(jié)構(gòu)二、存儲(chǔ)結(jié)構(gòu)#define INFINITY 10000 / INFINITY用以表示用以表示#define MAX_VERTEX_NUM 20 /最大頂點(diǎn)數(shù)最大頂點(diǎn)數(shù)enum GraphKind DG,DN,UDG,UDN ; /枚舉：有向圖枚舉：有向圖,有向網(wǎng)有向網(wǎng),無(wú)向圖無(wú)向圖,無(wú)向網(wǎng)無(wú)向網(wǎng)typedef struct ArcCell VRType adj; / VR

10、Type的類(lèi)型視具體情況而定。對(duì)于帶權(quán)圖，的類(lèi)型視具體情況而定。對(duì)于帶權(quán)圖，adj用以存用以存 /放邊或弧上的權(quán)值放邊或弧上的權(quán)值;對(duì)于無(wú)權(quán)圖，對(duì)于無(wú)權(quán)圖，adj用以存放用以存放0或或1(int類(lèi)型類(lèi)型) /InfoType * info; /一般情況下可以不使用該項(xiàng)一般情況下可以不使用該項(xiàng) ArcCell , AdjMatrix MAX_VERTEX_NUM , MAX_VERTEX_NUM ; /AdiMatrix是一個(gè)類(lèi)型為是一個(gè)類(lèi)型為ArcCell的二維數(shù)組的二維數(shù)組,用以存放弧或邊的鄰接關(guān)系或權(quán)值用以存放弧或邊的鄰接關(guān)系或權(quán)值typedef struct VertexType vex

11、s MAX_VERTEX_NUM ; / VertexType是頂點(diǎn)值的類(lèi)型是頂點(diǎn)值的類(lèi)型 /一維數(shù)組一維數(shù)組vexs用以存放各頂點(diǎn)的值用以存放各頂點(diǎn)的值 AdjMatrix arcs; /二維數(shù)組二維數(shù)組arcs存放邊或弧上的信息（如權(quán)值）存放邊或弧上的信息（如權(quán)值） int vexnum , arcnum; /這兩項(xiàng)分別存放圖的頂點(diǎn)數(shù)目和弧的條數(shù)這兩項(xiàng)分別存放圖的頂點(diǎn)數(shù)目和弧的條數(shù) GraphKind kind; / kind用以存放圖的種類(lèi)標(biāo)志用以存放圖的種類(lèi)標(biāo)志 MGraph11二、存儲(chǔ)結(jié)構(gòu)二、存儲(chǔ)結(jié)構(gòu)例1：例如：例如：MGraph G1; 0 1 1 0 0 0 0 0 0 0 0

12、1 1 0 0 0G1.vexs0=a，. .， G1.vexs3=d ；G1.vexnum=4； G1.arcnum=4 ； G1.kind=DGG1.arcs =abcd012312二、存儲(chǔ)結(jié)構(gòu)二、存儲(chǔ)結(jié)構(gòu)例2：abde0134c2MGraph G2; 3 9 3 6 8 6 2 4 9 2 8 4 G2.vexs0=a，. .， G2.vexs4=e ；G2.vexnum=5； G2.arcnum=6 ； G2.kind=UDNG2.arcs =38692413二、存儲(chǔ)結(jié)構(gòu)二、存儲(chǔ)結(jié)構(gòu)*當(dāng)輸入一個(gè)圖時(shí)，要求用戶(hù)先輸入圖的類(lèi)型：Status CreateGraph(MGraph &

13、G) cinG.kind; switch(G.kind) case DG: return CreateDG(G); /0 case DN: return CreateDN(G); /1 case UDG: return CreateUDG(G); /2 case UDN: return CreateUDN(G); /3 default : return ERROR;/CreateGraph14二、存儲(chǔ)結(jié)構(gòu)二、存儲(chǔ)結(jié)構(gòu)*以無(wú)向網(wǎng)為例,即當(dāng)用戶(hù)輸入圖的類(lèi)型標(biāo)志為UDN時(shí),有：Status CreateUDN(MGraph &G) cinG.vexnum G.arcnum; /輸入頂點(diǎn)個(gè)數(shù)和

14、邊的條數(shù) for (i=0;iG.vexsi; /一維數(shù)組存放頂點(diǎn)值 for (i=0;iG.vexnum;+ +i ) /二維數(shù)組賦初值 for (j=0;jG.vexnum;+ +j ) G.arcsij= INFINITY ; /即將做為初值存入矩陣的各行各列 for (k=0;kv1 v2 w; i=locatevex(G,v1); j=locatevex(G,v2); /求頂點(diǎn)v1,v2在圖中的位置 G.arcsij.adj=w; G.arcsji.adj=w; /無(wú)向網(wǎng)的鄰接矩陣是對(duì)稱(chēng)的 return OK;/CreateUDN此處的locatevex(G,vi)是一個(gè)對(duì)一維數(shù)組G

15、.vexsG.vexnum進(jìn)行搜索查找vi在圖G中的位置的函數(shù)子程序；請(qǐng)同學(xué)們自己編寫(xiě)之。參考：int locatevex(MGraph G, VRType v) int k,i; k=-1; for (i=0;iG.kind; /輸入圖的種類(lèi) switch(G.kind) case 0: return CreateAL0(G); /DG case 1: return CreateAL1(G); /DN case 2: return CreateAL2(G); /UDG case 3: return CreateAL3(G); /UDN default : return ERROR;/Crea

16、teGraph19二、存儲(chǔ)結(jié)構(gòu)二、存儲(chǔ)結(jié)構(gòu)*以無(wú)向圖為例,即當(dāng)用戶(hù)輸入圖的類(lèi)型標(biāo)志為2時(shí),有：Status CreateAL2(ALGraph &G) cinG.vexnum G.arcnum; /輸入頂點(diǎn)數(shù)和弧的條數(shù) n= G.vexnum; e= G.arcnum; G.kind=2; for (i=0;iG.verticesi.data; G.verticesi.firstarc=NULL; /輸入n個(gè)頂點(diǎn)的值 for (k=1;kvt vh; /輸入一條邊的兩個(gè)頂點(diǎn)的值 i=locatevex(G,vt); j=locatevex(G,vh); p=new Arcnode; /申請(qǐng)一個(gè)弧結(jié)點(diǎn)存放序號(hào)申請(qǐng)一個(gè)弧結(jié)點(diǎn)存放序號(hào)j,并并 p-adjvex=j; /頭插法將其插入到序號(hào)為i的頂點(diǎn)的單鏈表（即第i個(gè)單鏈表）的表首 p-nextarc=G.verticei.firstarc; G.verticei.firstarc=p; p= new Arcnode; /由于邊可視為對(duì)稱(chēng)的兩條弧，故 /再申請(qǐng)一個(gè)弧結(jié)點(diǎn)存放序號(hào)i, 并將其插入到序號(hào)為j的頂點(diǎn)的單鏈表的表首 p-adjvex=i; p-ne