數(shù)據(jù)結(jié)構(gòu)部分線性表樹圖

數(shù)據(jù)結(jié)構(gòu)部分線性表樹圖第一頁，共五十六頁，編輯于2023年，星期三第一部分：線性結(jié)構(gòu)一、線性表最常見的一種線性結(jié)構(gòu)，有兩種存儲(chǔ)方法：順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)1、定義：N個(gè)元素的有限序列，n≥0，通常表示為（a1,a2,…,an）2、特點(diǎn)：元素集合中存在唯一稱作“第一個(gè)”和唯一“最后一個(gè)”元素，除第一個(gè)元素外，每個(gè)元素均只有一個(gè)直接前驅(qū)；除最后一個(gè)元素外，序列中的每個(gè)元素只有一個(gè)直接后繼。3、存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)含義：用一組連續(xù)的存儲(chǔ)單元存放線性表中的數(shù)據(jù)元素。特點(diǎn)：邏輯相鄰的元素，物理位置也相鄰。優(yōu)點(diǎn)和缺點(diǎn)：存取方便，插入刪除操作需要移動(dòng)大量元素。第二頁，共五十六頁，編輯于2023年，星期三第一部分：線性結(jié)構(gòu).鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)含義：存儲(chǔ)數(shù)據(jù)元素的同時(shí)必須存儲(chǔ)元素之間的關(guān)系。用節(jié)點(diǎn)來存儲(chǔ)數(shù)據(jù)元素，節(jié)點(diǎn)地址可以連續(xù)，也可以不連續(xù)。節(jié)點(diǎn)結(jié)構(gòu)：節(jié)點(diǎn)的插入和刪除操作插入操作刪除操作

第三頁，共五十六頁，編輯于2023年，星期三第一部分：線性結(jié)構(gòu)4.其他幾種鏈表結(jié)構(gòu)：雙向鏈表：

每個(gè)節(jié)點(diǎn)包含兩個(gè)指針，分別指出當(dāng)前節(jié)點(diǎn)元素的直接前驅(qū)和直接后繼。循環(huán)鏈表：靜態(tài)鏈表：

借助數(shù)組來描述線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)第四頁，共五十六頁，編輯于2023年，星期三第一部分：線性結(jié)構(gòu)二、棧和隊(duì)列1.棧定義只能通過它的一端來實(shí)現(xiàn)數(shù)據(jù)存儲(chǔ)和檢索的線性結(jié)構(gòu)，也稱為后進(jìn)先出（或先進(jìn)后出）的線性表?；具\(yùn)算初始化棧：InitStack(S)判?？?StackEmpty入棧:Push(S,x)出棧:Pop(S)讀棧頂元素:Top(s)存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)：（順序棧）指用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)自棧頂?shù)綏５椎臄?shù)據(jù)元素，同時(shí)附設(shè)指針top指示棧頂元素的位置。第五頁，共五十六頁，編輯于2023年，星期三第一部分：線性結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)（鏈棧）：為了克服順序?？赡艽嬖谏弦绲牟蛔?，采用鉆鏈表作為存儲(chǔ)結(jié)構(gòu)的棧。棧的應(yīng)用：表達(dá)式求值，括號(hào)匹配，遞歸轉(zhuǎn)非遞歸。2.隊(duì)列定義：是一種先進(jìn)先出（FIFO）的線性表，只允許在表的一端插入元素，表的另一端刪除元素?；具\(yùn)算：

(1)初始化隊(duì)InitQueue(Q)(2)判隊(duì)空Empty(Q)(3)入隊(duì)EnQueue(Q,x)(4)出隊(duì)DeQueue(Q)(5)讀隊(duì)頭元素FrontQue(Q)第六頁，共五十六頁，編輯于2023年，星期三第一部分：線性結(jié)構(gòu)隊(duì)列的存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)（順序隊(duì)列）利用一組地址連續(xù)的存儲(chǔ)單元存放隊(duì)列中的元素，同時(shí)設(shè)置隊(duì)頭指針和隊(duì)尾指針，分別表示當(dāng)前的隊(duì)首元素和隊(duì)尾元素。思考:(1)為什么要引入循環(huán)隊(duì)列？

(2)什么叫假溢出？如何形成的？鏈?zhǔn)酱鎯?chǔ)（鏈隊(duì)列）隊(duì)列的應(yīng)用：常用于需要排隊(duì)的場(chǎng)合：比如操作系統(tǒng)中處理打印任務(wù)，離散事件的計(jì)算模擬等。第七頁，共五十六頁，編輯于2023年，星期三第一部分：線性結(jié)構(gòu)3串即字符串，是一種特殊的線性表，它的數(shù)據(jù)元素僅由一個(gè)字符組成。串的定義是僅由字符構(gòu)成的有限序列，是取值范圍受限的線性表。一般記為：S=‘a(chǎn)1a2…an’，其中S是串名，單引號(hào)括起來的字符序列是串值。幾個(gè)相關(guān)的基本概念空串：長(zhǎng)度為零的串，不包含任何字符?？崭翊河梢粋€(gè)或多個(gè)空格組成的串。子串：由串中任意長(zhǎng)度的連續(xù)字符構(gòu)成的序列稱為子串?？沾侨我獯淖哟?。串相等：兩個(gè)串長(zhǎng)度相等，且對(duì)應(yīng)位置上的字符也相同。串比較：比較大小時(shí)，以ASCII碼值作為依據(jù)?；静僮髻x值strAssign(s,t):將串t賦給串s連接Concat(s,t):串t接續(xù)在串s的尾部，形成一個(gè)新串。第八頁，共五十六頁，編輯于2023年，星期三第一部分：線性結(jié)構(gòu)求串長(zhǎng)StrLength(s)串比較StrCompare(s,t)返回值-1、0、1分別表示s<t,s=t,s>t求子串SubString(s,start,len)串的存儲(chǔ)結(jié)構(gòu)靜態(tài)存儲(chǔ)(即串的順序存儲(chǔ)結(jié)構(gòu))

用一組地址連續(xù)的存儲(chǔ)單元來存儲(chǔ)串值的字符序列。（在程序設(shè)計(jì)語言中可借助字符數(shù)組定義串的存儲(chǔ)空間）。鏈?zhǔn)酱鎯?chǔ)用鏈表存儲(chǔ)串中的字符，每個(gè)節(jié)點(diǎn)中可以存儲(chǔ)一個(gè)字符，也可以存儲(chǔ)多個(gè)字符，注意存儲(chǔ)密度問題,因?yàn)樗苯佑绊懙酱吞幚硇?。串的模式匹配即子串的定位操作，是各種串處理中最重要的運(yùn)算之一。有以下兩種算法：（1）樸素模式匹配算法基本思想：P432（2）改進(jìn)的模式匹配算法基本思想：P433第九頁，共五十六頁，編輯于2023年，星期三第一部分：線性結(jié)構(gòu)4數(shù)組、矩陣和廣義表（1）數(shù)組定義：線性表的元素又是一個(gè)線性表，是定長(zhǎng)線性表在維數(shù)上的一個(gè)擴(kuò)張。特點(diǎn)：

.數(shù)據(jù)元素?cái)?shù)目固定

.數(shù)據(jù)元素具有相同數(shù)據(jù)類型

.數(shù)據(jù)元素的下標(biāo)關(guān)系具有上下界的約束且下標(biāo)有序兩個(gè)基本運(yùn)算其一：給定一組下標(biāo)，存取相應(yīng)的數(shù)據(jù)元素；其二：給定一組下標(biāo)，修改相應(yīng)的數(shù)據(jù)元素中某個(gè)數(shù)據(jù)項(xiàng)的值。存儲(chǔ)結(jié)構(gòu) 由于數(shù)組一般不作插入和刪除運(yùn)算，所以數(shù)組中數(shù)據(jù)元素個(gè)數(shù)和元素之間的關(guān)系固定不變，因此適合采用順序存儲(chǔ)結(jié)構(gòu)。

.二維數(shù)組的存儲(chǔ)方式有兩種：行優(yōu)先：列優(yōu)先：第十頁，共五十六頁，編輯于2023年，星期三第一部分：線性結(jié)構(gòu)（2）矩陣在數(shù)據(jù)結(jié)構(gòu)中，我們研究的是如何存儲(chǔ)矩陣中的元素。特殊矩陣指矩陣中的元素分布有一定的規(guī)律的矩陣。例如：對(duì)稱矩陣、三角矩陣、對(duì)角矩陣。存儲(chǔ)時(shí)，可以將其壓縮存儲(chǔ)在一維數(shù)組中，并建立起每個(gè)非零元素在矩陣中的位置與其一維護(hù)數(shù)組中的位置之間的對(duì)應(yīng)關(guān)系。稀疏矩陣非零元素的個(gè)數(shù)遠(yuǎn)遠(yuǎn)少于零元素的個(gè)數(shù)，且非零元素的分布沒有規(guī)律。第十一頁，共五十六頁，編輯于2023年，星期三第一部分：線性結(jié)構(gòu)5廣義表定義是線性表的推廣一，由零個(gè)或多個(gè)單元素或子表所組成的有限序列。一般記為：LS=（a1,a2,…,an）其中ai(1<=i<=n)

注意與線性表的區(qū)別：基本操作取表頭：head(LS)

取表尾:tail(LS)特點(diǎn)：多層次結(jié)構(gòu)，即廣義表的元素可以是子表 廣義表的元素可以是已經(jīng)定義好的廣義表是一個(gè)遞歸的表，即廣義表的元素可是本廣義表的名字存儲(chǔ)結(jié)構(gòu)通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：有兩種方法，即同層結(jié)點(diǎn)法，表頭表尾法第十二頁，共五十六頁，編輯于2023年，星期三第二部分非線性結(jié)構(gòu)一、樹（一）樹的定義及運(yùn)算1、樹的定義樹是n（n>=0）個(gè)節(jié)點(diǎn)的有限集合，當(dāng)n=0時(shí)，稱為空樹，在任一非空樹中：（1）有且僅有一個(gè)稱為根的節(jié)點(diǎn)；（2）其余節(jié)點(diǎn)可分為m(m>=0)

個(gè)互不相交的有限集T1、T2、

…、Tm,其中Ti又都是一棵樹，并且樂為根節(jié)點(diǎn)的子樹。（遞歸定義）2、樹的基本概念與樹相關(guān)的概念有：雙親、孩子、兄弟節(jié)點(diǎn)的度、葉子節(jié)點(diǎn)、節(jié)點(diǎn)的層次、樹的高度、有序（無序）樹

3、樹的遍歷按照某種次序，獲取樹中全部節(jié)點(diǎn)的信息。第十三頁，共五十六頁，編輯于2023年，星期三第二部分非線性結(jié)構(gòu)（二）二叉樹的定義及基本運(yùn)算、1、二叉樹的定義：二叉樹或?yàn)榭諛?；或是由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱為左子樹和右子樹的、互不交的二叉樹組成。2、二叉樹的運(yùn)算二叉樹的基本運(yùn)算是遍歷，其它運(yùn)算都是建立在遍歷的基礎(chǔ)之上。第十四頁，共五十六頁，編輯于2023年，星期三第二部分非線性結(jié)構(gòu)（三）二叉樹的性質(zhì)（共五個(gè)性質(zhì)）1、在二叉樹的第i

層上至多有2i-1個(gè)結(jié)點(diǎn)。(i≥1)2、深度為k的二叉樹上至多含2k-1個(gè)結(jié)點(diǎn)（k≥1）3、對(duì)任何一棵二叉樹，若它含有n0個(gè)葉子結(jié)點(diǎn)、n2個(gè)度為

2

的結(jié)點(diǎn)，則必存在關(guān)系式：n0=n2+1

兩類特殊的二叉樹：滿二叉樹：指的是深度為k且含有2k-1個(gè)結(jié)點(diǎn)的二叉樹。完全二叉樹：樹中所含的n個(gè)結(jié)點(diǎn)和滿二叉樹中編號(hào)為1至n的結(jié)點(diǎn)一一對(duì)應(yīng)。

4、具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為

log2n+1第十五頁，共五十六頁，編輯于2023年，星期三第二部分非線性結(jié)構(gòu)5、若對(duì)含n個(gè)結(jié)點(diǎn)的完全二叉樹從上到下且從左至右進(jìn)行1

至n

的編號(hào)，則對(duì)完全二叉樹中任意一個(gè)編號(hào)為i

的結(jié)點(diǎn)：

(1)若i=1，則該結(jié)點(diǎn)是二叉樹的根，無雙親,否則，編號(hào)為i/2的結(jié)點(diǎn)為其雙親結(jié)點(diǎn);

(2)若2i>n，則該結(jié)點(diǎn)無左孩子，

否則，編號(hào)為2i的結(jié)點(diǎn)為其左孩子結(jié)點(diǎn)；

(3)若2i+1>n，則該結(jié)點(diǎn)無右孩子結(jié)點(diǎn)，

否則，編號(hào)為2i+1的結(jié)點(diǎn)為其右孩子結(jié)點(diǎn)。第十六頁，共五十六頁，編輯于2023年，星期三第二部分非線性結(jié)構(gòu)(四)二叉樹的存儲(chǔ)結(jié)構(gòu)1、順序存儲(chǔ)結(jié)構(gòu)

(1)存儲(chǔ)要求：用一組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)二叉樹中的數(shù)據(jù)元素，節(jié)點(diǎn)必須排成線性序列，并且該序列能反映出節(jié)點(diǎn)之間的邏輯關(guān)系。

(2)完全二叉樹的存儲(chǔ)完全二叉樹的存儲(chǔ)一般二叉樹的存儲(chǔ)二者比較得知：對(duì)于一般的二叉樹，不宜采用順序存儲(chǔ)結(jié)構(gòu)，對(duì)于完全二叉樹，采用順序存儲(chǔ)結(jié)構(gòu)既簡(jiǎn)單，又節(jié)省空間第十七頁，共五十六頁，編輯于2023年，星期三第二部分非線性結(jié)構(gòu)2、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)可以采用二叉鏈表或三叉鏈表來存儲(chǔ)二叉樹。ABDCEF第十八頁，共五十六頁，編輯于2023年，星期三第二部分非線性結(jié)構(gòu)(五)二叉樹的遍歷1、遍歷的含義：指按照某種策略訪問樹中的每個(gè)節(jié)點(diǎn)，且僅訪問一次。遍歷過程的實(shí)質(zhì)是：將樹中的節(jié)點(diǎn)排成一個(gè)線性序列的過程。2、常見幾種遍歷：先序遍歷算法若二叉樹為空樹，則空操作；否則，（1）訪問根結(jié)點(diǎn)；（2）先序遍歷左子樹；（3）先序遍歷右子樹。voidPreOrder(BiTreeroot){if(root!=null)return;else{printf(“%d”,root->data);PreOrder(root->lchild);PreOrder(roolt->rchild);}}第十九頁，共五十六頁，編輯于2023年，星期三第二部分非線性結(jié)構(gòu)中序遍歷算法：若二叉樹為空樹，則空操作；否則，（1）中序遍歷左子樹；（2）訪問根結(jié)點(diǎn)；（3）中序遍歷右子樹

voidInOrder(BiTreeroot){if(root==null)return;else{InOrder(root->lchild); printf(“%d”,root->data);InOrder(root->rchild); }}第二十頁，共五十六頁，編輯于2023年，星期三第二部分非線性結(jié)構(gòu)后序遍歷算法：若二叉樹為空樹，則空操作；否則，（1）后序遍歷左子樹；（2）后序遍歷右子樹；（3）訪問根結(jié)點(diǎn)。

voidPostOrder(BiTreeroot)

{if(root==null)return; else{PostOrder(root->lchild);PostOrder(root->rchild);printf(“%d”,root->data); }}

第二十一頁，共五十六頁，編輯于2023年，星期三第二部分非線性結(jié)構(gòu)層次遍歷算法：從樹的根結(jié)點(diǎn)出發(fā)，首先訪問第一層的樹的根結(jié)點(diǎn)，然后從左到右依次訪問第二層上的節(jié)點(diǎn)，其次是第三層上的節(jié)點(diǎn)……依次類推，自上而下，自左至右，逐層訪問樹中各層上的節(jié)點(diǎn)。層次遍歷序列：

A

BE

CFDGHK第二十二頁，共五十六頁，編輯于2023年，星期三第二部分非線性結(jié)構(gòu)(六)線索二叉樹1、定義二叉樹的遍歷實(shí)質(zhì)：對(duì)非線性結(jié)構(gòu)進(jìn)行線性化操作，使得每個(gè)結(jié)點(diǎn)（除第一個(gè)和最后一個(gè)結(jié)點(diǎn)外）在線性序列中有且僅有一個(gè)直接前驅(qū)和直接后繼。由于二叉鏈表的存儲(chǔ)結(jié)構(gòu)中，只能找到結(jié)點(diǎn)的左、右孩子的信息，得不到前驅(qū)和后繼信息，因此引入線索二叉樹保存遍歷過程中得到的前驅(qū)和后繼信息。2、建立線索二叉樹第二十三頁，共五十六頁，編輯于2023年，星期三第二部分非線性結(jié)構(gòu)第二十四頁，共五十六頁，編輯于2023年，星期三第二部分非線性結(jié)構(gòu)對(duì)線索鏈表中結(jié)點(diǎn)的約定：

在二叉鏈表的結(jié)點(diǎn)中增加兩個(gè)標(biāo)志域，并作如下規(guī)定：若該結(jié)點(diǎn)的左子樹不空，則Lchild域的指針指向其左子樹，且左標(biāo)志域的值為“指針Link”；否則,Lchild域的指針指向其“前驅(qū)”，且左標(biāo)志的值為“線索Tread”。若該結(jié)點(diǎn)的右子樹不空，則rchild域的指針指向其右子樹，且右標(biāo)志域的值為“指針Link”；否則，rchild域的指針指向其“后繼”，且右標(biāo)志的值為“線索Thread”。

如此定義的二叉樹的存儲(chǔ)結(jié)構(gòu)稱作“線索鏈表”

第二十五頁，共五十六頁，編輯于2023年，星期三第二部分非線性結(jié)構(gòu)思考：畫出下列二叉樹的中序線索二叉樹及其中序線索鏈表。

第二十六頁，共五十六頁，編輯于2023年，星期三第二部分非線性結(jié)構(gòu)(七)二叉樹的應(yīng)用：最優(yōu)二叉樹1.哈夫曼樹（1）相關(guān)概念：結(jié)點(diǎn)的路徑長(zhǎng)度：從根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑上分支的數(shù)目。樹的路徑長(zhǎng)度：

樹中每個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和。樹的帶權(quán)路徑長(zhǎng)度定義為：樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和WPL(T)=WkLkWPL(T)=72+52+23+43+92=60第二十七頁，共五十六頁，編輯于2023年，星期三第二部分非線性結(jié)構(gòu)(2)如何構(gòu)造最優(yōu)二叉樹（Huffuman算法）

①根據(jù)給定的n個(gè)權(quán)值{w1,w2,…,wn}，構(gòu)造n棵二叉樹的集合F={T1,T2,…,Tn}，其中每棵二叉樹中均只含一個(gè)帶權(quán)值為wi的根結(jié)點(diǎn),其左、右子樹為空樹;②在F中選取其根結(jié)點(diǎn)的權(quán)值為最小的兩棵二叉樹，分別作為左、右子樹構(gòu)造一棵新的二叉樹，并置這棵新的二叉樹根結(jié)點(diǎn)的權(quán)值為其左、右子樹根結(jié)點(diǎn)的權(quán)值之和;WPL(T)=74+94+53+42+21=89第二十八頁，共五十六頁，編輯于2023年，星期三第二部分非線性結(jié)構(gòu)③從F中刪去這兩棵樹，同時(shí)加入剛生成的新樹。④重復(fù)(2)和(3)兩步，直至F中只含一棵樹為止。(3)舉例：

已知權(quán)值W={5,6,2,9,7}構(gòu)造一棵哈夫曼樹。步驟如下：（右圖為哈夫曼編碼）第二十九頁，共五十六頁，編輯于2023年，星期三第二部分非線性結(jié)構(gòu)（八）樹和森林1、樹的存儲(chǔ)結(jié)構(gòu)（三種表示方法）(1)雙親表示法：第三十頁，共五十六頁，編輯于2023年，星期三第二部分非線性結(jié)構(gòu)

(2)孩子表示法第三十一頁，共五十六頁，編輯于2023年，星期三第二部分非線性結(jié)構(gòu)第三十二頁，共五十六頁，編輯于2023年，星期三第二部分非線性結(jié)構(gòu)2、樹和林林的遍歷（1）樹的遍歷：先根遍歷后根遍歷（2）森林的遍歷先序遍歷中序遍歷3、樹、森林和二叉樹之間的相互轉(zhuǎn)換

（1）樹、森林轉(zhuǎn)換為二叉樹利用孩子兄弟法實(shí)現(xiàn)轉(zhuǎn)換（P454例）（2）二叉樹轉(zhuǎn)換為樹和森林（P454例）第三十三頁，共五十六頁，編輯于2023年，星期三第二部分非線性結(jié)構(gòu)三、圖（一）圖的定義與圖相關(guān)的概念有：有向圖/無向圖：無向完全圖/有向完全圖：度、出度和入度：路徑：從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的頂點(diǎn)序列子圖：連通圖與連通分量：強(qiáng)連通圖與強(qiáng)連通分量：網(wǎng)：帶權(quán)值的圖有向樹：有向圖恰有一個(gè)頂點(diǎn)的入度為0，其余頂點(diǎn)的入度為1.第三十四頁，共五十六頁，編輯于2023年，星期三第二部分非線性結(jié)構(gòu)(二)圖的存儲(chǔ)結(jié)構(gòu)1、鄰接矩陣表示法：無向圖鄰接矩陣第三十五頁，共五十六頁，編輯于2023年，星期三第二部分非線性結(jié)構(gòu)第三十六頁，共五十六頁，編輯于2023年，星期三第二部分非線性結(jié)構(gòu)2、鄰接表表示法第三十七頁，共五十六頁，編輯于2023年，星期三第二部分非線性結(jié)構(gòu)有向圖逆鄰接表

在有向圖的鄰接表中，對(duì)每個(gè)頂點(diǎn)，鏈接的是指向該頂點(diǎn)的弧。第三十八頁，共五十六頁，編輯于2023年，星期三第二部分非線性結(jié)構(gòu)（三）圖的遍歷1、深度優(yōu)先（DFS）遍歷算法：從圖中某個(gè)頂點(diǎn)V0出發(fā)，訪問此頂點(diǎn)，然后依次從V0的各個(gè)未被訪問的鄰接點(diǎn)出發(fā)深度優(yōu)先搜索遍歷圖，直至圖中所有和V0有路徑相通的頂點(diǎn)都被訪問到。例子：第三十九頁，共五十六頁，編輯于2023年，星期三第二部分非線性結(jié)構(gòu)2、廣度優(yōu)先遍歷（BFS）遍歷算法：從圖中的某個(gè)頂點(diǎn)V0出發(fā)，并在訪問此頂點(diǎn)之后依次訪問V0的所有未被訪問過的鄰接點(diǎn)，之后按這些頂點(diǎn)被訪問的先后次序依次訪問它們的鄰接點(diǎn)，直至圖中所有和V0有路徑相通的頂點(diǎn)都被訪問到。若此時(shí)圖中尚有頂點(diǎn)未被訪問,則另選圖中一個(gè)未曾被訪問的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問到為止。第四十頁，共五十六頁，編輯于2023年，星期三第二部分非線性結(jié)構(gòu)(四)生成樹及最小生成樹1、生成樹的概念

一個(gè)連通圖的生成樹是一個(gè)極小連通子圖，它包含圖中的全部頂點(diǎn)，但只有構(gòu)成一棵樹的n-1條邊。按深度和廣度優(yōu)先搜索可以分別得到不同的生成樹，分別稱為深度優(yōu)先生成樹和廣度優(yōu)先生成樹。上面圖的深度優(yōu)先生成樹和廣度優(yōu)先生成樹分別如下：第四十一頁，共五十六頁，編輯于2023年，星期三第二部分非線性結(jié)構(gòu)深度優(yōu)先生成樹廣度優(yōu)先生成樹第四十二頁，共五十六頁，編輯于2023年，星期三第二部分非線性結(jié)構(gòu)2、最小生成樹由于生成樹不唯一，從不同頂點(diǎn)出發(fā)可得到不同的生成樹，因此如何求解最小生成樹有許多實(shí)際應(yīng)用價(jià)值。常見的最小生成樹算法有兩種：、（1）普里姆算法（Prim）①基本思想：取圖中任意一個(gè)頂點(diǎn)v作為生成樹的根，之后往生成樹上添加新的頂點(diǎn)w。在添加的頂點(diǎn)w和已經(jīng)在生成樹上的頂點(diǎn)v之間必定存在一條邊，并且該邊的權(quán)值在所有連通頂點(diǎn)v和w之間的邊中取值最小。之后繼續(xù)往生成樹上添加頂點(diǎn)，直至生成樹上含有n-1個(gè)頂點(diǎn)為止。第四十三頁，共五十六頁，編輯于2023年，星期三第二部分非線性結(jié)構(gòu)②舉例第四十四頁，共五十六頁，編輯于2023年，星期三第二部分非線性結(jié)構(gòu)（2）克魯斯卡爾算法(kruskal)①基本思想：

考慮問題的出發(fā)點(diǎn):為使生成樹上邊的權(quán)值之和達(dá)到最小，則應(yīng)使