課程名稱數(shù)據(jù)結(jié)構(gòu)14

1、課程名稱 數(shù)據(jù)結(jié)構(gòu)14 授課題目圖 有向圖授課日期2003 年 11 月 26 日授課班級(jí)生物醫(yī)學(xué)工程授課時(shí)數(shù)4授課方式理論課授課重點(diǎn)、難點(diǎn)1. 有向圖及其表示方法：鄰樓表，鄰樓矩陣2. 圖的遍歷，與樹(shù)的遍歷及線性3. 掌握先深搜索與先廣搜索授課內(nèi)容、教具與時(shí)間分配授課內(nèi)容、教具與時(shí)間分配第五章 圖 5 1.1 有向圖及其表示方法 (存儲(chǔ)方法) (P127) 圖5.1 有向圖 頂點(diǎn)的集合 V= 1,2,3,4,頂點(diǎn)表示對(duì)象 弧的集合 E=（1，2），（1，3），（2，4），（3，2），（4，3） 對(duì)象之間的關(guān)系 圖 G = （V，E） 有序?qū)?、相鄰?一條?。?vw ， v為弧的尾，w為弧的頭

2、，是頂點(diǎn)v和w 的有序?qū)?，w和v是相鄰 的。 ，故而稱為有向圖。 路經(jīng)：頂點(diǎn)序列 路徑長(zhǎng)途： 弧的條數(shù) 簡(jiǎn)單路徑： 簡(jiǎn)單環(huán)路： 標(biāo)號(hào)有向圖：圖，頂點(diǎn)、弧附加信息 無(wú)向圖：若圖中的邊是頂點(diǎn)的無(wú)序?qū)Γ瑒t稱此圖為無(wú)向圖。無(wú)向圖中頂點(diǎn)間的聯(lián)系不用表示。512 鄰接矩陣 P127一、 鄰接矩陣是有向圖的一種表示方法（存儲(chǔ)方法），是二維數(shù)組方法。二、 圖 G =（V，E） ， V= 1，2，3 n用鄰接矩陣表示有向圖： aryij 行 列 有向圖 標(biāo)號(hào)有向圖 i j 1 a 無(wú) 0 空格 （布爾矩陣） 0,1 元素 10 對(duì)應(yīng)圖5.1 對(duì)應(yīng)圖5.2 三、 函數(shù)adjmatrix 建立圖的鄰接矩陣，返回圖的

3、頂點(diǎn)個(gè)數(shù)。 9 輸入方法：v1 v2 weight = 1 1 0 = 1 2 10 = 0 0 0 輸入結(jié)束四、 函數(shù)prmatrix打印鄰接矩陣。鄰接表一、 圖的另一種表示方法(存儲(chǔ)方法)，是鏈接方法二、 對(duì)圖中的任一頂點(diǎn)，由此頂點(diǎn)出發(fā)的全部相鄰頂點(diǎn)用一個(gè)向前鏈表表示，向前鏈表的前后次序不影響圖頂點(diǎn)之間的相互聯(lián)系。向前鏈表的表頭結(jié)點(diǎn)，構(gòu)成一個(gè)數(shù)組 list，表頭結(jié)點(diǎn)有信息場(chǎng)和鏈場(chǎng)組成，信息場(chǎng)另作它用。圖5.3 p128。1 2 3 兩者等價(jià)1 3 2 三、 函數(shù)adjlist建立有向圖鄰接表，返回圖的頂點(diǎn)個(gè)數(shù)。四、 函數(shù)pradjlist打印鄰接表。對(duì) p.128 graph.h 的說(shuō)明2

4、. adjmatrix(matrix) 建立有向圖(或無(wú)向圖)鄰接矩陣，返回頂點(diǎn)個(gè)數(shù)。實(shí)參是 MAX×MAX 二維數(shù)組名。 二維數(shù)組 matrixMAX 是鄰接矩陣。 輸入圖的頂點(diǎn)個(gè)數(shù)。 v1 v2 weight=1 1 0 對(duì)矩陣的每個(gè)元素賦值 INFIN (9999) 。 v1 v2 weight=1 2 10 用循環(huán)語(yǔ)句向矩陣輸入數(shù)據(jù)，以下圖為例： v1 v2 weight=1 3 9 10 v1 v2 weight=2 2 0 . v1 v2 weight=0 0 0 9 輸入完畢，循環(huán)結(jié)束。 3. prmatrix(mat,n) 打印鄰接矩陣。 實(shí)參是已生成的鄰接矩陣二維數(shù)

5、組的數(shù)組名，和圖的頂點(diǎn)個(gè)數(shù)。 printf(matij)=INFIN)? "t":"%d",matij) ；printf("n")； 如果矩陣元素是 INFIN 不打印 否則 打印矩陣元素值即 weight 4. adjlist(list) 建立有向圖的鄰接表，返回圖的頂點(diǎn)個(gè)數(shù)。 實(shí)參是大小為 MAX 的結(jié)構(gòu)體數(shù)組變量。 list是結(jié)構(gòu)體數(shù)組變量。 輸入圖的頂點(diǎn)個(gè)數(shù)。 list 賦初值。數(shù)據(jù)場(chǎng)目前暫空，也可供某些操作存放一定的標(biāo)志。 頂點(diǎn)標(biāo)號(hào) 以 p.127 圖5.1 為例，用循環(huán)語(yǔ)句輸入數(shù)據(jù)建立鄰接表： 數(shù)組下標(biāo) v1 v2=1 2

6、 或 v1 v2=1 3 1 v1 v2=1 3 v1 v2=1 2 2 v1 v2=2 4 3 v1 v2=3 2 4 v1 v2=4 3 v1 v2=0 0 輸入完畢，循環(huán)結(jié)束。5. pradjlist(list，n) 打印鄰接表數(shù)據(jù)場(chǎng)的值。 實(shí)參是已生成的鄰接表的表頭結(jié)點(diǎn)所構(gòu)成的數(shù)組的數(shù)組名，和圖的頂點(diǎn)個(gè)數(shù)。 以 p.127 圖5.1 為例。 6. 參考 p.30 ，補(bǔ)寫(xiě) push(arg)和pop()。參考 p.40 inser(arg) 和 delete() 補(bǔ)寫(xiě) engqueue(arg) 和 dequeue() 。NODE *front=NULL,*rear=NULL; enqu

7、eue(arg) int arg; NODE *ptr; ptr=getnode(NODE); ptr->info=arg; ptr->link=NULL; if(front=NULL) front=ptr; else rear->link=ptr; rear=ptr; dequeue() NODE *ptr; int var; if(front=NULL) return(-1); ptr=front; front=ptr->link; var=ptr->info; free(ptr); if(front=NULL) rear=NULL; return(var)5

8、.2 有向圖的遍歷圖遍歷的定義：p130圖的遍歷比樹(shù)的遍歷要復(fù)雜，從樹(shù)根到樹(shù)中的每個(gè)結(jié)點(diǎn)只有一條路徑，而從圖的起始點(diǎn)到達(dá)圖中的每個(gè)頂點(diǎn)可能存在著多條路徑。當(dāng)順著圖中的一條路徑訪問(wèn)過(guò)某一個(gè)頂點(diǎn)后，可能還會(huì)順著另一條路徑回到該頂點(diǎn)。5.2.1 先深搜索一、圖的先深搜索是樹(shù)的先根遍歷的推廣 舉例圖解二、先深搜索的步驟：1 輸出打印頂點(diǎn)標(biāo)號(hào)。 2. 標(biāo)記已訪問(wèn)過(guò)的頂點(diǎn)，NEWà OLD 。3 在向前鏈表中下移一個(gè)結(jié)點(diǎn)，用指針數(shù)組實(shí)現(xiàn) ptr =ptr àlink 。4 判斷向前鏈表是否結(jié)束，ptr !=NULL 。三、圖解先深搜索的算法思想 以p.130 圖 5.4 有向圖為例。四

9、、對(duì)先深搜索的說(shuō)明1 生成鄰接表。 2. 打印鄰接表。3對(duì)指針數(shù)組ptr 的每個(gè)元素賦值頭結(jié)點(diǎn)鏈場(chǎng)。4對(duì)頭結(jié)點(diǎn)數(shù)組每個(gè)元素的信息場(chǎng)賦值NEW 。5for (v=1; v<=n; v+) 查看起始頂點(diǎn)v，如果=NEW 從頂點(diǎn)v開(kāi)始先深搜索，調(diào)用dfs(v) 。6 函數(shù)dfs(v)打印頂點(diǎn)v 。頂點(diǎn)v的信息域改為OLD 。如果頂點(diǎn)v的鏈域NULL，搜索下一個(gè)結(jié)點(diǎn)。5.2.2 先廣搜索一、 圖解先廣搜索的算法思想。以圖為例。二、 對(duì) p.134 bfirst.c 的說(shuō)明。1 生成鄰接表。2 打印鄰接表。3 頭結(jié)點(diǎn)信息域賦值NEW 。4 for (v=1; v<=n;

10、v+) 查看起始頂點(diǎn)v，如果=NEW，則調(diào)用bfirst( )5 函數(shù)bfirst(v1) 定義一個(gè)指針變量ptr 。 打印頂點(diǎn)標(biāo)號(hào)v1 。 使 從NEW à OLD 。 v1入隊(duì)。 while (v=dequeue()!= EOF) /* 出隊(duì)成功不空 */ ptr=listv.link while (ptr!=NULL) /* 沒(méi)有到達(dá)鄰接表的最后一個(gè)結(jié)點(diǎn) */ 如果這個(gè)結(jié)點(diǎn)尚未訪問(wèn)過(guò)， 打印該結(jié)點(diǎn)，標(biāo)號(hào)NEW à OLD，入隊(duì) 在鄰接表中移過(guò)一個(gè)結(jié)點(diǎn)，ptr=ptràlink 授課內(nèi)容、教具與時(shí)間分配小結(jié)、復(fù)習(xí)、思考題、參考書(shū)思考題： 1將課本 p.131 圖5.4 用手工方法先深搜索。再運(yùn)行 dfs1.c ，生成數(shù)據(jù)文件存入dfs1.r1 。比較兩種方法所得的結(jié)果。2.將課本 p.132 圖5.6(a) 用手工方法先深搜索。再運(yùn)行 dfs1.c ，生成數(shù)據(jù)文件存dfs1.r2