第3章 非線性數(shù)據(jù)結(jié)構(gòu)

第3章非線性數(shù)據(jù)結(jié)構(gòu)3.1樹及其基本概念3.2二叉樹

3.3二叉樹的遍歷3.4樹的存儲結(jié)構(gòu)和遍歷3.5樹、森林與二叉樹的轉(zhuǎn)換3.6霍夫曼樹及其應(yīng)用3.7圖及其基本概念3.8圖的存儲結(jié)構(gòu)3.9圖的遍歷3.10圖的連通性及最小生成樹本章小節(jié)習(xí)題

老祖宗兒子孫子曾孫

定義：樹是由n(n≥0)個結(jié)點組成的有限集合T。其中有且僅有一個結(jié)點稱為根結(jié)點，其余結(jié)點可分為m(m≥0)個互不相交的有限集合T1，T2，……Ti

…

Tm，每個Ti本身又是一棵樹，稱為根結(jié)點的子樹。樹的定義是遞歸的！

基本術(shù)語

結(jié)點（node）：樹中元素。

結(jié)點的度(degree)：結(jié)點擁有的子樹數(shù)。樹形數(shù)據(jù)結(jié)構(gòu)是結(jié)點之間有分支，有層次的非線性數(shù)據(jù)結(jié)構(gòu)。一棵樹中最大的結(jié)點度數(shù)為樹的度。張源張明張亮張麗張林張維張平張華張群張晶張磊圖3-1樹型結(jié)構(gòu)3.1樹及其基本概念

雙親（parents）：孩子結(jié)點的上層結(jié)點稱為這些結(jié)點的雙親。

兄弟（sibling）：同一雙親的孩子。

結(jié)點的層次（level）：從根結(jié)點開始算起，根為第一層，根的直接后繼結(jié)點為第二層，依次類推。

深度（depth）：樹中結(jié)點的最大層次數(shù)。

有序樹：樹中結(jié)點在同一層中按從左到右有序排列，不能互換的稱為有序樹。

森林：m(m≥0)棵互不相交的樹的集合。

孩子(child)：除根結(jié)點外，每個結(jié)點都是其前趨結(jié)點的孩子。

葉子(leaf)：度為0的結(jié)點。

在計算機中表示一棵樹時，就隱含著一種確定的相對次序，所以后面我們討論的都是有序樹。3.2.1二叉樹的定義及其性質(zhì)二叉樹是n(n≥0)個結(jié)點的有限集合，它或為空樹或是由一個根結(jié)點和兩棵分別稱為左子樹和右子樹的互不相交的二叉樹構(gòu)成。二叉樹也是遞歸定義的！二叉樹的特點：(1)每個結(jié)點最多有兩棵子樹(2)有左右之分。ABEFABEF兩棵不同的二叉樹3.2二叉樹圖3-2二叉樹的五種基本形態(tài)

1二叉樹的定義例3-1

畫出具有3個結(jié)點的樹和二叉樹的所有不同形態(tài)。圖3-3有3個結(jié)點的所有樹的不同形態(tài)圖3-43個結(jié)點的所有二叉樹的不同形態(tài)

(2)圖3-3有3個結(jié)點的所有樹的不同形態(tài)解：(1)具有3個結(jié)點的樹有2種不同的形態(tài)，如圖3-3所示。注意：樹和二叉樹的區(qū)別主要是二叉樹的結(jié)點的子樹要區(qū)分左子樹和右子樹，即使在結(jié)點只有一個子樹的情況下，也要明確指出該子樹是左子樹還是右子樹。2二叉樹的性質(zhì)

性質(zhì)一：二叉樹的第i層上至多有2i-1(i≥1)個結(jié)點。

性質(zhì)二：深度為k的二叉樹上至多含有2k-1個結(jié)點。

性質(zhì)三：在任意的二叉樹T中，若有n0個葉子結(jié)點，n2個度為2的結(jié)點，則必有:n0=n2+1。性質(zhì)三證明：綜合這二者關(guān)系可得性質(zhì)三另一方面，度為1的結(jié)點有1個孩子，度為2的結(jié)點有2個孩子。故二叉樹中孩子結(jié)點總數(shù)為：n1+2n2，又二叉樹中只有根結(jié)點不是任何結(jié)點的孩子，故總結(jié)點數(shù)為n=n1+2n2+1；設(shè)ni表示度數(shù)為i的結(jié)點，則總結(jié)點數(shù)n為：n=n0+n1+n2；

幾種特殊形式的二叉樹

滿二叉樹:深度為k的二叉樹的,并且含有2k-1個結(jié)點。特點：每一層的結(jié)點數(shù)都是最大結(jié)點數(shù)圖3-6深度為4的滿二叉樹

完全二叉樹：對滿二叉樹的結(jié)點進(jìn)行連續(xù)編號：從根結(jié)點起，自上而下逐層從左到右給每個結(jié)點編一個從1開始的順序號。圖3-6就成為圖3-7。圖3-7深度為4的滿二叉樹深度為k，有n個結(jié)點的二叉樹，當(dāng)且僅當(dāng)其每一個結(jié)點都與深度為k的滿二叉樹中的編號從1到n的結(jié)點一一對應(yīng)時，稱之為完全二叉樹。如圖3-8所示是一棵深度為4的完全二叉樹。圖3-8深度為4的完全二叉樹特點：(1)葉子只可能在層次最大的兩層上出現(xiàn)。

(2)最下面一層的結(jié)點都集中在該層最左邊的若干位置上。思考：深度為h的完全二叉樹的結(jié)點數(shù)目不少于？2h-1

性質(zhì)四：具有n個結(jié)點的完全二叉樹的深度為證明：假設(shè)深度為k，則根據(jù)性質(zhì)22k?1?1＜n≤2k?1或2k?1≤n＜2k于是k?1≤lbn＜k

因為k是整數(shù)所以

如果對一棵有n個結(jié)點的完全二叉樹的結(jié)點按層序編號(從第1層到第n層，每層從左到右)，則對任一結(jié)點i(1≤i≤n)，有

(1)如果i=1，則i是二叉樹的根，無雙親；如果i>1，則其雙親是結(jié)點。

(2)如果2i>n，則結(jié)點i無左孩子；否則其左孩子是2i。

(3)如果2i+1>n，則結(jié)點i無右孩子；否則其右孩子是結(jié)點2i+1。證明從略。

性質(zhì)五：

平衡二叉樹特點：左子樹與右子樹的深度之差的絕對值不超過1，且左、右子樹也都是平衡二叉樹。例3-2

圖3-9中有兩棵二叉樹，試判定其是否是平衡二叉樹？圖3-9兩棵二叉樹3.2.2二叉樹的存儲結(jié)構(gòu)1二叉樹的順序存儲結(jié)構(gòu)

為實現(xiàn)順序存儲，必須把二叉樹中所有結(jié)點按照一定的次序組成一個線性序列，使得結(jié)點在這個序列中的相互位置能反映出結(jié)點之間的邏輯關(guān)系。

對于完全二叉樹，從樹根起，自上層到下層，每層從左到右的給結(jié)點進(jìn)行編號，就能得到一個反映整棵二叉樹結(jié)構(gòu)的線性序列。

對于完全二叉樹，按圖3-8中的編號順序存儲，就能得到一個足以反映整個二叉樹結(jié)構(gòu)的線性序列。將完全二叉樹中所有結(jié)點按編號順序依次存儲到一組連續(xù)的存儲單元(即向量)中，既不浪費內(nèi)存，又可用地址公式確定其結(jié)點的位置。但對于一般的二叉樹，順序分配造成內(nèi)存浪費，圖3-8所示的完全二叉樹，其順序存儲結(jié)構(gòu)如圖3-10(a)所示。

圖3-8深度為4的完全二叉樹圖3-10二叉樹的順序存儲結(jié)構(gòu)在最壞情況下，一個深度為k且只有k個結(jié)點的單支樹(樹中無度為2的結(jié)點)卻需要2k–1個存儲單元。浪費很大。所以，一般用鏈表來表示二叉樹。

2二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)二叉鏈表lchilddatarchild結(jié)點結(jié)構(gòu)的直觀形式1：鏈表中每個結(jié)點由數(shù)據(jù)域(data)、左指針域(lchild)及右指針(rchild)構(gòu)成。這種存儲結(jié)構(gòu)又稱為二叉鏈表。結(jié)點的結(jié)構(gòu)1：圖3-11二叉樹及其二叉鏈表存儲結(jié)構(gòu)(a）ABCDEFA^BDE^^F^^C^^root(b）為便于找到結(jié)點的雙親，還可增加一個指向其雙親的指針域(parent)。由這種結(jié)點結(jié)構(gòu)所得的二叉樹存儲結(jié)構(gòu)稱為三叉鏈表。lchilddataparentrchild結(jié)點的結(jié)構(gòu)2：結(jié)點結(jié)構(gòu)的直觀形式2：圖3-12二叉樹及三叉鏈表存儲結(jié)構(gòu)(a)ABCDEF三叉鏈表(b)3.3二叉樹的遍歷

遍歷二叉樹就是按一定的次序，系統(tǒng)地訪問樹中的所有結(jié)點，使每個結(jié)點恰好被訪問一次。所謂訪問結(jié)點，其含義是很廣的，可以理解為對結(jié)點的增、刪、修改等各種運算的抽象。在本節(jié)討論中，假定訪問結(jié)點即為輸出結(jié)點數(shù)據(jù)域值。二叉樹的遍歷是最重要和最基本的運算，二叉樹的許多操作都是以遍歷為基礎(chǔ)的。

遍歷的含義：指沿某條搜索路線，依次訪問數(shù)據(jù)結(jié)構(gòu)中的全部結(jié)點，而且每個結(jié)點只被訪問一次。二叉樹的遍歷：是指依次遍歷根結(jié)點、左子樹及右子樹。對于線性結(jié)構(gòu)來說，因此只需從開始結(jié)點順序掃描每個結(jié)點即可。但是二叉樹為非線性結(jié)構(gòu)，每個結(jié)點最多可有兩個后繼，因此必須人為設(shè)定遍歷路徑！以D，L，R分別表示訪問根結(jié)點、遍歷左子樹，遍歷右子樹DLR，LDR，LRD，DRL，RDL，RLD排列組合{DLR，LDR，LRD

}規(guī)定先左后右三種基本遍歷方法：DLR：先序遍歷LDR：中序遍歷LRD：后序遍歷二叉鏈表的C語言描述如下：structtnode{ intdata; structtnode*lchild,*rchild; }typedefstructtnodeTNODE;算法3-1

先序遍歷根結(jié)點指針為bt的二叉樹。voidpreorder(TNODE*bt) { if(bt!=NULL) { printf(''%d\n'',bt->data); preorder(bt->lchild); preorder(bt->rchild); } }根據(jù)先序遍歷的定義，先序遍歷二叉樹的遞歸算法如下：算法3-2

中序遍歷根結(jié)點指針為bt的二叉樹。voidinorder(TNODE*bt) { if(bt!=NULL) { inorder(bt->lchild); printf(''%d\n'',bt->data); inorder(bt->rchild); } }根據(jù)中序遍歷的定義，中序遍歷二叉樹的遞歸算法如下：算法3-3

后序遍歷根結(jié)點指針為bt的二叉樹。voidpostorder(TNODE*bt) { if(bt!=NULL) { postorder(bt->lchild); postorder(bt->rchild); printf(''%d\n'',bt->data); }}

根據(jù)后序遍歷的定義，后序遍歷二叉樹的遞歸算法如下：ABECFGD中序遍歷結(jié)果：CBDAEGFLDRLDRLDRCnilnilBLDRDnilnilALDRELDRFLDRGnilnilnilnil先序遍歷結(jié)果：后序遍歷結(jié)果：ABCDEFGCDBGFEA下面重點以中序遍歷為例，討論二叉樹的遍歷算法。

算法3-4

中序遍歷bt所指二叉樹，s為存儲二叉樹結(jié)點指針的工作棧。

Step1.[初始化]置堆棧s為空，設(shè)置臨時指針變量p(bt→p)；

Step2.[判定p==NULL]若p==NULL，則執(zhí)行Step4；上述示例給出了中序遍歷的非遞歸算法思路：利用一個輔助堆棧S，可以寫出中序遍歷二叉樹的非遞歸算法。

Step3.[P進(jìn)棧]將p指針入棧，然后置p=p->lchild，返回Step2；

Step4.[取棧頂元素，并退棧]若棧s為空，則算法結(jié)束，否則，將棧頂元素置指針變量P；

Step5.[訪問結(jié)點p]訪問結(jié)點P，然后置p=p->rchild，并返回Step2。

#defineNm /*m為二叉樹的結(jié)點個數(shù)*/voidinorderf(TNODE*pt) { TNODE*p; TNODE*s[N]; inttop=?1;//Step1. p=bt;//Step1.

while((p!=NULL)||(top!=?1))//Step2.

如果設(shè)定棧s采用順序存儲結(jié)構(gòu)，則可給出C語言描述如下。{ while(p!=NULL)//Step3.

{top++; s[top]=p; p=p->lchild;} if(top!=?1)//Step4.

{p=s[top];//Step5.

top??; p=p->rchild;}}}

printf(''%d\n'',p->data);//先序遍歷

分析此算法的運算量，假定二叉樹T有n個結(jié)點，每個結(jié)點都要入棧和出棧一次。因此，入棧和出棧都要執(zhí)行n次，對結(jié)點的訪問當(dāng)然也需執(zhí)行n次。這樣，中序遍歷二叉樹算法的時間復(fù)雜度為O(n)。

例3-4如圖3-12所示的二叉樹表示下述表達(dá)式：a+b*c?e/f

試寫出它的三種遍歷序列。

解：先序遍歷二叉樹，按訪問結(jié)點的先后次序?qū)⒔Y(jié)點排列起來，可得先序遍歷序列為：?+a*bc/ef中序遍歷序列為：

a+b*c?e/f后序遍歷序列為：

abc*+ef/?

從表達(dá)式來看，以上三個序列恰好為表達(dá)式的前綴表示(波蘭式)、中綴表示和后綴表示(逆波蘭式)。圖3-12二叉樹

3.4樹的存儲結(jié)構(gòu)和遍歷

樹在計算機內(nèi)存儲，可以用順序存儲方式、也可以用鏈?zhǔn)酱鎯Ψ绞剑@主要取決于要對樹結(jié)構(gòu)進(jìn)行什么運算。二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)（1）從結(jié)點指針域的個數(shù)是否固定來區(qū)分：定長結(jié)點和不定長結(jié)點；樹的鏈?zhǔn)椒峙洌?）從一個結(jié)點的各指針域存放的指針值的性質(zhì)來區(qū)分：指向其所有孩子的多重鏈表和指向長子(最左邊的孩子)及次弟(右鄰的兄弟)的二叉鏈表。

二叉鏈表表示法又稱二叉樹表示法，或孩子兄弟表示法。即以二叉鏈表作為樹的存儲結(jié)構(gòu)。鏈表中結(jié)點的兩個指針域分別指向該結(jié)點的第一個孩子和下一個兄弟結(jié)點。

1．二叉鏈表表示法childdatabrother圖3-13是一棵樹，該樹的二叉鏈表如圖3-14所示。利用這種存儲結(jié)構(gòu)便于實現(xiàn)各種樹的操作，首先易于實現(xiàn)找結(jié)點孩子等的操作，如果再為每個結(jié)點增設(shè)一個PARENT域，則同樣能方便地實現(xiàn)求某結(jié)點雙親的操作。二叉鏈表結(jié)點的直觀表示：圖3-13樹圖3-14圖3-13中樹的二叉鏈表

(2)后序遍歷樹：先從左到右依次后根遍歷每棵子樹，然后訪問根結(jié)點。如后序遍歷圖3-13所示的樹，得到的結(jié)點序列為：DGHIEBFCA。

2．樹的遍歷次序：先序遍歷樹和后序遍歷樹(1)先序遍歷樹：先訪問樹的根結(jié)點，然后從左到右依次先序遍歷根的每棵子樹。如先序遍歷圖3-13所示的樹，得到的結(jié)點序列為：ABDEGHICF。3.5樹、森林與二叉樹的轉(zhuǎn)換

由于二叉樹和樹都可用二叉鏈表作為存儲結(jié)構(gòu)，則以二叉鏈表作為媒介可導(dǎo)出樹與二叉樹之間的一個對應(yīng)關(guān)系。圖3-15樹與二叉樹的對應(yīng)關(guān)系

步驟：

(1)加線：親兄弟之間加一虛連線。

(2)抹線：抹掉(除最左一個孩子外)該結(jié)點到其余孩子之間的連線。

(3)旋轉(zhuǎn)：新加上去的虛線改實線且均向右斜(rchild)，原有的連線均向左斜(lchild)。1．一般樹轉(zhuǎn)換為二叉樹

例3-5將圖3-16(a)所示的一般樹轉(zhuǎn)換為二叉樹。

解：轉(zhuǎn)換過程如圖3-16(a)、(b)、(c)、(d)所示(a)(b)(c)(d)加線抹線旋轉(zhuǎn)圖3-16一般樹轉(zhuǎn)換為二叉樹的操作過程(a)一般樹；(b)加線后；(c)抹線后；(d)旋轉(zhuǎn)后

步驟：

(1)將各棵樹分別轉(zhuǎn)換為二叉樹。

(2)按給出森林中樹的次序，依次將后一棵二叉樹作為前一棵二叉樹根結(jié)點的右子樹，則第一棵樹的根結(jié)點是轉(zhuǎn)換后二叉樹的根。2．森林轉(zhuǎn)換為二叉樹森林是樹的有限集合，利用樹的轉(zhuǎn)換思想，可以實現(xiàn)森林到二叉樹的轉(zhuǎn)換。

例3-6將圖3-17(a)的森林轉(zhuǎn)換成二叉樹

解：轉(zhuǎn)換過程如圖3-17(b)、(c)所示。(a)

例3-6將圖3-17(a)的森林轉(zhuǎn)換成二叉樹(a)森林(b)各棵數(shù)對應(yīng)的二叉樹(c)轉(zhuǎn)換成的二叉樹圖3-17森林轉(zhuǎn)換成對應(yīng)的二叉樹的過程思考：將如下二叉樹轉(zhuǎn)換成森林？轉(zhuǎn)換結(jié)果唯一嗎？

結(jié)點間的路徑長度：從樹中一個結(jié)點到另一個結(jié)點之間的分支構(gòu)成這兩個結(jié)點之間的路徑，路徑上的分支數(shù)稱為這兩個結(jié)點之間的路徑長度?；舴蚵鼧?HuffmanTree)，又稱最優(yōu)樹，是一類帶權(quán)路徑長度最短的樹。1．樹的路徑長度和帶權(quán)路徑長度

樹的路徑長度：從樹根到樹中每一個結(jié)點的路徑長度之和稱為樹的路徑長度，一般記作PL。3.6霍夫曼樹及其應(yīng)用如圖3-18所示的兩棵二叉樹，其路徑長度分別計算如下：

(a)?PL=0+1+1+2+2+2+2+3=13(b)?PL=0+1+1+2+2+2+3=11

容易知道，對于有n個結(jié)點的所有二叉樹而言，滿二叉樹或者完全二叉樹具有最小的路徑長度。我們把路徑長度的概念推廣到帶權(quán)的路徑長度(WeightedPathLength)。注意：只有葉子節(jié)點有權(quán)值則它們的帶權(quán)路徑長度分別為

(a)?WPL=2*2+4*2+6*2+8*2=40(b)?WPL=4*2+6*3+8*3+2*1=52(c)?WPL=8*1+6*2+4*3+2*3=38

由此可見，帶權(quán)路徑長度最小的二叉樹不一定是完全二叉樹。通常，在帶權(quán)路徑長度最小的二叉樹中，權(quán)值越大的終端結(jié)點離二叉樹的根越近。

給定：一組權(quán)值{W1，W2，…，Wn}

構(gòu)造：一棵有n個葉子結(jié)點的最小帶權(quán)路徑長度的二叉樹，即霍夫曼樹或者最優(yōu)二叉樹，相應(yīng)的算法稱為霍夫曼算法。2．霍夫曼樹和霍夫曼編碼(1)給定的權(quán)值為{W1，W2，…，Wn}，據(jù)此生成森林F={T1，T2，…，Tn}(2)在F中選取兩棵根結(jié)點的權(quán)值最小和次小的二叉樹作為左、右子樹構(gòu)造一棵新的二叉樹，新二叉樹根結(jié)點的權(quán)值為其左、右子樹根結(jié)點的權(quán)值之和。

(3)在F中刪除這兩棵權(quán)值最小和次小的二叉樹，同時將新生成的二叉樹并入森林F中。

(4)重復(fù)(2)和(3)，直到F中只有一棵二叉樹為止。例如，給定一組權(quán)值{2，7，4，8}，圖3-20給出了構(gòu)造相應(yīng)霍夫曼樹的過程。圖3-20霍夫曼樹的構(gòu)造過程

霍夫曼樹應(yīng)用：信息編碼，判定過程，排序過程（1）信息編碼中權(quán)值可看成是某個符號出現(xiàn)的頻率；（2）判定過程中，權(quán)值可看成是某類數(shù)據(jù)出現(xiàn)的頻率；（3）排序過程中，權(quán)值可看成是已排好次序而待合并的序列的長度等。不等長二進(jìn)制前綴編碼：

在信息通信中，以字符傳送為主。眾所周知，字符集中的每個字符使用的頻率是不等的。如果能讓使用頻率較高的字符的編碼盡可能短，這樣就可以縮短整個信息通信過程中所需傳送的二進(jìn)制編碼序列的長度，從而達(dá)到節(jié)省通信資源的目的。

問題：設(shè)D={d1，d2，…，dn}為需要編碼的字符集合。又設(shè)Wi為di在文本中出現(xiàn)的次數(shù)，現(xiàn)要求對D進(jìn)行二進(jìn)制編碼。

解決方法：以Wi為權(quán)值構(gòu)造霍夫曼樹。在生成的霍夫曼樹中，令所有的左分支取編碼為0，令所有的右分支取編碼為1，將從根結(jié)點出發(fā)到葉子結(jié)點的路徑上各左、右分支的編碼順序排列就得到了該葉子結(jié)點所對應(yīng)的字符的二進(jìn)制前綴編碼，也稱為霍夫曼編碼。

例給出下面一個文本：

CASTCATSSATATATASA

則有D={C，A，S，T}、W={2，7，4，5}，得到D中每個字符的二進(jìn)制前綴編碼為

C：110 S：111 A：0T：10霍夫曼樹

可以看出，出現(xiàn)次數(shù)最多的字符，其編碼位數(shù)最少。相應(yīng)文本的編碼為

110011110110010111 111010 010 0 1001110

21543圖3-22無向圖（1）圖：是由頂點集合和頂點間關(guān)系組成，記作G=（V，R）。V為頂點集合，V={v1，v2，…，vn}。R是兩個頂點之間的關(guān)系的集合。（2）無向圖：當(dāng)圖中頂點之間關(guān)系為無序時，稱為無向圖。

特點：(Vi,Vj)=(Vj,Vi)，稱為邊。無向圖記作G（V，E）。V=（v1，v2，v3，v4，v5）E={(v1,v2)，(v1,v3)，(v1,v4)，(v2,v3)，(v3,v5)}對圖3-22：3.7圖及其基本概念1324圖3-23有向圖（3）有向圖：當(dāng)圖中頂點之間關(guān)系為有序時，稱為有向圖。V=（v1，v2，v3，v4）E={<v1,v2>，<v1,v3>，<v3,v4>，<v4,v1>}圖中有序?qū)?lt;Vi,Vj>稱為弧，其中Vi為弧尾(起始點)，Vj為弧頭(終點)。此時<Vi,Vj>≠

<Vj,Vi>

。有向圖記作G（V，A）。3.7圖及其基本概念（4）子圖：設(shè)有兩個圖GA和GB，且滿足

V(GB)V(GA)E(GB)E(GA)則稱GB是GA的子圖。如圖3-24所示。

圖3-24圖與子圖

（5）帶權(quán)圖：無向圖中每條邊附一個對應(yīng)的數(shù)（權(quán)），該圖為帶權(quán)圖。

圖3-25帶權(quán)圖(網(wǎng))（6）路徑：圖中一個頂點的序列稱路徑。如v到v'的路徑為(V=Vi0，Vi1，Vi2，…，Vin=V')，<Vi0,Vi1><Vi1,Vi2>…<Vin?1,Vin>都屬于集合E。路徑上弧的數(shù)目稱為該路徑的長度。

在無向圖中，若每一對頂點之間都有路徑，則稱此圖為連通圖。在有向圖中，若每一對頂點u和v之間都存在v到u及u到v的路徑，則稱此圖為強連通圖。（7）鄰接點：在無向圖中，如果邊(u,v)∈E，則u和v互為鄰結(jié)點，即u是v的鄰結(jié)點，v也是u的鄰結(jié)點。在有向圖中，如果弧<u,v>∈E，則v是u的鄰結(jié)點。稱u鄰接到v，或頂點v鄰接自頂點u。(8)頂點的度：在無向圖中，頂點的度就是和該頂點相關(guān)聯(lián)的邊的數(shù)目，記為TD(V)。如圖3-22中，TD(V3)=3。21543圖3-221324圖3-23入度、出度：在有向圖中，以某頂點為尾的（初始點）的弧的數(shù)目稱為該頂點的出度；而以該頂點為頭（終端點）的弧的數(shù)目稱為該頂點的入度。圖3-23中，ID(V3)=1,OD(V3)=1,TD(V3)=ID(V3)+OD(V3)=2。1324圖3-233.8圖的存儲結(jié)構(gòu)

要求：掌握鄰接矩陣表示法和鄰接表表示法。

需在計算機中存儲：（1）圖的頂點的集合；（2）頂點之間的聯(lián)系，即邊或弧的集合。3.8.1鄰接矩陣

（1）用一維數(shù)組存放圖中所有頂點的信息；（2）用一個二維數(shù)組來存放數(shù)據(jù)元素之間的關(guān)系的信息(即邊或弧的集合E)。這個二維數(shù)組稱之為鄰接矩陣。解決辦法：

鄰接矩陣是表示頂點之間的鄰接關(guān)系的矩陣。設(shè)G=(V，E)是有n(n≥1)個頂點的圖，則G的鄰接矩陣A是一個具有下列性質(zhì)的n×n階矩陣：若若若將頂點編號為1～Vtxnum，設(shè)弧上或邊上無權(quán)值，則圖的存儲結(jié)構(gòu)可以簡化為用一個二維數(shù)組表示：

intadjmatrix[vtxnum][vtxnum]；

123451234512341234215431324圖3-26圖與鄰接矩陣之間的轉(zhuǎn)換借助于接矩陣，能夠判定任意兩個頂點之間是否有邊（弧）相連，亦能求得各個頂點的度。（1）在無向圖中，頂點的度是鄰接矩陣中該點所在行（列）的元素之和；（2）在有向圖中，頂點的出度是該頂點所在行的元素之和，頂點的入度是頂點所在列的元素之和。網(wǎng)的鄰接矩陣可定義為：其中Wij是邊(Vi,Vj)或弧<Vi,Vj>上的權(quán)值。

鄰接表包括兩個部分：一部分是鏈表；另一部分是向量。3.8.2鄰接表

在鄰接表中，對圖中每個頂點建立一個單鏈表，第i個單鏈表中的結(jié)點包含了頂點Vi的所有鄰接頂點。結(jié)點結(jié)構(gòu)：

為便于鄰接表操作，在每個單鏈表上附設(shè)一個頭結(jié)點。頭結(jié)點結(jié)構(gòu)：鄰接表中將每個單鏈表的頭結(jié)點以順序結(jié)構(gòu)的形式存儲，鄰接表的存儲結(jié)構(gòu)可以用C語言描述如下：

#defineVTXUNM n

/*n為圖中頂點個數(shù)的最大可能值*/structarcnode{ intadjvex; floatdata; structarcnode*nextarc;};typedefstructarcnodeARCNODE;structheadnode{ intvexdata; ARCNODE*firstarc; }adjlist[VTXUNM];/*頂點Vi的鄰結(jié)點在圖中的位置為整數(shù)*//*結(jié)點數(shù)據(jù)類型*//*將結(jié)點arcnode重新命名為ARCNODE*//*定義鄰接表數(shù)組adjlist*/

對于圖3-29中的圖G4和圖3-30中的圖G5，其鄰接表存儲結(jié)構(gòu)如圖3-29(b)和圖3-30(b)所示。圖3-29有向帶權(quán)圖及其鄰接表圖3-30無向圖及其鄰接表

鄰接表優(yōu)點：容易找到任一頂點的第一個鄰接點和下一個鄰接點鄰接表缺點：要判定任意兩個頂點(Vi和Vj)之間是否有邊或弧相連，則需搜索第i個或第j個鏈表，因此不及鄰接矩陣方便。注意：（1）鄰接表不惟一；（2）對于有向圖，其鄰接表中第i個單鏈表的結(jié)點個數(shù)就是此結(jié)點的出度；對于無向圖，其鄰接表中第i個單鏈表的結(jié)點個數(shù)就是此結(jié)點的度。3.9圖

的

遍

歷

和樹的遍歷類似，從圖中某一頂點出發(fā)訪問圖中其余的頂點，使每個頂點都被訪問且僅被訪問一次，這個過程就叫做圖的遍歷(traversinggraph)。要求：能寫圖出的深度優(yōu)先搜索和廣度優(yōu)先搜索的序列

同一頂點可能被訪問多次，因此，在遍歷圖的過程中，必須記下每個已訪問過的頂點。為此，設(shè)一個輔助數(shù)組visited[n]，它的初值為“假”或者零，一旦訪問了頂點Vi，便置visited[i]為“真”或者為被訪問時的次序號。

通常有兩種遍歷圖的方法：（1）深度優(yōu)先搜索；（2）廣度優(yōu)先搜索。

算法步驟：

(1)首先訪問圖G的指定起始點V0；

(2)從V0出發(fā)，訪問一個與V0鄰接的頂點W1后，再從W1出發(fā)，訪問與W1鄰接且未被訪問過的頂點W2。從W2出發(fā)，重復(fù)上述過程，直到遇到一個所有與之鄰接的頂點均被訪問過的頂點為止；

1．深度優(yōu)先搜索圖的深度優(yōu)先搜索遍歷(depth-firstsearch)類似于樹的先序遍歷，是樹的先序遍歷的推廣。

(3)沿著剛才訪問的次序，反向回退到尚有未被訪問過的鄰接點的頂點，從該頂點出發(fā)，重復(fù)步驟(2)、(3)，直到所有被訪問過的頂點的鄰接點都已被訪問過為止；若此時圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作起始點，重復(fù)上述過程，直至圖中所有頂點都被訪問到為止。326451987遍歷結(jié)果：324916587

顯然，這個遍歷過程是個遞歸過程。在設(shè)計具體算法時，首先要確定圖的存儲結(jié)構(gòu)，下面以鄰接表為例，討論深度優(yōu)先搜索法。

例3-7連通圖G6的鄰接表表示如圖3-31所示，以頂點V1為始點，按深度優(yōu)先搜索遍歷圖中所有頂點，寫出頂點的遍歷序列。圖3-31G6及其鄰接表解：訪問序列為：V1→V2→V4→V8→V5→V6→V3→V7。下面給出dfs的算法。算法3-5

深度優(yōu)先搜索的遞歸算法。#defineVTXUNM n/*n為圖中頂點個數(shù)的最大可能值*/structarcnode{ intadjvex; floatdata; structarcnode*nextarc; };typedefstructarcnodeARCNODE;structheadnode{ intvexdata; ARCNODE*firstarc; };structheadnodeG[VTXUNM+1];intvisited[VTXUNM+1];/*訪問標(biāo)志數(shù)組*/voiddfs(structheadnodeG[],intv) { ARCNODE*p; printf(''%d->'',G[v].vexdata); visited[v]=1; p=G[v].firstarc; while(p!=NULL) /*當(dāng)鄰接點存在時*/ { if(visited[p->adjvex]==0) dfs(G,p->adjvex);/*從第v個頂點出發(fā)進(jìn)行dfs*/p=p->nextarc;}};/*找下一鄰接點*/

voidtraver(structheadnodeG[]) { intv; for(v=1;v<=VTXUNM;v++) visited[v]=0; for(v=1;v<=VTXUNM;v++) ifvisited[v]==0dfs(G,v);};/*對所有頂點進(jìn)行dfs*//*訪問標(biāo)志數(shù)組初始值為0*/算法3-6

深度優(yōu)先搜索的非遞歸算法（不要求）。

廣度優(yōu)先搜索(breadth-firstsearch)類似于樹的按層次遍歷的過程。

2．廣度優(yōu)先搜索算法邏輯：從圖中某頂點V0出發(fā)，在訪問了V0之后依次訪問V0的各個未曾被訪問過的鄰接點，然后分別從這些鄰接點出發(fā)廣度優(yōu)先搜索遍歷圖，直至圖中所有已被訪問的頂點的鄰接點都被訪問到。若圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作起始點，重復(fù)上述過程，直至所有頂點都被訪問到。

具體遍歷步驟如下：

(1)訪問V0。

(2)從V0出發(fā)，依次訪問V0的未被訪問過的鄰接點W1，W2，…，Wt。然后依次從W1，W2，…，Wt出發(fā)，訪問各自未被訪問過的鄰接點。

(3)重復(fù)步驟(2)，直到所有頂點的鄰接點均被訪問過為止。326451987第一層次第二層次第三層次起始訪問點

解：遍歷序列如下：V1→V2→V3→V4→V5→V6→V7→V8

例3-8

對連通圖G6，從頂點V1出發(fā)，寫出頂點的廣度優(yōu)先遍歷序列。G6

注意，在bfs算法中，若W1在W2之前訪問，則W1的鄰接點也將在W2的鄰接點之前訪問，這里蘊涵了一個排隊關(guān)系。在實現(xiàn)算法時，需設(shè)一個隊列，每訪問一個頂點后將其入隊，然后將隊頭頂點出列，去訪問與它鄰接的所有頂點，重復(fù)上述過程，直至隊空為止。訪問Vi，置標(biāo)志初始化隊列Vi入隊隊空？隊頭元素V出隊求V的鄰接點WW存在？W訪問過？訪問W，置標(biāo)志并入隊求V的下一個鄰接點結(jié)束YNYNNY廣度優(yōu)先搜索遍歷算法流程：0123456789rearV3326451987V2V6V1V4V5V9V7V8front遍歷次序：由廣度優(yōu)先搜索遍歷的邏輯可見，先訪問的頂點其鄰接頂點也先被訪問，因此在算法中需引進(jìn)一個隊列保存已訪問過的頂點！算法3-7

廣度優(yōu)先遍歷算法。#defineVTXUNM nvoidbfs(structheadnodeG[],intv) {intqueue[VTXUNM]; intrear=VTXUNM?1;front=VTXUNM?1; inti; ARCNODE*p; printf(''%d->'',G[v].vexdata);visited[v]=1; rear=(rear+1)%VTXUNM; queue[rear]=v; /*訪問過的頂點進(jìn)隊列*/ while(rear!=front) {front=(front+1)%VTXUNM; v=queue[front]; p=G[v].firstarc; while(p!=NULL){if(visited[p->adjvex]==0){ printf(''%d->'',G[p->adjvex].vexdata); visited[p->adjvex]=1; rear=(rear+1)%VTXUNM; q