基本數(shù)據(jù)結(jié)構(gòu)14圖a

1、講師：尹成QQ:77025077博客:http:/ 傳智播客傳智播客http:/高薪就業(yè)高薪就業(yè)第2頁(yè)上堂課內(nèi)容回顧上堂課內(nèi)容回顧特點(diǎn)：特點(diǎn)：“左小右大左小右大”，中序遍歷可得從小到大順序，中序遍歷可得從小到大順序搜索：同子樹(shù)根結(jié)點(diǎn)比較，同找到，小向左，大向右！搜索：同子樹(shù)根結(jié)點(diǎn)比較，同找到，小向左，大向右！插入：搜索父結(jié)點(diǎn)（相應(yīng)子樹(shù)空）插入：搜索父結(jié)點(diǎn)（相應(yīng)子樹(shù)空）,小插左，大插右！小插左，大插右！刪除：無(wú)左子樹(shù)，右子樹(shù)替代刪除結(jié)點(diǎn)刪除：無(wú)左子樹(shù)，右子樹(shù)替代刪除結(jié)點(diǎn) 有左子樹(shù)，有左子樹(shù)，(1)左子樹(shù)替代刪除結(jié)點(diǎn)，右子樹(shù)左子樹(shù)替代刪除結(jié)點(diǎn)，右子樹(shù)接到左子樹(shù)最右下結(jié)點(diǎn)。（接到左子樹(shù)最右下結(jié)點(diǎn)。（

2、2）改進(jìn)：左子樹(shù)最右下）改進(jìn)：左子樹(shù)最右下結(jié)點(diǎn)結(jié)點(diǎn)t替代刪除結(jié)點(diǎn)，并將替代刪除結(jié)點(diǎn)，并將t的左子樹(shù)掛到其父節(jié)點(diǎn)的的左子樹(shù)掛到其父節(jié)點(diǎn)的右子樹(shù)上。右子樹(shù)上。452453122890第3頁(yè)(1) (1) 哈夫曼樹(shù)是：哈夫曼樹(shù)是：WPL WPL 最小的樹(shù)。最小的樹(shù)。WPL = WPL = wklk wklk k=1k=1n n(2) Huffman(2) Huffman算法的思路：算法的思路：權(quán)值大的結(jié)點(diǎn)用短路徑，權(quán)值小的結(jié)點(diǎn)用長(zhǎng)路徑。權(quán)值大的結(jié)點(diǎn)用短路徑，權(quán)值小的結(jié)點(diǎn)用長(zhǎng)路徑。(3)(3)構(gòu)造構(gòu)造HuffmanHuffman樹(shù)的步驟：對(duì)權(quán)值的合并、刪除與替換樹(shù)的步驟：對(duì)權(quán)值的合并、刪除與替換(4)

3、 Huffman(4) Huffman編碼規(guī)則：左編碼規(guī)則：左“0” “0” 右右“1”“1”，是一種前，是一種前綴碼綴碼也稱為最小冗余編碼、緊致碼等，它是數(shù)據(jù)壓縮學(xué)的也稱為最小冗余編碼、緊致碼等，它是數(shù)據(jù)壓縮學(xué)的基礎(chǔ)。基礎(chǔ)。第4頁(yè)哈夫曼樹(shù)相關(guān)算法哈夫曼樹(shù)相關(guān)算法1. 1. 建立建立huffmanhuffman樹(shù)：樹(shù)：結(jié)點(diǎn)信息、父結(jié)點(diǎn)指針、權(quán)值、左右孩子指針。結(jié)點(diǎn)信息、父結(jié)點(diǎn)指針、權(quán)值、左右孩子指針。對(duì)權(quán)值的合并、刪除與替換對(duì)權(quán)值的合并、刪除與替換3. Huffman3. Huffman譯碼譯碼 2. Huffman2. Huffman編碼：編碼： 左左“0” “0” 右右“1”“1”，從葉子

4、結(jié)點(diǎn)開(kāi)始，從葉子結(jié)點(diǎn)開(kāi)始， Huffman Huffman編碼是一種前綴碼也稱為最小冗余編碼、緊致碼，等編碼是一種前綴碼也稱為最小冗余編碼、緊致碼，等等，它是數(shù)據(jù)壓縮學(xué)的基礎(chǔ)。等，它是數(shù)據(jù)壓縮學(xué)的基礎(chǔ)?？磳?shí)際程序注解和演示！看實(shí)際程序注解和演示！第5頁(yè)建立哈夫曼樹(shù)建立哈夫曼樹(shù)eleparent weightlchildrchild前面 n個(gè)，原始數(shù)據(jù)（n個(gè)子樹(shù)）后面 n1個(gè)，新生成子樹(shù)typedef char datatype;typedef struct node datatype name; folat weight; int parent, lchild, rchild; huftree

5、;整個(gè)哈夫曼樹(shù)的存儲(chǔ)結(jié)構(gòu)：整個(gè)哈夫曼樹(shù)的存儲(chǔ)結(jié)構(gòu)：2n-1個(gè)結(jié)點(diǎn)構(gòu)成的靜態(tài)鏈表個(gè)結(jié)點(diǎn)構(gòu)成的靜態(tài)鏈表下標(biāo)0 122nnameabweight0.10.2parent000Lchild000rchild000第6頁(yè)建樹(shù)主要步驟：建樹(shù)主要步驟：1. 2n-1 個(gè)結(jié)點(diǎn)初始化；2. 結(jié)點(diǎn)的合并，形成haffman樹(shù)3. 注意：無(wú)刪除與替換操作，原結(jié)點(diǎn)保留第7頁(yè)初始狀態(tài)（上）初始狀態(tài)（上） 與最終狀態(tài)（下）與最終狀態(tài)（下） P210第8頁(yè)初始狀態(tài)（左）初始狀態(tài)（左） 與最終狀態(tài)（右）與最終狀態(tài)（右）第9頁(yè) /*數(shù)據(jù)初始化* m=2*n-1; /總共需要的空間 HT=(HuffmanTree)malloc(

6、m+1)*sizeof(HTNode); /分配空間 /for(p=*HT,i=1;i=n;+p,+w) *p=wi-1.elem,wi-1. weight,0,0,0; for(i=1;i=n;+i) /結(jié)點(diǎn)、權(quán)值和指針初始化 HTi.elem=wi-1.elem; HTi.m_weight=wi-1.m_weight; HTi.parent=HTi.lchild=HTi.rchild=0; for( ;i=m;+i) /空結(jié)點(diǎn)初始化 隱含i初值n1 HTi.elem=0; HTi.m_weight=HTi.parent=HTi.lchild=HTi.rchild=0; 第10頁(yè) /*建立哈

7、夫曼樹(shù)* for(i=n+1;i=m;+i) Select(*HT,i-1,&s1,&s2); /在HT1.i-1中選擇parent為0且weight最小的兩個(gè)結(jié)點(diǎn)，其序號(hào)分別為s1和s2/注意此處i是變化的，也就是HT數(shù)組中參與比較到的結(jié)點(diǎn)不斷增多 HTs1.parent=i; HTs2.parent=i; HTi.lchild=s1; HTi.rchild=s2; HTi.m_weight=HTs1.m_weight+HTs2.m_weight; /兩結(jié)點(diǎn)權(quán)值相加新結(jié)點(diǎn)權(quán)值 合并合并第11頁(yè)哈夫曼編哈夫曼編碼碼1. 找到n個(gè)結(jié)點(diǎn)的父結(jié)點(diǎn)2. 從父節(jié)點(diǎn)開(kāi)始到葉子的路徑記錄下來(lái)就是編碼，左0右

8、1, 注意是逆向編碼，自底向上編碼表的存儲(chǔ)結(jié)編碼表的存儲(chǔ)結(jié)構(gòu)構(gòu)1. 靜態(tài)順序存儲(chǔ) 2. 動(dòng)態(tài)鏈?zhǔn)酱鎯?chǔ)第12頁(yè) 靜態(tài)順序存儲(chǔ)typedef struct cnode char bitsleafnum+1; /編碼字串，最大深度為葉子結(jié)點(diǎn)數(shù)目 int start; /記錄起始點(diǎn) char ch; /字符名稱 hufcode;結(jié)構(gòu)簡(jiǎn)單但浪費(fèi)空間第13頁(yè) 動(dòng)態(tài)鏈?zhǔn)酱鎯?chǔ)typedef char * huffmancode;HC= (HuffmanCode) malloc(n*sizeof(char*);HCi= (char *)malloc(n-start)*sizeof(char); 結(jié)構(gòu)復(fù)雜但節(jié)約空

9、間huffmancode HC第14頁(yè) /*哈夫曼樹(shù)編碼* (*HC)=(HuffmanCode)malloc(n*sizeof(char*); /分配編碼空間數(shù)組 char* HuffmanCode cd=(char *)malloc(n*sizeof(char); /分配求編碼的工作空間 cdn-1=0; /編碼結(jié)束符號(hào) for(i=1;i=n;+i) /逐個(gè)字符求哈夫曼編碼 start=n-1; /編碼結(jié)束符位置 for(c=i, f=HTi.parent; f!=0; c=f, f=HTf.parent) /從葉子到根逆向求編碼 if(HTf.lchild=c) cd-start=0;

10、 else cd-start=1; (*HC)i= (char *)malloc(n-start)*sizeof(char); /為第i個(gè)字符分配編碼空間 strcpy(*HC)i,&cdstart); 第15頁(yè)c=i;f=HTi.parent; /從葉子到根逆向求編碼while(f!=0) if(HTf.lchild=c) cd-start=0; /左0右1 else cd-start=1; c=f; f=HTf.parent;for(c=i,f=HTi.parent ; f!=0; c=f,f=HTf.parent)第16頁(yè)哈夫曼譯哈夫曼譯碼碼1. 從根結(jié)點(diǎn)開(kāi)始依次根據(jù)編碼0或1向下搜索2

11、. 到達(dá)根結(jié)點(diǎn)，提取根結(jié)點(diǎn)的字符3. 繼續(xù)下一個(gè)循環(huán)第17頁(yè)2 23 35 56 6111110107 73232171728282121191940406060100100b bc ca ad de eg gf fh h0 00 00 00 00 01 11 11 11 11 11 11 10 00 000 bchg第18頁(yè)例例3:3:設(shè)字符集為設(shè)字符集為2626個(gè)英文字母，其出現(xiàn)頻度如下表所示。個(gè)英文字母，其出現(xiàn)頻度如下表所示。注：若圓滿實(shí)現(xiàn)了此方案，平時(shí)成績(jī)獎(jiǎng)勵(lì)注：若圓滿實(shí)現(xiàn)了此方案，平時(shí)成績(jī)獎(jiǎng)勵(lì)5分！分！51481156357203251頻度頻度zyxwvu字符字符1161188238

12、0頻度頻度p21fq15gr47hsonmlkj字符字符5710332221364186頻度頻度idcba字符字符先建哈夫曼樹(shù)，再利用此樹(shù)對(duì)報(bào)文先建哈夫曼樹(shù)，再利用此樹(shù)對(duì)報(bào)文“This program is my favorite”進(jìn)行編碼和譯碼。進(jìn)行編碼和譯碼。要求編程實(shí)現(xiàn)要求編程實(shí)現(xiàn)：提示：為了避免在編程調(diào)試過(guò)程中輸入數(shù)據(jù)過(guò)于麻煩，可采用文提示：為了避免在編程調(diào)試過(guò)程中輸入數(shù)據(jù)過(guò)于麻煩，可采用文件存儲(chǔ)編碼字符及其權(quán)重，每次讀入即可，或直接用數(shù)組存儲(chǔ)。件存儲(chǔ)編碼字符及其權(quán)重，每次讀入即可，或直接用數(shù)組存儲(chǔ)。第19頁(yè)1 1、定義和性質(zhì)、定義和性質(zhì)2 2、存儲(chǔ)結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)3 3、遍歷、遍歷4

13、4、線索化：線索樹(shù)、線索化：線索樹(shù)順序結(jié)構(gòu)順序結(jié)構(gòu)鏈?zhǔn)浇Y(jié)構(gòu)鏈?zhǔn)浇Y(jié)構(gòu)二叉鏈表二叉鏈表三叉鏈表三叉鏈表先序線索樹(shù)先序線索樹(shù)中序線索樹(shù)中序線索樹(shù)后序線索樹(shù)后序線索樹(shù)先先序序遍遍歷歷中中序序遍遍歷歷遍歷遍歷存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)遍歷遍歷雙親表示雙親表示孩子表示孩子表示孩子兄弟孩子兄弟先序遍歷先序遍歷后序遍歷后序遍歷中序遍歷中序遍歷后序遍歷后序遍歷先序遍歷先序遍歷哈夫曼樹(shù)哈夫曼樹(shù)哈夫曼編碼哈夫曼編碼二叉排序樹(shù)二叉排序樹(shù)查找插入刪除查找插入刪除第20頁(yè)數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容多對(duì)多多對(duì)多（m:n)第21頁(yè)7.1 7.1 基本術(shù)語(yǔ)基本術(shù)語(yǔ)7.2 7.2 存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)7.3 7.3 圖的遍歷圖的遍歷

14、7.4 7.4 圖的其他運(yùn)算圖的其他運(yùn)算7.5 7.5 圖的應(yīng)用圖的應(yīng)用第22頁(yè)圖：記為圖：記為 G G( V, E ) ( V, E ) 其中：其中：V V 是是G G的頂點(diǎn)集合，是有窮非空集；的頂點(diǎn)集合，是有窮非空集； E E 是是G G的邊集合，是有的邊集合，是有窮集。窮集。問(wèn)：當(dāng)問(wèn)：當(dāng)E(G)E(G)為空時(shí)，圖為空時(shí)，圖G G存在否？存在否？答：還存在！但此時(shí)圖答：還存在！但此時(shí)圖G G只有頂點(diǎn)而沒(méi)有邊。只有頂點(diǎn)而沒(méi)有邊。有向圖：有向圖：無(wú)向圖：無(wú)向圖：完全圖：完全圖：圖圖G G中的每條邊都是有方向的；中的每條邊都是有方向的；圖圖G G中的每條邊都是無(wú)方向的；中的每條邊都是無(wú)方向的；圖

15、圖G G任意兩個(gè)頂點(diǎn)都有一條邊相連接；任意兩個(gè)頂點(diǎn)都有一條邊相連接；V=vertex E=edge第23頁(yè)證明：第24頁(yè)例：判斷下列例：判斷下列4 4種圖形各屬什么類型？種圖形各屬什么類型？無(wú)向無(wú)向無(wú)向圖無(wú)向圖(樹(shù)樹(shù))有向圖有向圖有向有向G1G1的頂點(diǎn)集合為的頂點(diǎn)集合為V(G1)=0,1,2,3V(G1)=0,1,2,3邊集合為邊集合為E(G1)=(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)E(G1)=(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)完全圖完全圖完全圖完全圖第25頁(yè)稀疏圖：邊較少的圖。通常邊數(shù)n2子 圖：設(shè)有兩個(gè)圖 G(V, E)

16、 和 G(V, E)。若 V V 且 E E, 則稱 圖G 是 圖G 的子圖。稠密圖：邊很多的圖。無(wú)向圖中，邊數(shù)接近n(n-1)/2 ； 有向圖中，邊數(shù)接近n(n-1) 帶權(quán)圖：即邊上帶權(quán)的圖。其中權(quán)是指每條邊可以標(biāo)帶權(quán)圖：即邊上帶權(quán)的圖。其中權(quán)是指每條邊可以標(biāo)上具有某種含義的數(shù)值（即與邊相關(guān)的數(shù)）。上具有某種含義的數(shù)值（即與邊相關(guān)的數(shù)）。網(wǎng)網(wǎng) 絡(luò)：絡(luò)： 帶權(quán)圖帶權(quán)圖第26頁(yè)簡(jiǎn)單路徑：路徑上各頂點(diǎn)路徑上各頂點(diǎn) v1,v2,.,vm v1,v2,.,vm 均不互相重復(fù)。均不互相重復(fù)?；?路：例：例：若路徑上第一個(gè)頂點(diǎn)若路徑上第一個(gè)頂點(diǎn) v1 v1 與最后一個(gè)頂點(diǎn)與最后一個(gè)頂點(diǎn)vm vm 重合重合

17、，則稱這樣的路徑為回路或環(huán)。，則稱這樣的路徑為回路或環(huán)。路徑：路徑長(zhǎng)度：第27頁(yè)例157324G26例245136G1路徑：1，2，3，5，6，3路徑長(zhǎng)度：5(路徑上結(jié)點(diǎn)數(shù)-1)簡(jiǎn)單路徑：1，2，3，5回路：1，2，3，5，6，3，1簡(jiǎn)單回路：3，5，6，3路徑：1，2，5，7，6，5，2，3路徑長(zhǎng)度：7簡(jiǎn)單路徑：1，2，5，7，6回路：1，2，5，7，6，5，2，1簡(jiǎn)單回路：1，2，3，1第28頁(yè)弧頭和弧尾：有向邊(u, v)稱為弧，邊的始點(diǎn)u叫弧尾，終點(diǎn)v叫弧頭 頂點(diǎn)頂點(diǎn)v的度是與它相關(guān)聯(lián)的邊的條數(shù)。記作的度是與它相關(guān)聯(lián)的邊的條數(shù)。記作TD(v)。 在有向圖中在有向圖中, 頂點(diǎn)的度等于該頂

18、點(diǎn)的入度與出度之和。頂點(diǎn)的度等于該頂點(diǎn)的入度與出度之和。 頂點(diǎn)頂點(diǎn) v 的入度是以的入度是以 v 為終點(diǎn)的有向邊的條數(shù)為終點(diǎn)的有向邊的條數(shù), 記作記作 ID(v); 頂點(diǎn)頂點(diǎn) v 的出度是以的出度是以 v 為始點(diǎn)的有向邊的條數(shù)為始點(diǎn)的有向邊的條數(shù), 記作記作 OD(v)。鄰接頂點(diǎn)：若 (u, v) 是 E(G) 中的一條邊，則稱 u 與 v 互為鄰接頂點(diǎn)度、入度和出度：?jiǎn)枺寒?dāng)有向圖中僅問(wèn)：當(dāng)有向圖中僅1 1個(gè)頂點(diǎn)的入度為個(gè)頂點(diǎn)的入度為0,0,其余頂點(diǎn)的其余頂點(diǎn)的入度均為入度均為1 1，此時(shí)是何形狀？，此時(shí)是何形狀？答：是樹(shù)！而且是一棵有向樹(shù)！答：是樹(shù)！而且是一棵有向樹(shù)！第29頁(yè)生成樹(shù)：生成樹(shù)：

19、V1V2V4V5V3V7V6V8例V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8第30頁(yè)連連 通通 圖：圖：強(qiáng)連通圖：強(qiáng)連通圖：有兩類圖形有兩類圖形不在本章討不在本章討論之列：論之列：連通圖245136強(qiáng)連通圖356245136非連通圖連通分量第31頁(yè)ADT Graph 數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象V：v是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點(diǎn)集。是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點(diǎn)集。數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系R：R=VR；VR=|v,wV 且且 P(v,w), 表示從表示從v到到w的弧，的弧， 謂詞謂詞P(v,w)定義了弧定義了弧的意義或信息的意義或信息基本操作基本操作P： CreatGr

20、aph ( &G, V,VR); 初始條件：初始條件：V是圖的頂點(diǎn)集，是圖的頂點(diǎn)集，VR是圖中弧的集合。是圖中弧的集合。 操作結(jié)果：按操作結(jié)果：按V和和VR的定義構(gòu)造圖的定義構(gòu)造圖G。 InsertVex ( &G, v); 初始條件：圖初始條件：圖G存在，存在，v和圖中頂點(diǎn)有相同特征。和圖中頂點(diǎn)有相同特征。 操作結(jié)果：在圖操作結(jié)果：在圖G中添加新頂點(diǎn)。中添加新頂點(diǎn)。 （參見(jiàn)（參見(jiàn)P156-257）注意：注意：V V 的大的大小寫含義不同小寫含義不同！第32頁(yè)圖的特點(diǎn)：非線性結(jié)構(gòu)（圖的特點(diǎn)：非線性結(jié)構(gòu)（m :n m :n ） 鄰接表鄰接表 鄰接多重表鄰接多重表 十字鏈表十字鏈表設(shè)計(jì)為鄰接矩設(shè)計(jì)

21、為鄰接矩陣陣鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)： 無(wú)！無(wú)?。ǘ鄠€(gè)頂點(diǎn)，無(wú)序可言）（多個(gè)頂點(diǎn)，無(wú)序可言）但可用數(shù)組描述元素間關(guān)系。但可用數(shù)組描述元素間關(guān)系?？捎枚嘀劓湵砜捎枚嘀劓湵碇攸c(diǎn)介紹：重點(diǎn)介紹：第33頁(yè) , ),( , , .否否則則或或者者如如果果01AEjiEjijiEdgev1v2v3v5v4v4A鄰接矩陣：A.Edge =（ v1 v2 v3 v4 v5 ）v1v2v3v4v50 0 0 0 00 0 0 0 00 0 0 0 00 0 0 0 00 0 0 0 00 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 10 1 1 1 00 1

22、0 1 01 0 1 0 10 1 0 1 11 0 1 0 10 1 1 1 0頂點(diǎn)表：第34頁(yè)例例2 2 ：有向圖的鄰接矩陣：有向圖的鄰接矩陣素之和素之和, ,即：即：TD(Vi)=OD( Vi ) + ID( Vi )TD(Vi)=OD( Vi ) + ID( Vi )v1v2v3v4鄰接矩陣：A.Edge =( v1 v2 v3 v4 )v1v2v3v40 0 0 00 0 0 0 0 0 0 0 0 0 0 0 注：在有向圖的鄰接矩陣中，注：在有向圖的鄰接矩陣中， 第第i i行含義：以結(jié)點(diǎn)行含義：以結(jié)點(diǎn)vivi為尾的弧為尾的弧( (即出度邊）；即出度邊）； 第第i i列含義：以結(jié)點(diǎn)列

23、含義：以結(jié)點(diǎn)vivi為頭的弧為頭的弧( (即入度邊）。即入度邊）。頂點(diǎn)表：0 1 1 00 0 0 0 0 0 0 1 1 0 0 0 0 1 1 00 0 0 0 0 0 0 1 1 0 0 0 第35頁(yè) 容易實(shí)現(xiàn)圖的操作，如：求某頂點(diǎn)的度、判斷容易實(shí)現(xiàn)圖的操作，如：求某頂點(diǎn)的度、判斷頂點(diǎn)之間是否有邊（弧）、找頂點(diǎn)的鄰接點(diǎn)等等。頂點(diǎn)之間是否有邊（?。?、找頂點(diǎn)的鄰接點(diǎn)等等。 n n個(gè)頂點(diǎn)需要個(gè)頂點(diǎn)需要n n* *n n個(gè)單元存儲(chǔ)邊個(gè)單元存儲(chǔ)邊( (弧弧););空間效率空間效率為為O(n2)O(n2)。 對(duì)稀疏圖而言尤其浪費(fèi)空間。對(duì)稀疏圖而言尤其浪費(fèi)空間。特別討論特別討論 ：網(wǎng)（即有權(quán)圖）的鄰接

24、矩陣：網(wǎng)（即有權(quán)圖）的鄰接矩陣定義為：定義為： A.Edge i j =Wij 或（或（vi, vj）VR 無(wú)邊（?。o(wú)邊（?。﹙1v2v3v4Nv5v65489755613以有向網(wǎng)為例以有向網(wǎng)為例：鄰接矩陣： N.Edge =( v1 v2 v3 v4 v5 v6 )鄰接矩陣法優(yōu)點(diǎn)：鄰接矩陣法優(yōu)點(diǎn)：鄰接矩陣法缺點(diǎn)：鄰接矩陣法缺點(diǎn)：頂點(diǎn)表： 5 7 4 8 9 5 6 5 3 1 5 7 4 8 9 5 6 5 3 1 第36頁(yè)注：用兩個(gè)數(shù)組分別存儲(chǔ)頂點(diǎn)表和鄰接矩陣注：用兩個(gè)數(shù)組分別存儲(chǔ)頂點(diǎn)表和鄰接矩陣#define INFINITY INT_MAX /最大值最大值#define MAX_VE

25、RTEX_NUM 20 /假設(shè)的最大頂點(diǎn)數(shù)假設(shè)的最大頂點(diǎn)數(shù)Typedef enum DG, DN, AG,AN GraphKind; /有向有向/無(wú)向圖，有向無(wú)向圖，有向/無(wú)向網(wǎng)無(wú)向網(wǎng)Typedef struct ArcCell /?。ㄟ叄┙Y(jié)點(diǎn)的定義?。ㄟ叄┙Y(jié)點(diǎn)的定義 VRType adj; /頂點(diǎn)間關(guān)系，無(wú)權(quán)圖取頂點(diǎn)間關(guān)系，無(wú)權(quán)圖取1或或0；有權(quán)圖??；有權(quán)圖取權(quán)值類型權(quán)值類型 InfoType *info; /該弧相關(guān)信息的指針該弧相關(guān)信息的指針ArcCell, AdjMatrix MAX_VERTEX_NUM MAX_VERTEX_NUM ;圖的鄰接矩陣存儲(chǔ)表示（參見(jiàn)教材圖的鄰接矩陣存儲(chǔ)表

26、示（參見(jiàn)教材P161P161）對(duì)于對(duì)于n n個(gè)頂點(diǎn)的圖或網(wǎng)，空間效率個(gè)頂點(diǎn)的圖或網(wǎng)，空間效率=O(n2)=O(n2)第37頁(yè)Typedef struct /圖的定義圖的定義 VertexType vexs MAX_VERTEX_NUM ; /頂點(diǎn)表，用一維向量即可頂點(diǎn)表，用一維向量即可AdjMatrix arcs; /鄰接矩陣鄰接矩陣Int Vernum, arcnum; /頂點(diǎn)總數(shù)，弧（邊頂點(diǎn)總數(shù)，?。ㄟ叄┛倲?shù)）總數(shù)GraphKind kind; /圖的種類標(biāo)志圖的種類標(biāo)志 Mgraph;第38頁(yè)adjvexinfonextarcdatafirstarc鄰接點(diǎn)域，表鄰接點(diǎn)域，表示示vi一個(gè)鄰

27、接一個(gè)鄰接點(diǎn)的位置點(diǎn)的位置鏈域，指向鏈域，指向vi下一個(gè)邊下一個(gè)邊或弧的結(jié)點(diǎn)或弧的結(jié)點(diǎn)數(shù)據(jù)域，與數(shù)據(jù)域，與邊有關(guān)信息邊有關(guān)信息（如權(quán)值）（如權(quán)值）數(shù)據(jù)域，存數(shù)據(jù)域，存儲(chǔ)頂點(diǎn)儲(chǔ)頂點(diǎn)vi 信信息息鏈域，指向鏈域，指向單鏈表的第單鏈表的第一個(gè)結(jié)點(diǎn)一個(gè)結(jié)點(diǎn)第39頁(yè)v1v2v3v5v4v4鄰接表0123413341420v1v2v3v4V4V3V2V12301鄰接表鄰接表(出邊出邊)V4V3V2V13020逆鄰接表逆鄰接表(入邊入邊)v1v2v3v4v5231420第40頁(yè)8064125當(dāng)鄰接表當(dāng)鄰接表的存儲(chǔ)結(jié)的存儲(chǔ)結(jié)構(gòu)形成后構(gòu)形成后，圖便唯，圖便唯一確定！一確定！第41頁(yè)分析分析1: 對(duì)于對(duì)于n個(gè)頂點(diǎn)

28、個(gè)頂點(diǎn)e條邊的無(wú)向圖，鄰接表中除了條邊的無(wú)向圖，鄰接表中除了n個(gè)頭結(jié)點(diǎn)外個(gè)頭結(jié)點(diǎn)外，只有，只有2e個(gè)表結(jié)點(diǎn)個(gè)表結(jié)點(diǎn),空間效率為空間效率為O(n+2e)。若是稀疏圖若是稀疏圖(en2)，則比鄰接矩陣表示法，則比鄰接矩陣表示法O(n2)省空間。省空間。鄰接表存儲(chǔ)法的特點(diǎn)：鄰接表存儲(chǔ)法的特點(diǎn)：分析分析2:在有向圖中，鄰接表中除了在有向圖中，鄰接表中除了n個(gè)頭結(jié)點(diǎn)外，只有個(gè)頭結(jié)點(diǎn)外，只有e個(gè)表結(jié)點(diǎn)個(gè)表結(jié)點(diǎn),空間效率為空間效率為O(n+e)。若是稀疏圖，則比鄰接矩陣表示法合適。若是稀疏圖，則比鄰接矩陣表示法合適。它其實(shí)是對(duì)鄰接矩陣法的一種改進(jìn)它其實(shí)是對(duì)鄰接矩陣法的一種改進(jìn)怎樣計(jì)算無(wú)向圖頂點(diǎn)的度？怎樣計(jì)算

29、無(wú)向圖頂點(diǎn)的度？鄰接表的缺點(diǎn)：鄰接表的缺點(diǎn)：怎樣計(jì)算有向圖頂點(diǎn)的出度？怎樣計(jì)算有向圖頂點(diǎn)的出度？怎樣計(jì)算有向圖頂點(diǎn)的入度？怎樣計(jì)算有向圖頂點(diǎn)的入度？怎樣計(jì)算有向圖頂點(diǎn)怎樣計(jì)算有向圖頂點(diǎn)Vi的度：的度：需遍歷全表需遍歷全表鄰接表的優(yōu)點(diǎn)：鄰接表的優(yōu)點(diǎn)：TD(Vi)=TD(Vi)=單鏈表中鏈接的結(jié)點(diǎn)個(gè)數(shù)單鏈表中鏈接的結(jié)點(diǎn)個(gè)數(shù)OD(Vi)單鏈出邊表中鏈接的結(jié)點(diǎn)數(shù)單鏈出邊表中鏈接的結(jié)點(diǎn)數(shù)I D( Vi ) 鄰接點(diǎn)為鄰接點(diǎn)為Vi的弧個(gè)數(shù)的弧個(gè)數(shù)TD(Vi) = OD( Vi ) + I D( Vi )空間效率高；容易尋找頂點(diǎn)的鄰接點(diǎn)；空間效率高；容易尋找頂點(diǎn)的鄰接點(diǎn)；判斷兩頂點(diǎn)間是否有邊或弧，需搜索兩結(jié)點(diǎn)

30、判斷兩頂點(diǎn)間是否有邊或弧，需搜索兩結(jié)點(diǎn)對(duì)應(yīng)的單鏈表，沒(méi)有鄰接矩陣方便。對(duì)應(yīng)的單鏈表，沒(méi)有鄰接矩陣方便。第42頁(yè)討論：鄰接表與鄰接矩陣有什么異同之處？討論：鄰接表與鄰接矩陣有什么異同之處？1. 1. 聯(lián)系：鄰接表中每個(gè)鏈表對(duì)應(yīng)于鄰接矩陣中的一行，聯(lián)系：鄰接表中每個(gè)鏈表對(duì)應(yīng)于鄰接矩陣中的一行，鏈表中結(jié)點(diǎn)個(gè)數(shù)等于一行中非零元素的個(gè)數(shù)。鏈表中結(jié)點(diǎn)個(gè)數(shù)等于一行中非零元素的個(gè)數(shù)。2. 2. 區(qū)別：區(qū)別： 對(duì)于任一確定的無(wú)向圖，鄰接矩陣是唯一的（行列對(duì)于任一確定的無(wú)向圖，鄰接矩陣是唯一的（行列號(hào)與頂點(diǎn)編號(hào)一致），但鄰接表不唯一（鏈接次序號(hào)與頂點(diǎn)編號(hào)一致），但鄰接表不唯一（鏈接次序與頂點(diǎn)編號(hào)無(wú)關(guān)）。與頂點(diǎn)編號(hào)

31、無(wú)關(guān)）。( (考試怎么辦？給定順序）考試怎么辦？給定順序） 鄰接矩陣的空間復(fù)雜度為鄰接矩陣的空間復(fù)雜度為O(n2),O(n2),而鄰接表的空間復(fù)而鄰接表的空間復(fù)雜度為雜度為O(n+e)O(n+e)。3. 3. 用途：鄰接矩陣多用于稠密圖的存儲(chǔ)（用途：鄰接矩陣多用于稠密圖的存儲(chǔ)（e e接近接近n(n-n(n-1)/2)1)/2)；而鄰接表多用于稀疏圖的存儲(chǔ)（；而鄰接表多用于稀疏圖的存儲(chǔ)（en2)en2)第43頁(yè)圖的鄰接表存儲(chǔ)表示（參見(jiàn)教材圖的鄰接表存儲(chǔ)表示（參見(jiàn)教材P163P163）#define MAX_VERTEX_NUM 20 /假設(shè)的最大頂點(diǎn)數(shù)假設(shè)的最大頂點(diǎn)數(shù)Typedef struct

32、 ArcNode int adjvex; /該弧所指向的頂點(diǎn)位置該弧所指向的頂點(diǎn)位置 struct ArcNode *nextarcs; /指向下一條弧的指針指向下一條弧的指針 InfoArc *info; /該弧相關(guān)信息的指針該弧相關(guān)信息的指針 ArcNode；Typedef struct VNode /頂點(diǎn)結(jié)構(gòu)頂點(diǎn)結(jié)構(gòu) VertexType data; /頂點(diǎn)信息頂點(diǎn)信息 ArcNode * firstarc; /指向依附該頂點(diǎn)的第一條弧的指針指向依附該頂點(diǎn)的第一條弧的指針VNode, AdjList MAX_VERTEX_NUM ; Typedef struct /圖結(jié)構(gòu)圖結(jié)構(gòu) AdjL

33、ist vertics ; /應(yīng)包含鄰接表應(yīng)包含鄰接表 int vexnum, arcnum; /應(yīng)包含頂點(diǎn)總數(shù)和弧總數(shù)應(yīng)包含頂點(diǎn)總數(shù)和弧總數(shù) int kind; /還應(yīng)說(shuō)明圖的種類（用標(biāo)志）還應(yīng)說(shuō)明圖的種類（用標(biāo)志）ALGraph; /圖結(jié)構(gòu)圖結(jié)構(gòu)圖的鄰接表生成算法作為自測(cè)題。圖的鄰接表生成算法作為自測(cè)題?？臻g效率為空間效率為O(n+2e)O(n+2e)或或O(n+e)O(n+e)時(shí)間效率為時(shí)間效率為O(n+eO(n+e* *n)n)第44頁(yè)一、深度優(yōu)先搜索二、廣度優(yōu)先搜索 7.3 7.3 圖的遍歷圖的遍歷遍歷定義：從已給的連通圖中某一頂點(diǎn)出發(fā)，沿著一些邊訪遍遍歷定義：從已給的連通圖中某一頂

34、點(diǎn)出發(fā)，沿著一些邊訪遍圖中所有的頂點(diǎn)，且使每個(gè)頂點(diǎn)僅被訪問(wèn)一次，就叫做圖圖中所有的頂點(diǎn)，且使每個(gè)頂點(diǎn)僅被訪問(wèn)一次，就叫做圖的遍歷，它是圖的基本運(yùn)算。的遍歷，它是圖的基本運(yùn)算。遍歷實(shí)質(zhì)：找每個(gè)頂點(diǎn)的鄰接點(diǎn)的過(guò)程。遍歷實(shí)質(zhì)：找每個(gè)頂點(diǎn)的鄰接點(diǎn)的過(guò)程。圖的遍歷操作的特點(diǎn)：圖中可能存在回路，且圖的任一頂點(diǎn)都圖的遍歷操作的特點(diǎn)：圖中可能存在回路，且圖的任一頂點(diǎn)都可能與其它頂點(diǎn)相通，在訪問(wèn)完某個(gè)頂點(diǎn)之后可能會(huì)沿著可能與其它頂點(diǎn)相通，在訪問(wèn)完某個(gè)頂點(diǎn)之后可能會(huì)沿著某些邊又回到了曾經(jīng)訪問(wèn)過(guò)的頂點(diǎn)。某些邊又回到了曾經(jīng)訪問(wèn)過(guò)的頂點(diǎn)。解決思路：可設(shè)置一個(gè)輔助數(shù)組解決思路：可設(shè)置一個(gè)輔助數(shù)組 visited n ，用

35、來(lái)標(biāo)記每個(gè)被，用來(lái)標(biāo)記每個(gè)被訪問(wèn)過(guò)的頂點(diǎn)。它的初始狀態(tài)為訪問(wèn)過(guò)的頂點(diǎn)。它的初始狀態(tài)為0，在圖的遍歷過(guò)程中，在圖的遍歷過(guò)程中，一旦某一個(gè)頂點(diǎn)一旦某一個(gè)頂點(diǎn)i 被訪問(wèn)，就立即改被訪問(wèn)，就立即改 visited i為為1，防止，防止它被多次訪問(wèn)。它被多次訪問(wèn)。圖常用的遍歷：圖常用的遍歷：怎樣避免重復(fù)訪問(wèn)？怎樣避免重復(fù)訪問(wèn)？第45頁(yè)基本思想：基本思想：仿樹(shù)的先序遍歷過(guò)程。仿樹(shù)的先序遍歷過(guò)程。Depth_First Searchv1v2v3v8v7v6v4v5起點(diǎn)起點(diǎn)起點(diǎn)起點(diǎn)遍歷步驟遍歷步驟第46頁(yè)深度優(yōu)先搜索（遍歷）步驟：深度優(yōu)先搜索（遍歷）步驟：詳細(xì)歸納：詳細(xì)歸納：在訪問(wèn)圖中某一起始頂點(diǎn)在訪問(wèn)圖中某

36、一起始頂點(diǎn) v 后，由后，由 v 出發(fā)，訪問(wèn)它的任一鄰接頂點(diǎn)出發(fā)，訪問(wèn)它的任一鄰接頂點(diǎn) w1；再?gòu)脑購(gòu)?w1 出發(fā)，訪問(wèn)與出發(fā)，訪問(wèn)與 w1鄰接但還未被訪問(wèn)過(guò)的頂點(diǎn)鄰接但還未被訪問(wèn)過(guò)的頂點(diǎn) w2；然后再?gòu)娜缓笤購(gòu)?w2 出發(fā)，進(jìn)行類似的訪問(wèn)，出發(fā)，進(jìn)行類似的訪問(wèn)， 如此進(jìn)行下去，直至到達(dá)所有的鄰接頂點(diǎn)都被訪問(wèn)過(guò)的頂點(diǎn)如此進(jìn)行下去，直至到達(dá)所有的鄰接頂點(diǎn)都被訪問(wèn)過(guò)的頂點(diǎn) u 為止。為止。接著，退回一步，退到前一次剛訪問(wèn)過(guò)的頂點(diǎn)，看是否還有其它沒(méi)有被接著，退回一步，退到前一次剛訪問(wèn)過(guò)的頂點(diǎn)，看是否還有其它沒(méi)有被訪問(wèn)的鄰接頂點(diǎn)。訪問(wèn)的鄰接頂點(diǎn)。若有，則訪問(wèn)此頂點(diǎn)，之后再?gòu)拇隧旤c(diǎn)出發(fā)，進(jìn)行與前述類似的

37、訪問(wèn)；若有，則訪問(wèn)此頂點(diǎn)，之后再?gòu)拇隧旤c(diǎn)出發(fā)，進(jìn)行與前述類似的訪問(wèn)；若沒(méi)有，就再退回一步進(jìn)行搜索。重復(fù)上述過(guò)程，直到連通圖中所有頂若沒(méi)有，就再退回一步進(jìn)行搜索。重復(fù)上述過(guò)程，直到連通圖中所有頂點(diǎn)都被訪問(wèn)過(guò)為止。點(diǎn)都被訪問(wèn)過(guò)為止。簡(jiǎn)單歸納：簡(jiǎn)單歸納：訪問(wèn)起始點(diǎn)訪問(wèn)起始點(diǎn) v;若若v的第的第1個(gè)鄰接點(diǎn)沒(méi)訪問(wèn)過(guò)，深度遍歷此鄰接點(diǎn)；個(gè)鄰接點(diǎn)沒(méi)訪問(wèn)過(guò)，深度遍歷此鄰接點(diǎn)；若當(dāng)前鄰接點(diǎn)已訪問(wèn)過(guò)，再找若當(dāng)前鄰接點(diǎn)已訪問(wèn)過(guò)，再找v的第的第2個(gè)鄰接點(diǎn)重新遍歷。個(gè)鄰接點(diǎn)重新遍歷。第47頁(yè)V1V2V4V5V3V7V6V8例深度遍歷：V1 V2 V4 V8 V5 V6 V3 V7V1V2V4V5V3V7V6V8例深度遍

38、歷：V1 V2 V4 V8 V3 V6 V7 V51654327131791812752410深度遍歷：V1 V2 V4 V3 V5 V6練習(xí)：第48頁(yè)1 2 3 4 5 61 0 0 0 0 0 00 0 0 0 0 03 0 0 0 0 0 04 0 0 0 0 0 05 0 0 0 0 0 06 0 0 0 0 0 0000000123456010000100001000010101鄰鄰接接矩矩陣陣A輔助數(shù)組輔助數(shù)組 visited n visited n 起起點(diǎn)點(diǎn)開(kāi)輔助數(shù)組開(kāi)輔助數(shù)組 visited n！例：例：1 2 3 4 561 0000 0 0030 0 0040 0 0 05

39、 00 006 0 0 000第49頁(yè)DFS1(A, n, v) visit（v）; visitedv=1; for( j=1; jlink; while (!p) v=p-data; if(! visitedv ) DFS2(list, v, p); p=p-link; 第54頁(yè)（設(shè)圖中有（設(shè)圖中有 n 個(gè)頂點(diǎn)，個(gè)頂點(diǎn)，e 條邊）條邊）如果用鄰接矩陣來(lái)表示圖，遍歷圖中每一個(gè)頂點(diǎn)都要如果用鄰接矩陣來(lái)表示圖，遍歷圖中每一個(gè)頂點(diǎn)都要從頭掃描該頂點(diǎn)所在行，因此遍歷全部頂點(diǎn)所需的從頭掃描該頂點(diǎn)所在行，因此遍歷全部頂點(diǎn)所需的時(shí)間為時(shí)間為O(n2)。如果用鄰接表來(lái)表示圖，雖然有如果用鄰接表來(lái)表示圖，雖然有

40、 2e 個(gè)表結(jié)點(diǎn)，但只個(gè)表結(jié)點(diǎn)，但只需掃描需掃描 e 個(gè)結(jié)點(diǎn)即可完成遍歷，加上訪問(wèn)個(gè)結(jié)點(diǎn)即可完成遍歷，加上訪問(wèn) n個(gè)頭結(jié)個(gè)頭結(jié)點(diǎn)的時(shí)間，因此遍歷圖的時(shí)間復(fù)雜度為點(diǎn)的時(shí)間，因此遍歷圖的時(shí)間復(fù)雜度為O(n+e)。結(jié)論：結(jié)論： 稠密圖適于在鄰接矩陣上進(jìn)行深度遍歷；稠密圖適于在鄰接矩陣上進(jìn)行深度遍歷； 稀疏圖適于在鄰接表上進(jìn)行深度遍歷。稀疏圖適于在鄰接表上進(jìn)行深度遍歷。第55頁(yè)基本思想：基本思想：仿樹(shù)的層次遍歷過(guò)程。仿樹(shù)的層次遍歷過(guò)程。Breadth_First Searchv1v2v3v8v7v6v4v5起點(diǎn)起點(diǎn)遍歷步驟遍歷步驟起點(diǎn)起點(diǎn)第56頁(yè)V1V2V4V5V3V7V6V8例例V1V2V4V5V3

41、V7V6V8廣度遍歷：V1 V2 V3 V4 V5 V6 V7 V8廣度遍歷：V1 V2 V3 V4 V5 V6 V7 V8V1V2V4V5V3V7V6V8例廣度遍歷：V1 V2 V3 V4 V6 V7 V8 V5練習(xí)：第57頁(yè)廣度優(yōu)先搜索（遍歷）步驟：廣度優(yōu)先搜索（遍歷）步驟：簡(jiǎn)單歸納：簡(jiǎn)單歸納：在訪問(wèn)了起始點(diǎn)在訪問(wèn)了起始點(diǎn)v之后，依次訪問(wèn)之后，依次訪問(wèn) v的鄰接點(diǎn)；的鄰接點(diǎn)；然后再依次訪問(wèn)這些頂點(diǎn)中未被訪問(wèn)過(guò)的鄰接點(diǎn)；然后再依次訪問(wèn)這些頂點(diǎn)中未被訪問(wèn)過(guò)的鄰接點(diǎn)；直到所有頂點(diǎn)都被訪問(wèn)過(guò)為止。直到所有頂點(diǎn)都被訪問(wèn)過(guò)為止。廣度優(yōu)先搜索是一種分層的搜索過(guò)程，每向前走一步廣度優(yōu)先搜索是一種分層的搜索過(guò)程，每向前走一步可能訪問(wèn)一批頂點(diǎn)，不像深度優(yōu)先搜索那樣有回退的可能訪問(wèn)一批頂點(diǎn)，不像深度優(yōu)先搜索那樣有回退的情況。因此，廣度優(yōu)先搜索不是一個(gè)遞歸的過(guò)程，其情況。因此，廣度優(yōu)先搜索不是一個(gè)遞歸的過(guò)程，其算