數據結構與算法 課件 魏振鋼 第6-10章 樹和二叉樹 -算法思想

第6章樹和二叉樹1問題導入：層次化數據的高效解決方案

現實中的層次數據實例文件系統目錄、企業組織架構、網頁DOM樹等，均體現數據元素間逐層遞進的層次關系。

線性結構的局限性線性表、數組難以高效存儲多對多層次數據，導致存儲效率低、操作復雜。

樹結構的核心優勢自然刻畫“一個對象擁有多個子對象”關系，靈活表達層次化組織，操作（查找/插入等）效率高。

二叉樹的典型應用憑借結構簡潔性，廣泛應用于編譯原理、數據壓縮、人工智能、數據庫索引等領域。目錄01.樹的定義和基本術語02.二叉樹的定義、性質與存儲03.遍歷二叉樹04.線索二叉樹05.樹和森林06.應用案例6.1樹的定義和基本術語樹的定義定義樹是n(n≥0)個結點的有限集。在一棵非空樹中：1.有且僅有一個特定的稱為根（root）的結點。2.當n>1時，其余結點可分為m(m>0)個互不相交的有限集T1，T2，...，Tm，每個集合本身又是一棵樹，并且稱為根的子樹。圖示圖：典型的樹結構示例（節點A為根節點）

樹的抽象數據類型定義

數據對象與數據關系數據對象D是具有相同特性的數據元素集合；數據關系R為二元關系，含唯一根結點，其余結點劃分為互不相交的子樹。

查找類基本操作包括求根結點（Root(T)）、當前結點值（Value(T，cur_e)）、雙親（Parent(T，cur_e)）、左孩子（LeftChild(T，cur_e)）、樹深度（TreeDepth(T)）等。

插入與刪除操作插入操作如InsertChild(T，p，i，c)（將樹c插入為p的第i棵子樹）；刪除操作如DeleteChild(T，p，i)（刪除p的第i棵子樹）。

遍歷與初始化操作遍歷操作TraverseTree(T，Visit())按某種次序訪問所有結點；初始化操作包括InitTree(T)（置空樹）、CreateTree(T，definition)（按定義構造樹）。樹的基本術語（一）基本概念結點：包含數據元素及若干指向其子樹的分支。結點的度：結點擁有的子樹數目。例如，A的度為3。葉子（終端結點）：度為0的結點。例如，E，K，L，G，H，I，M。非終端結點（分支結點）：度不為0的結點。例如，A，B，C，D，F。樹的度：樹內所有結點度的最大值。此樹的度為3。樹的示例樹的基本術語（二）基本概念孩子/雙親：結點子樹的根稱為該結點的孩子，該結點稱為孩子的雙親。例如，D是A的孩子，A是D的雙親。兄弟：同一個雙親的孩子之間互稱兄弟。例如，H，I，J互為兄弟。祖先：結點的祖先是從根到該結點所經分支上的所有結點子孫：某結點子樹中的結點都是該結點的子孫層次：從根開始定義，根為第一層，其孩子為第二層，依此類推。深度（高度）：樹中結點的最大層次。此樹的深度為4。森林：m(m≥0)棵互不相交的樹的集合。6.2二叉樹二叉樹的定義與基本形態二叉樹的遞歸定義二叉樹或為空樹，或由一個根結點加上兩棵互不相交的左子樹和右子樹組成，左、右子樹本身也是二叉樹。二叉樹的5種基本形態包括：空二叉樹、僅有根結點、根+左子樹、根+右子樹、根+左子樹+右子樹。二叉樹與普通樹的區別二叉樹每個結點最多有2個子樹且左右子樹有序；普通樹結點子樹數無限制且子樹無序。二叉樹的五種基本形態形態說明空二叉樹只有根結點的二叉樹根結點只有左子樹根結點只有右子樹根結點既有左子樹又有右子樹圖示二叉樹的性質核心性質

二叉樹的性質核心性質

二叉樹的性質核心性質

特殊二叉樹：滿二叉樹與完全二叉樹滿二叉樹的定義與特點

完全二叉樹的定義與特點與滿二叉樹前n個結點編號一一對應，葉子結點僅在最后兩層，左子樹深度≥右子樹深度。滿二叉樹與完全二叉樹的異同相同點：每層結點從左至右排列；不同點：滿二叉樹所有層結點數均滿，完全二叉樹最后一層可不滿但需從左到右連續。二叉樹的性質核心性質

二叉樹的性質核心性質

二叉樹的順序存儲二叉樹的順序存儲示例存儲原理順序存儲結構使用一組連續的存儲單元來存放二叉樹中的結點。通常是按照從上到下、從左到右的順序對二叉樹的結點進行編號，然后將結點存入數組中對應下標的位置。

適用場景特別適合完全二叉樹。對于完全二叉樹，順序存儲可以充分利用存儲空間，且通過簡單的公式就能計算出父子節點的位置。二叉樹的鏈式存儲（二叉鏈表）存儲原理鏈式存儲結構用指針來表示結點之間的邏輯關系。最常用的是二叉鏈表，每個結點包含三個域：數據域(data)、左指針域(lchild)、右指針域(rchild)。//----二叉樹的二叉鏈表表示----typedefstructBiTNode{//結點結構TElemTypedata;structBiTNode*lchild,*rchild;//左、右孩子指針}BiTNode,*BiTree;圖示與說明二叉鏈表結構靈活，可表示任意二叉樹，存儲空間利用率高。二叉樹的鏈式存儲（三叉鏈表）存儲原理若需快速查找結點雙親,可增加一個指向其雙親結點的指針域,形成三叉鏈表。///----二叉樹的三叉鏈表表示----typedefstructTriTNode{//結點結構TElemTypedata;structTriTNode*lchild,*rchild;//左、右孩子指針structTriTNode*parent;//雙親指針}TriTNode,*TriTree;圖示與說明

二叉樹的存儲結構對比順序存儲結構使用一維數組按層次存儲完全二叉樹，編號為i的結點存于下標i處，適用于滿二叉樹和完全二叉樹，空間利用率高。

鏈式存儲結構：二叉鏈表每個結點含數據域、左孩子指針和右孩子指針，n個結點有n+1個空鏈域，適用于非完全二叉樹，操作靈活。

鏈式存儲結構：三叉鏈表在二叉鏈表基礎上增加雙親指針域，可快速查找雙親結點，空間開銷略增，適用于需頻繁訪問雙親的場景。

存儲結構對比與適用場景順序存儲適合完全二叉樹的緊湊存儲；鏈式存儲適合任意二叉樹，尤其是頻繁插入刪除的場景。6.3遍歷二叉樹遍歷的定義與意義遍歷的概念與搜索路徑

遍歷二叉樹是按某條搜索路徑巡訪每個結點，使每個結點被訪問且僅被訪問一次。訪問含義廣泛，如輸出信息等，是獲取樹中信息的關鍵操作。按層次遍歷路徑

從上到下、從左到右按層次依次訪問結點，是一種直觀易懂的搜索路徑。先左后右遍歷路徑

先遍歷左子樹，再遍歷右子樹，基于此有先序、中序、后序三種有效遍歷組合。先右后左遍歷路徑

假如用L、D、R分別表示遍歷左子樹、訪問根結點和遍歷右子

樹。先遍歷右子樹，再遍歷左子樹，有DRL、RDL、RLD等組合，應用場景相對較少。遞歸遍歷算法：先序、中序、后序操作定義：若二叉樹為空則空操作，否則先訪問根結點，再遞歸先序遍歷左子樹，最后遞歸先序遍歷右子樹。算法實現通過遞歸調用完成。先序遍歷遞歸定義與實現01操作定義：若二叉樹為空則空操作，否則先遞歸中序遍歷左子樹，再訪問根結點，最后遞歸中序遍歷右子樹。實現方式與先序類似，僅訪問根結點時機不同。中序遍歷遞歸定義與實現02操作定義：若二叉樹為空則空操作，否則先遞歸后序遍歷左子樹，再遞歸后序遍歷右子樹，最后訪問根結點。其遞歸實現體現了左右子樹遍歷完成后訪問根的特點。后序遍歷遞歸定義與實現03二叉樹的遍歷——先序遍歷操作定義訪問根結點。先序遍歷左子樹。先序遍歷右子樹。示例與結果ABCDEFGHK二叉樹的遍歷——先序遍歷算法二叉樹的遍歷——中序中序遍歷(LDR)1.中序遍歷左子樹。2.訪問根結點。3.中序遍歷右子樹。BDCAHGKFE二叉樹的遍歷——后序中序遍歷(LRD)1.后序遍歷左子樹。2.后序遍歷右子樹。3.訪問根結點。DCBHKGFEA二叉樹的遍歷——層次遍歷操作定義與思路層次遍歷是指從上到下、從左到右依次訪問二叉樹的每一層節點。實現思路：通常借助隊列（Queue）來實現。示例與結果遍歷結果：A→B→C→D→E二叉樹的遍歷——非遞歸遍歷算法算法思路利用棧模擬遞歸過程，從根結點開始，向左走到盡頭并將結點入棧，棧頂元素出棧訪問后，移動到其右孩子，重復操作直至棧空且指針為空。線性結構與樹結構核心對比

結構關系線性結構：元素僅含單一前驅/后繼（一對一）；樹結構：結點可含多個子結點（一對多），呈現“根-子-孫”層級。

存儲與復雜度線性結構：存儲為順序/鏈式，簡單易實現；樹結構：非線性嵌套，支持遞歸定義，操作復雜度更高但表達更靈活。

訪問與遍歷線性結構：通過索引/指針順序訪問（如棧LIFO、隊列FIFO）；樹結構：遍歷方式多樣（前序/中序/后序/層次），適配復雜邏輯關系。

典型應用線性結構：表達式計算、任務調度（強順序性場景）；樹結構：目錄索引、XML文檔、AI決策樹（層次化數據場景）。

遍歷算法的應用01統計葉子結點個數先序遍歷二叉樹，遍歷過程中判斷結點是否為葉子（左右孩子均為空），若是則計數器增1。算法6-4通過遞歸實現該功能。

02求二叉樹深度基于后序遍歷，先分別求左、右子樹深度，二叉樹深度為左右子樹深度最大值加1。算法6-5體現了這一遞歸求解過程。

03復制二叉樹后序遍歷待復制二叉樹，先復制左、右子樹，再創建當前結點副本并連接子樹。算法6-6通過遞歸完成二叉樹的復制操作。

04遍歷是二叉樹操作的基礎遍歷可用于求結點雙親、孩子，判定層次等操作，也可在遍歷中生成結點建立存儲結構，是實現二叉樹各種操作的核心基礎。6.4線索二叉樹線索二叉樹的概念與作用問題背景：傳統二叉鏈表的局限二叉鏈表存儲結構中，僅能直接獲取結點的左、右孩子信息，無法直接得知其前驅和后繼。n個結點的二叉鏈表存在n+1個空鏈域，造成空間浪費。核心思路：利用空鏈域存儲線索通過修改空指針域，存儲結點在遍歷序列中的前驅和后繼信息，將非線性結構線性化，實現高效訪問。基本定義：線索與線索二叉樹線索：指向結點前驅或后繼的指針；線索鏈表：增加標志域（LTag/RTag）的二叉鏈表；線索二叉樹：加上線索的二叉樹，可實現快速遍歷。

線索二叉樹的存儲結構結點結構：標志域與指針域結點包含lchild（左指針）、LTag（左標志）、data（數據）、RTag（右標志）、rchild（右指針）。LTag/RTag為0表示指針指向孩子，為1表示指向線索。

標志域的含義LTag=0：lchild指向左孩子；LTag=1：lchild指向前驅。RTag=0：rchild指向右孩子；RTag=1：rchild指向后繼。二叉樹線索化對二叉樹進行某種次序遍歷并轉換為線索二叉樹的過程稱為線索化中序線索二叉樹

對應的中序序列為B

D

C

AHGKF

E建立線索鏈表線索化本質二叉鏈表空指針改造為前驅/后繼線索，通過遍歷過程動態修改空指針實現。

中序線索化關鍵指針遍歷時維護pre（剛訪問結點）與p（當前結點），pre始終指向p的前驅結點。

線索化核心目標利用空指針存儲遍歷順序關系，解決傳統二叉鏈表僅存父子關系、無法直接獲取前驅后繼的問題。

voidInThreading(BiThrTreep){if(p){//對以p為根的非空二叉樹進行線索化InThreading(p->lchild);//左子樹線索化if(!p->lchild)//建立前驅線索{p->LTag=Thread;p->lchild=pre;}if(!pre->rchild)//建立后繼線索{pre->RTag=Thread;pre->rchild=p;}pre=p;//保持pre指向p的前驅InThreading(p->rchild);//右子樹線索化}}//InThreading建立線索鏈表StatusInOrderThreading(BiThrTree&Thrt,BiThrTreeT){//中序遍歷二叉樹T,并將其中序線索化,Thrt指向頭結點Thrt=newBiThrNode();//創建頭結點if(!Thrt)returnerror;//內存分配失敗返回錯誤Thrt->LTag=Link;Thrt->RTag=Thread;//建立頭結點Thrt->rchild=Thrt;//右指針回指if(!T){Thrt->lchild=Thrt;//若二叉樹空,則左指針回指}else{Thrt->lchild=T;pre=Thrt;InThreading(T);//中序遍歷進行線索化pre->rchild=Thrt;//最后一個結點線索化pre->RTag=Thread;Thrt->rchild=pre;}returnOK;}線索二叉樹遍歷

遍歷高效性：無需棧輔助線索二叉樹遍歷時間復雜度為O(n)，通過線索直接訪問前驅/后繼，避免遞歸或棧空間開銷，適用于頻繁遍歷場景。

雙向線索鏈表的優勢添加頭結點，左指針指向根，右指針指向中序最后一個結點；首結點左線索和尾結點右線索均指向頭結點，支持雙向遍歷（從首結點順后繼或從尾結點順前驅）。StatusInOrderTraverse_Thr(BiThrTreeT,Status(*Visit)(TElemTypee)){//T指向頭結點,頭結點的左鏈lchild指向根結點,可參見線索化算法//中序遍歷二叉線索樹T的非遞歸算法,對每個數據元素調用函數Visit()p=T->lchild;//p指向根結點while(p!=T){//空樹或遍歷結束時,p==Twhile(p->LTag==Link)p=p->lchild;//找到第一個結點if(!Visit(p->data))returnerror;//訪問其左子樹為空的結點while(p->RTag==Thread&&p->rchild!=T){p=p->rchild;Visit(p->data);//訪問后繼結點}p=p->rchild;//p進至其右子樹根}returnok;}6.5樹和森林樹的存儲結構（一）：雙親表示法定義與思想雙親表示法是一種順序存儲結構，用一組連續的存儲空間來存儲樹的結點。每個結點包含兩個域：數據域和雙親域。數據域存儲結點的數據信息，雙親域存儲該結點的雙親在數組中的位置。結構定義與圖示#defineMAX_TREE_SIZE100typedefstructPTNode{TElemTypedata;//數據域intparent;//雙親位置域}PTNode;typedefstruct{PTNodenodes[MAX_TREE_SIZE];intr,n;}PTree;數組中每個元素代表一個節點，parent值為-1表示根節點。樹的存儲結構（二）：孩子表示法定義與思想孩子表示法是將每個結點的孩子結點排列起來，以單鏈表作為存儲結構，稱為孩子鏈表。n個結點共有n個孩子鏈表（葉子結點的單鏈表為空），然后將n個結點的數據和n個孩子鏈表的頭指針組成一個順序表。結構定義與圖示//-----樹的孩子鏈表存儲表示-----typedefstructCTNode{//孩子結點intchild;structCTNode*next;}*ChildPtr;typedefstruct{Elemdata;ChildPtrfirstchild;//孩子鏈表頭指針}CTBox;typedefstruct{CTBoxnodes[MAX_TREE_SIZE];intn,r;//結點數和根結點的位置}CTree;每個節點作為一個表頭，其后鏈接的是它所有的孩子節點。樹的存儲結構（三）：孩子兄弟表示法定義與思想孩子兄弟表示法又稱二叉樹表示法，或二叉鏈表表示法。即以二叉鏈表作為樹的存儲結構。鏈表中每個結點設有兩個鏈域，分別指向該結點的第一個孩子結點和下一個兄弟結點。結構定義與圖示typedefstructCSNode{TElemTypedata;structCSNode*firstchild,*nextsibling;}CSNode,*CSTree;每個節點有兩個指針，一個指向它的第一個孩子，另一個指向它的下一個兄弟。

樹的存儲結構雙親表示法以連續空間存儲樹的結點，每個結點包含數據域和指示雙親位置的指示器。優點是便于查找雙親結點，缺點是求孩子結點需遍歷整個結構。

孩子表示法將每個結點的孩子結點排列成單鏈表，頭指針組成順序存儲的線性表。優點是便于涉及孩子的操作，可與雙親表示法結合使用。

孩子兄弟表示法每個結點包含數據域、指向第一個孩子的指針和指向下一個兄弟的指針。能有效反映樹的層次結構和結點關系，便于實現樹的各種操作。樹轉換為二叉樹：核心思想與步驟核心思想將樹的孩子關系轉換為二叉樹的左孩子關系，將樹的兄弟關系轉換為二叉樹的右孩子關系。這是樹轉二叉樹的本質。轉換三步驟加線：在所有兄弟結點之間加一條連線。抹線：對樹中每個結點，只保留它與第一個孩子結點的連線。旋轉：順時針旋轉整棵樹，調整結構。森林與二叉樹的轉換

轉換對應關系森林與二叉樹存在一一對應關系，樹的二叉鏈表表示與二叉樹的存儲結構相同，只是解釋不同，森林的第一棵樹子樹森林對應二叉樹左子樹，剩余樹對應右子樹。森林轉換為二叉樹轉換步驟1.將森林中的每一棵樹分別轉換為二叉樹。2.將第一棵二叉樹作為結果二叉樹的根。3.將第二棵二叉樹的根節點作為第一棵二叉樹根節點的右孩子。4.依次類推，將后續二叉樹連接為前一棵樹的右子樹。核心思想森林中的樹與樹之間是兄弟關系，因此在轉換為二叉樹時，它們依次作為前一棵樹的右子樹，從而將整個森林串聯成一棵完整的二叉樹。二叉樹轉換為森林轉換步驟1.若二叉樹B為空，則轉換的森林F為空。2.若二叉樹B非空，F首棵樹根為二叉樹B的根；首棵樹的子樹森林由B的左子樹轉換而成的森林，剩余森林由B右子樹轉換

樹和森林的遍歷樹的遍歷先根遍歷：先訪問根結點，再依次先根遍歷各子樹；后根遍歷：先依次后根遍歷各子樹，再訪問根結點；按層次遍歷：自上而下、自左至右訪問每個結點。

森林的遍歷先序遍歷：訪問第一棵樹的根，先序遍歷其根的子樹森林，再先序遍歷剩余樹的森林；中序遍歷：中序遍歷第一棵樹根的子樹森林，訪問根，再中序遍歷剩余樹的森林。

與二叉樹遍歷的關系樹的先根、后根遍歷分別對應二叉樹的先序、中序遍歷；森林的先序、中序遍歷即為其對應二叉樹的先序、中序遍歷。

樹的計數基本概念相似二叉樹指結構相同但結點數據不同；等價二叉樹要求結構和數據都相同。樹的計數問題是求具有n個結點的不同形態樹的數目。

二叉樹的計數

樹的計數推導

6.6應用案例

哈夫曼樹及其應用01哈夫曼樹的定義與關鍵概念哈夫曼樹（最優二叉樹）是帶權路徑長度最短的二叉樹，權值越大的結點離根越近。路徑是結點間的路線，路徑長度為邊的數量，帶權路徑長度（WPL）是所有葉子結點權值與路徑長度乘積之和。

02哈夫曼算法步驟1.初始化：將n個權值構造成n棵單根結點二叉樹；2.選擇與合并：選取權值最小的兩棵樹作為左右子樹，構造新樹，根權值為兩子樹權值之和；3.更新集合：將新樹加入集合，刪除原兩棵樹；4.重復操作至集合只剩一棵樹。

03哈夫曼樹構造實例以權值{7，5，2，4}為例，構造過程：先合并2和4得6，再合并5和6得11，最后合并7和11得18，最終WPL=7×1+5×2+4×3+2×3=35，為最優結構。

04哈夫曼編碼在數據壓縮中的應用以字符出現頻率為權值構建哈夫曼樹，左分支賦0、右分支賦1，從根到葉子路徑形成前綴編碼。高頻字符編碼短，低頻字符編碼長，實現數據壓縮，且解碼唯一無歧義。

哈夫曼樹及其應用01哈夫曼樹的定義與關鍵概念哈夫曼樹（最優二叉樹）是帶權路徑長度最短的二叉樹，權值越大的結點離根越近。路徑是結點間的路線，路徑長度為邊的數量，帶權路徑長度（WPL）是所有葉子結點權值與路徑長度乘積之和。

02哈夫曼算法步驟1.初始化：將n個權值構造成n棵單根結點二叉樹；2.選擇與合并：選取權值最小的兩棵樹作為左右子樹，構造新樹，根權值為兩子樹權值之和；3.更新集合：將新樹加入集合，刪除原兩棵樹；4.重復操作至集合只剩一棵樹。

03哈夫曼樹構造實例以權值{7，5，2，4}為例，構造過程：先合并2和4得6，再合并5和6得11，最后合并7和11得18，最終WPL=7×1+5×2+4×3+2×3=35，為最優結構。

04哈夫曼編碼在數據壓縮中的應用以字符出現頻率為權值構建哈夫曼樹，左分支賦0、右分支賦1，從根到葉子路徑形成前綴編碼。高頻字符編碼短，低頻字符編碼長，實現數據壓縮，且解碼唯一無歧義。01哈夫曼編碼的實現哈夫曼樹的存儲結構采用動態數組存儲哈夫曼樹結點，每個結點含權值、雙親及左右孩子指針typedefstruct{unsignedintweight;unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;//動態分配數組存儲哈夫曼樹typedefchar**HuffmanCode;//動態分配數組存儲哈夫曼編碼表02從葉子到根逆向求編碼算法從葉子結點出發，通過雙親指針逆向追溯至根，左孩子記0、右孩子記1，將編碼存入工作空間，最后復制到編碼表。需動態分配編碼空間，時間復雜度O(n2)。03從根遍歷求編碼算法（無棧非遞歸）利用結點狀態標志（0：未訪問，1：左子樹訪問，2：右子樹訪問），遍歷哈夫曼樹，左分支加0、右分支加1，遇到葉子結點時登記編碼。無需棧輔助，空間效率更高。04編碼與解碼過程分析編碼：根據字符權值構建哈夫曼樹，生成前綴編碼；解碼：從根開始，按編碼序列（0左1右）遍歷樹，直至葉子結點得到字符，實現無歧義解碼。哈夫曼樹無度為1的結點，含n個葉子時共有2n-1個結點。人工智能中的決策樹決策樹的概念與構建過程決策樹是樹結構，分支結點表示特征測試，葉子結點代表類別或決策結果。構建從根開始，選擇最優特征劃分數據，遞歸劃分至滿足停止條件（如最大深度、樣本同類別）。在分類任務中的應用用于醫學診斷（癥狀→疾病）、垃圾郵件過濾（關鍵詞→是否垃圾郵件）等。通過學習特征與類別關系，對新樣本沿決策路徑分類，如根據“年齡”“收入”預測用戶購買行為。在回歸任務中的應用預測連續值，如房地產房價（面積、戶型等特征→房價）。通過劃分數據空間，使葉子結點樣本值接近平均值，新樣本按特征路徑找到對應葉子結點得預測值。決策樹的優點與缺陷優點：可解釋性強（結構直觀）、處理非線性關系能力好、對數據要求低（無需假設分布）。缺陷：易過擬合（需剪枝）、對數據敏感（微小變化影響結構）、大規模數據計算復雜度高。6.7本章小結

知識體系梳理基本概念與術語樹是n(n≥0)個結點的有限集，有且僅有一個根結點，其余結點可分為互不相交的子樹。核心術語包括度（結點子樹數量）、葉子（度為0的結點）、層次（根為第一層）、深度（最大層次）等。二叉樹是特殊樹結構，每個結點最多有左、右兩棵子樹，具有5種基本形態。

二叉樹性質與存儲結構二叉樹性質：第i層至多2^(i-1)個結點；深度為k的二叉樹至多2^k-1個結點；葉子結點數=度為2的結點數+1。存儲結構分為順序存儲（適合滿二叉樹和完全二叉樹）和鏈式存儲（二叉鏈表含數據域及左、右指針，三叉鏈表增加雙親指針）。

遍歷算法與線索二叉樹遍歷算法包括先序（根→左→右）、中序（左→根→右）、后序（左→右→根）及層次遍歷，時間復雜度均為O(n)。線索二叉樹通過利用空鏈域存儲前驅/后繼線索，實現高效遍歷，無需棧輔助，時間復雜度O(n)。知識體系梳理

樹與森林的轉換及應用樹與二叉樹可通過孩子-兄弟表示法轉換，森林轉換為二叉樹時，第一棵樹的子樹森林轉為左子樹，其余樹轉為右子樹。應用案例包括哈夫曼樹（最優二叉樹，用于數據壓縮編碼）和決策樹（機器學習中用于分類與回歸）。學習意義與后續展望樹結構的核心地位樹和二叉樹是處理層次化數據的基礎結構，在文件系統、組織架構、DOM文檔等場景中廣泛應用。其非線性特性彌補了線性結構在表達多對多關系時的不足，為高效查找、插入、刪除操作提供支撐。對后續學習的影響掌握樹結構是學習高級數據結構（如B樹、紅黑樹、堆）和算法（如動態規劃、圖論）的前提。二叉樹的遞歸思想、遍歷策略可遷移至復雜問題求解，如表達式解析、路徑規劃等。未來應用領域拓展在人工智能領域，決策樹模型可用于醫療診斷、風險評估；在大數據處理中，哈夫曼編碼優化存儲與傳輸；在區塊鏈技術中，默克爾樹保障數據完整性。隨著技術發展，樹結構將在更多交叉領域發揮作用。感謝觀看Q&A歡迎提問與交流第七章圖數據結構與算法中國海洋大學本章目錄01.圖的定義和術語02.圖的存儲03.圖的遍歷04.圖的應用（最短路徑、最小生成樹等）05.本章小結問題導入：復雜交通網絡中的最優路徑規劃任務背景：復雜的交通網絡作為旅行規劃師，需規劃從城市A到城市Z的路線。網絡包含20個城市節點和上百條連接道路。每個道路（邊）都帶有不同的權重屬性，如收費、時間、擁堵指數等，構成了一個典型的帶權圖結構。核心挑戰：多約束條件優化旅行團需求苛刻，需要同時滿足“最短時間”、“預算內費用”以及“避免頻繁換乘”等多重目標。在如此復雜的網絡中，如何快速找到一條平衡各方利益的最優路徑，是本次任務的核心難點。問題本質：圖結構的最短路徑問題面對這樣的交通“圖”，我們需要利用圖論算法來解決。將城市抽象為頂點(Vertex)，將道路抽象為邊(Edge)，將費用和時間抽象為權重(Weight)。尋找最優路徑的過程，本質上就是在一個帶權圖中尋找最短路徑的過程，這正是我們本章要探討的核心算法。7.1圖的定義和術語圖的定義(Graph)圖是用于表示多對多關系的非線性數據結構，形式化表示為G=(V,E)。其中V是頂點的集合，E是邊的集合。頂點(Vertex/Node)圖的基本構成單元，表示實體或對象。例如在交通網絡中代表城市，在社交網絡中代表用戶。邊(Edge)表示頂點之間的關系，記為(v,w)或<v,w>。例如道路連接城市，好友關系連接用戶。鄰接點與關聯邊鄰接點：若頂點v和w之間存在邊，則稱v和w互為鄰接點。關聯邊：邊e與頂點v和w相關聯。無向圖vs有向圖無向圖(UndirectedGraph)定義：邊沒有方向，表示雙向關系。示例：社交網絡中的好友關系（A是B的好友，B也是A的好友）。表示：邊記為(v,w)。有向圖(DirectedGraph)定義：邊有方向，表示單向關系。示例：網頁間的超鏈接（從A指向B，B不一定指向A）。表示：邊記為<v,w>。有權圖vs無權圖無權圖(UnweightedGraph)邊僅表示關系的存在，沒有附加信息。可以認為邊的權重為1，僅關注節點間的連通性。有權圖(WeightedGraph/Network)邊帶有附加的數值信息（權重/Weight），表示關系的強度、成本或距離。例如：交通網絡中道路的長度或通行時間。稠密圖vs稀疏圖稀疏圖(SparseGraph)邊數遠小于最大可能邊數的圖。頂點之間連接較為松散。無向完全圖(Undirected)一種特殊的稠密圖。任意兩個頂點之間都存在邊，連接最緊密。有向完全圖(Directed)任意兩個頂點之間都存在兩條方向相反的邊，邊數達到最大值。無向圖的基本術語度(Degree)頂點v的度是與v相關聯的邊的數目，記為D(v)。它反映了頂點的連接緊密程度。路徑(Path)從頂點v到頂點w的頂點序列，相鄰頂點間有邊相連。路徑長度是邊的數目。無向圖的基本術語連通圖(ConnectedGraph)圖中任意兩個頂點之間都存在路徑，意味著整個圖是一個整體，沒有孤立的部分。生成樹(SpanningTree)連通圖的極小連通子圖，包含所有頂點和n-1條邊（n為頂點數），無環結構。有向圖的基本術語頂點的度(Degree)入度(In-degree)以頂點v為終點的邊的數目，記為ID(v)。出度(Out-degree)以頂點v為起點的邊的數目，記為OD(v)。總度(TotalDegree)D(v)=ID(v)+OD(v)。強連通圖(StronglyConnected)定義有向圖中任意兩個頂點v和w之間，既存在從v到w的路徑，也存在從w到v的路徑。圖的基本術語7.1.2圖的基本操作結構的建立和銷毀CreateGraph:創建圖結構DestroyGraph:銷毀圖結構對頂點的訪問操作LocateVex/GetVex:查找頂點PutVex:修改頂點信息對鄰接點的操作FirstAdjVex:求第一個鄰接點NextAdjVex:求下一個鄰接點插入或刪除頂點InsertVex:插入頂點DeleteVex:刪除頂點插入和刪除邊InsertArc:插入邊(弧)DeleteArc:刪除邊(弧)圖的遍歷操作DFSTraverse:深度優先遍歷BFSTraverse:廣度優先遍歷7.2圖的存儲-鄰接矩陣核心概念定義基本思想：使用二維數組（矩陣）來表示圖中頂點間的鄰接關系。矩陣結構：矩陣的行和列都對應頂點。元素含義：arcs[i][j]的值表示頂點i和頂點j之間是否有邊以及邊的權重。C語言結構定義實現//最大頂點數與邊結構體定義#defineMAX_VERTEX_NUM20typedefstructArcCell{intadj;//邊權值或相鄰標志InfoType*info;}AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//圖的鄰接矩陣存儲結構typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];AdjMatrixarcs;//鄰接矩陣intvexnum,arcnum;}MGraph;7.2圖的存儲-鄰接矩陣核心概念定義基本思想：使用二維數組（矩陣）來表示圖中頂點間的鄰接關系。矩陣結構：矩陣的行和列都對應頂點。元素含義：arcs[i][j]的值表示頂點i和頂點j之間是否有邊以及邊的權重。C語言結構定義實現//最大頂點數與邊結構體定義#defineMAX_VERTEX_NUM20typedefstructArcCell{intadj;//邊權值或相鄰標志InfoType*info;}AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//圖的鄰接矩陣存儲結構typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];AdjMatrixarcs;//鄰接矩陣intvexnum,arcnum;}MGraph;鄰接矩陣示例無向無權圖(a)特點：矩陣對稱，arcs[i][j]=1表示有邊，0表示無邊。有向無權圖(b)特點：矩陣不一定對稱，arcs[i][j]=1表示有從i到j的邊。無向有權圖(c)特點：矩陣對稱，arcs[i][j]存儲權重，無邊則為∞。有向有權圖(d)特點：矩陣不一定對稱，arcs[i][j]存儲權重，無邊則為∞。算法7-3：構造圖的鄰接矩陣表示(1)核心代碼：CreateGraph函數StatusCreateGraph(MGraph&G){//采用數組（鄰接矩陣）表示法，構造圖Gscanf(&G.kind);switch(G.kind){caseDG:returnCreateDG(G);//構造有向圖GcaseDN:returnCreateDN(G);//構造有向網GcaseUDG:returnCreateUDG(G);//構造無向圖GcaseUDN:returnCreateUDN(G);//構造無向網Gdefault:returnERROR;}}核心邏輯：根據圖的類型（DG/DN/UDG/UDN），通過switch-case語句動態調用對應的創建函數。算法7-3：構造圖的鄰接矩陣表示(2)CreateUDN函數實現(C語言)StatusCreateUDN(MGraph&G){//采用數組（鄰接矩陣）表示法，構造無向網scanf("%d%d%d",&G.vexnum,&G.arcnum,&IncInfo);//構造頂點向量for(inti=0;i<G.vexnum;++i){scanf("%s",&G.vexs[i]);}//初始化鄰接矩陣為無窮大for(inti=0;i<G.vexnum;++i)for(intj=0;j<G.vexnum;++j)G.arcs[i][j].adj=INFINITY;for(intk=0;k<G.arcnum;++k){//輸入邊信息并填充矩陣VertexTypev1,v2;intw;scanf("%s%s%d",&v1,&v2,&w);inti=LocateVex(G,v1),j=LocateVex(G,v2);G.arcs[i][j].adj=w;G.arcs[j][i]=G.arcs[i][j];//關鍵：無向圖的對稱性}returnOK;}鄰接矩陣的優缺點分析核心優勢(Advantages)查找快速判斷兩點是否有邊或獲取權重，時間復雜度為O(1)。實現簡單基于二維數組結構，邏輯直觀，易于編程實現和理解。適合稠密圖對于邊數接近頂點數平方的稠密圖，空間利用率較高。主要局限(Disadvantages)空間復雜度高空間復雜度為O(n2)，對于稀疏圖會浪費大量存儲空間。插入刪除困難插入或刪除頂點需要重構整個矩陣，操作成本較高。7.2.2圖的存儲-鄰接表鄰接表定義為每個頂點建立一個單鏈表，鏈表節點表示鄰接頂點及邊信息。整個圖由頂點數組和若干鄰接鏈表組成，適用于稀疏圖存儲。結構示意圖C語言實現代碼typedefstructArcNode{//邊節點結構定義intadjvex;//鄰接點索引structArcNode*nextarc;//指向下一條邊}ArcNode;typedefstructVNode{//頂點結構定義VertexTypedata;//頂點信息ArcNode*firstarc;//指向第一個邊節點}VNode;typedefstruct{//圖結構定義VNodeadjlist[MAX_V];//頂點數組intvexnum,arcnum;//頂點數和邊數}ALGraph;鄰接表示例構建原理與特點基本結構：以一個簡單的無向圖為例，圖中的每個頂點作為鏈表的頭節點，其后鏈接的是所有與其直接相連的頂點。存儲優勢：相比鄰接矩陣，鄰接表更節省空間，尤其適合存儲邊數較少的稀疏圖（SparseGraph）。查詢效率：查找特定頂點的所有鄰居非常高效，但判斷兩個頂點是否相連則需要遍歷鏈表。算法：構造圖的鄰接表表示核心構建步驟1.初始化頂點數組讀取頂點數和邊數，初始化每個頂點的鄰接表頭指針為NULL。2.創建并插入邊節點逐條讀取邊信息，定位頂點位置，動態分配邊節點并插入到鏈表頭部。3.無向圖雙向插入對于無向圖，同一條邊需在兩個頂點的鄰接表中各插入一次，確保圖的對稱性。C語言實現代碼(CreateUDG)for(inti=0;i<G.vexnum;++i){//初始化頂點數組scanf("%s",&G.adjlist[i].data);G.adjlist[i].firstarc=NULL;}for(intk=0;k<G.arcnum;++k){//逐條輸入邊信息并插入inti=LocateVex(G,v1),j=LocateVex(G,v2);//插入到v1的鄰接表ArcNode*p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=j;p->nextarc=G.adjlist[i].firstarc;G.adjlist[i].firstarc=p;//無向圖：插入到v2的鄰接表p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=i;p->nextarc=G.adjlist[j].firstarc;G.adjlist[j].firstarc=p;}鄰接表的優缺點分析核心優勢空間效率高空間復雜度為O(n+e)，避免了鄰接矩陣的空間浪費，非常適合稀疏圖。便于增刪頂點插入或刪除頂點操作相對容易，僅需調整頂點數組和相關鏈表指針。便于遍歷鄰接點遍歷一個頂點的所有鄰接點非常方便，直接遍歷其對應的鏈表即可。局限性與挑戰查找邊效率低判斷兩點間是否有邊需遍歷鏈表，時間復雜度為O(n)，不如矩陣查找迅速。實現相對復雜涉及鏈表的動態內存分配和指針操作，代碼實現比鄰接矩陣稍顯復雜。十字鏈表ABDCEF十字鏈表ABCDEF0123451305430125

212343

頂點firstinfirstout

弧尾

弧頭tlink

hlink

十字鏈表typedefintStatus;typedefintVertexType;typedefintInfoType;structArcBox{//邊的結構表示inttailvex,headvex;//該邊尾和頭頂點的位置ArcBox*hlink,*tlink;//分別指向弧頭頂點和弧尾頂點的下一條弧InfoType*info;//該邊相關信息的指針};structVexNode{//頂點的結構表示VertexTypedata;//頂點信息ArcBox*firstin,*firstout;//分別指向該頂點的第一條入邊和出邊};structOLGraph{//有向圖的結構表示VexNodexlist[MAX_VERTEX_NUM];//頂點結點(表頭向量)intvexnum,arcnum;//有向圖的當前頂點數和弧數};十字鏈表intLocateVex(OLGraph&G,VertexTypev){//定位頂點for(inti=0;i<G.vexnum;++i){if(G.xlist[i].data==v){returni;}}return-1;//如果未找到，返回-1}voidInput(InfoType&info){//輸入邊的信息cin>>info;//示例輸入，根據實際需求修改}StatusCreateDG(OLGraph&G){//創建有向圖cin>>G.vexnum>>G.arcnum;for(inti=0;i<G.vexnum;++i){ cin>>G.xlist[i].data;G.xlist[i].firstin=NULL;G.xlist[i].firstout=NULL;}十字鏈表for(intk=0;k<G.arcnum;++k){VertexTypev1,v2;cin>>v1>>v2;inti=LocateVex(G,v1);intj=LocateVex(G,v2);if(i==-1||j==-1){cerr<<"Vertexnotfound!"<<endl;returnERROR;}ArcBox*p=newArcBox;p->tailvex=i;p->headvex=j;p->hlink=G.xlist[j].firstin;//指向j頂點原第一條入邊p->tlink=G.xlist[i].firstout;//指向i頂點原第一條出邊p->info=NULL;G.xlist[j].firstin=p;//更新j頂點的入邊鏈表G.xlist[i].firstout=p;//更新i頂點的出邊鏈表//如果需要輸入邊的信息，取消以下注釋//Input(*p->info);}returnOK;}鄰接多重表

鄰接多重表是無向圖的另一種鏈式存儲結構。

邊的結點結構

mark

ivexilink

jvex

jlink

info其中：Mark為標志域；ivex和jvex為該邊依附的兩個頂點在圖中的位置；ilink指向下一條依附于頂點ivex的邊；jlink指向下一條依附于頂點jvex的邊；info為指向和邊相關的各種信息的指針域。鄰接多重表鄰接多重表typedefstructEbox{ VisitIfmark;//訪問標記 intivex,jvex;//該邊依附的兩個頂點的位置 structEBox*ilink,*jlink;//分別指向依附這兩個頂點的下一條邊 InfoType*info;//該邊信息指針}EBox;typedefstructVexBox{ VertexTypedata; EBox*firstedge;//指向第一條依附該頂點的邊}VexBox;typedefstruct{//鄰接多重表 VexBoxadjmulist[MAX_VERTEX_NUM]; intvexnum,edgenum;//無向圖的當前頂點數和邊數 }AMLGraph;7.3圖的遍歷-深度優先搜索(DFS)DFS基本思想核心策略：“先走到底，再回頭”。從起始頂點出發，盡可能深地探索路徑。遞歸過程：訪問一個鄰接頂點，然后以該頂點為新起點，遞歸進行搜索。回溯機制：當一個頂點的所有鄰接頂點都被訪問過時，回溯到上一個頂點，繼續訪問其他未訪問分支。核心實現機制數據結構：通常利用遞歸調用棧（系統棧）或顯式使用棧（Stack）數據結構來實現。算法特征：體現了“深度”優先的策略，優先縱向深入探索，而非橫向鋪開。關鍵操作：標記已訪問的頂點，避免重復訪問，確保每個頂點僅被訪問一次。DFS算法動態演示(1)第一步：訪問起始頂點選擇起點：選擇圖中的任意一個頂點作為遍歷的起始點（例如頂點A）。標記狀態：將該頂點標記為“已訪問”，避免后續重復訪問。輸出結果：將該頂點加入結果序列，完成第一步操作。DFS算法動態演示(2)第二步：遞歸訪問鄰接頂點起始與訪問：從起始頂點A出發，訪問其第一個未訪問的鄰接頂點（如頂點B），標記為已訪問并輸出。遞歸深入：以B為新的起點，遞歸地重復此過程，繼續訪問B的鄰接頂點，體現“深度優先”的核心思想。DFS算法動態演示(3)第三步：回溯過程(Backtracking)終止條件：當訪問到頂點（如頂點D）且其所有鄰接頂點都已被訪問時，無法再繼續深入。回溯操作：遞歸函數返回，回到上一個頂點（如頂點B），繼續尋找未訪問的分支。循環直至完成：重復“深入-回溯”的過程，直到圖中所有頂點都被訪問完畢。DFS算法動態演示(3)DFS算法實現代碼算法核心邏輯訪問標記數組

使用布爾數組`visited`記錄頂點狀態，避免重復訪問。深度優先遞歸

從起點出發，沿著一條路徑盡可能深地探索，直到盡頭再回溯。鄰接矩陣遍歷

通過雙重循環檢查矩陣中的鄰接關系(`G.arcs[v][w].adj==1`)。非連通圖處理

`DFSTraverse`函數確保所有連通分量都被訪問。C語言實現代碼//圖的種類：有向圖、有向網、無向圖、無向網typedefenum{DG,DN,UDG,UDN}GraphKind;structArcCell{

//邊的定義

intadj;

//頂點關系類型，無權圖用1或0表示相鄰否，有權圖為權值

InfoType*info;

//該邊相關信息的指針，如邊權};//鄰接矩陣typedefArcCellAdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

DFS算法實現代碼typedefstruct{

//圖的結構定義VertexTypevexs[MAX_VERTEX_NUM];//頂點向量AdjMatrixarcs;

//鄰接矩陣intvexnum,arcnum;

//圖的當前頂點數和邊數GraphKindkind;

//圖的種類標志}MGraph,Graph;boolvisited[MAX_VERTEX_NUM];

//訪問標志數StatusVisit(intv){//訪問函數cout<<"Visitedvertex:"<<v<<endl;returnOK;}DFS算法實現代碼intFirstAdjVex(constGraph&G,intv){//獲取第一個鄰接頂點for(inti=0;i<G.vexnum;++i){if(G.arcs[v][i].adj!=0){//如果存在邊returni;}}return-1;//沒有鄰接頂點}intNextAdjVex(constGraph&G,intv,intw){//獲取下一個鄰接頂點for(inti=w+1;i<G.vexnum;++i){if(G.arcs[v][i].adj!=0){//如果存在邊returni;}}return-1;//沒有下一個鄰接頂點}DFS算法實現代碼voidDFS(Graph&G,intv){//深度優先搜索visited[v]=TRUE;//標記為已訪問Visit(v);//訪問第v個頂點for(intw=FirstAdjVex(G,v);w!=-1;w=NextAdjVex(G,v,w)){if(!visited[w]){DFS(G,w);//對v的尚未訪問的鄰接頂點，遞歸調用DFS}}}voidDFSTraverse(Graph&G,Status(*Visit)(intv)){//深度優先搜索遍歷memset(visited,FALSE,sizeof(visited));//初始化訪問標志數組for(intv=0;v<G.vexnum;++v){if(!visited[v]){DFS(G,v);//對尚未訪問的頂點調用DFS}}}7.3圖的遍歷-廣度優先搜索(BFS)BFS基本思想：層層遞進，先廣后深從起始頂點出發，先訪問其所有鄰接頂點（第一層），然后依次訪問這些鄰接頂點的鄰接頂點（第二層），以此類推，直到所有頂點都被訪問。這種方式如同水面波紋向外擴散。核心實現機制：隊列(Queue)利用隊列（先進先出）來維護訪問順序，確保先被訪問的頂點的鄰接頂點優先被處理，完美體現了“廣度”優先的策略。BFS算法動態演示(1)第一步：初始化隊列與起始頂點選擇起始頂點選定圖中的起始節點（如頂點A）作為遍歷的起點。標記訪問狀態將起始頂點標記為“已訪問”，避免后續重復處理。入隊操作將已訪問的起始頂點加入隊列，作為后續處理的依據。BFS初始狀態示意圖BFS算法動態演示(2)第二步：出隊與鄰接訪問1.隊首出隊將隊列頭部的頂點（A）取出，作為當前訪問節點。2.訪問鄰接頂點遍歷當前節點（A）的所有未訪問鄰接點（B,C），標記為已訪問。3.新節點入隊將新發現的鄰接點（B,C）依次加入隊列尾部，等待下一層處理。隊列操作示意圖BFS算法動態演示(3)第三步：循環遍歷與隊列操作核心操作：重復第二步，依次將隊首頂點出隊，訪問其所有未訪問的鄰接頂點，標記并入隊。終止條件：直到隊列為空，所有頂點都被訪問。算法特點：最終的訪問順序體現了“層次遍歷”的特點，即由近及遠地訪問圖中的節點。BFS算法動態演示BFS算法實現代碼（鄰接矩陣）核心實現代碼(C語言)核心邏輯解析隊列管理機制使用數組模擬隊列，通過front和rear指針實現先進先出（FIFO），確保訪問順序。訪問標記數組visited[]數組記錄節點狀態，防止重復訪問，避免死循環。廣度優先遍歷循環取出隊首節點，遍歷其所有鄰接點，將未訪問的鄰接點入隊，層層向外擴展。intFirstAdjVex(constGraph&G,intv){//獲取第一個鄰接頂點for(inti=0;i<G.vexnum;++i){if(G.arcs[v][i].adj!=0){//如果存在邊returni;}}return-1;//沒有鄰接頂點}intNextAdjVex(constGraph&G,intv,intw){

//獲取下一個鄰接頂點for(inti=w+1;i<G.vexnum;++i){if(G.arcs[v][i].adj!=0){//如果存在邊returni;}}return-1;//沒有下一個鄰接頂點}BFS算法實現代碼voidBFSTraverse(Graph&G,Status(*Visit)(intv)){//廣度優先搜索遍歷memset(visited,FALSE,sizeof(visited));//初始化訪問標志queue<int>Q;

//輔助隊列for(intv=0;v<G.vexnum;++v){if(!visited[v]){

//尚未訪問Q.push(v);

//入隊列

visited[v]=TRUE;

//標記為已訪問

Visit(v);

//訪問while(!Q.empty()){intu=Q.front();

//隊頭元素

Q.pop();

//出隊for(intw=FirstAdjVex(G,u);w!=-1;w=NextAdjVex(G,u,w)){if(!visited[w]){

//為u的尚未訪問的鄰接頂點visited[w]=TRUE;

//標記為已訪問

Visit(w);

//訪問

Q.push(w);

//入隊列}}}}}7.4圖的應用-無向圖的連通分量和生成樹對無向圖進行遍歷時，對于連通圖，僅需從圖中任一頂點出發，進行深度優先搜索或廣度優先搜索，便可訪問到圖中所有頂點。深度優先生成樹/森林廣度優先生成樹/森林7.4圖的應用-無向圖的連通分量和生成樹無向圖的連通分量和生成樹Typedefstruct{…}//圖的結構定義//見鄰接矩陣定義typedefstructCSNode{//孩子-兄弟鏈表的節點定義VertexTypedata;//頂點信息structCSNode*firstchild;//指向第一個孩子structCSNode*nextsibling;//指向下一個兄弟}CSNode,*CSTree;boolvisited[MAX_VERTEX_NUM];//訪問標志數組intFirstAdjVex(constGraph&G,intv){//獲取第一個鄰接頂點for(inti=0;i<G.vexnum;++i){if(G.arcs[v][i].adj!=0){//如果存在邊returni；}return-1;//沒有鄰接頂點}intNextAdjVex(constGraph&G,intv,intw){//獲取下一個鄰接頂點for(inti=w+1;i<G.vexnum;++i){if(G.arcs[v][i].adj!=0){//如果存在邊returni;}}return-1;//沒有下一個鄰接頂點}無向圖的連通分量和生成樹voidDFSTree(Graph&G,intv,CSTree&p){//深度優先搜索生成樹visited[v]=TRUE;//標記為已訪問for(intw=FirstAdjVex(G,v);w!=-1;w=NextAdjVex(G,v,w)){if(!visited[w]){//如果w未被訪問CSTrees=(CSTree)malloc(sizeof(CSNode));//創建新節點s->data=G.vexs[w];//設置頂點信息s->firstchild=NULL;s->nextsibling=NULL;if(p->firstchild==NULL){//如果p沒有孩子p->firstchild=s;//設置s為p的第一個孩子}else{//如果p已經有孩子CSTreeq=p->firstchild;while(q->nextsibling!=NULL){//找到最后一個兄弟q=q->nextsibling;}q->nextsibling=s;//將s添加為最后一個兄弟} DFSTree(G,w,s);//遞歸生成以w為根的子樹 } }}無向圖的連通分量和生成樹voidDFSForest(Graph&G,CSTree&T){//深度優先生成森林T=NULL;//初始化森林為空memset(visited,FALSE,sizeof(visited));//初始化訪問標志數組CSTreeq=NULL;//q用于指向當前生成樹的根for(intv=0;v<G.vexnum;++v){if(!visited[v]){//如果v未被訪問CSTreep=(CSTree)malloc(sizeof(CSNode));//創建新節點p->data=G.vexs[v];//設置頂點信息p->firstchild=NULL;p->nextsibling=NULL;if(!T){//如果是第一棵生成樹T=p;//設置T為第一棵生成樹的根

}else{//如果不是第一棵生成樹q->nextsibling=p;//將p設置為前一棵生成樹的兄弟} q=p;//更新q為當前生成樹的根DFSTree(G,v,p);//生成以p為根的生成樹}}}7.4圖的應用-有向圖的強連通分量取圖中任意一個頂點u作為起始點進行DFS，當DFS當前訪問的頂點v不存在任何一條邊e，e=<v,v'>，v'為未訪問過的頂點時，頂點v就是一個強連通分量；當DFS當前訪問的頂點v存在一條邊e，e=<v,v'>，頂點v'為已經訪問的頂點且還未訪問完成的頂點（存在一個從頂點v到頂點v'的回路）時，頂點v到頂點v'所在路徑（DFS過程中）中的頂點都在一個強連通分支中，該頂點集合記為V'，再驗證其他頂點u，是否存在頂點x∈V'，邊<u,x>∈E，并且存在頂點x'∈V'，邊<x',u>∈E。若存在，則將頂點u也加入到強連通分量V'中；若不存在，則V'就是一個強連通分量。從圖G中去除V'中的頂點以及與V'中的頂點相關聯的邊，再次進行DFS求取下一個強連通分量，直至圖G中不存在任何頂點。7.4圖的應用-最小生成樹(MST)問題定義在一個連通的帶權無向圖中，尋找一個包含所有頂點的無環子圖（樹），使得所有邊的權重之和最小。這個子圖即為最小生成樹(MinimumSpanningTree)。應用場景廣泛應用于網絡布線、道路建設、電路設計等領域。核心目標是在保證所有節點連通的前提下，使用最小的成本（如距離、費用、時間）構建連接網絡。7.4圖的應用-最小生成樹(MST)ABDCEF32234413ABDCEF22313最小生成樹，權重之和為11ABDCEF32413不是最小生成樹，權重之和為13不是最小生成樹，存在回路ABDCEF32231Prim算法算法核心思想1.初始化起點生成樹初始狀態僅包含一個起始頂點，隨后逐步擴展。2.貪心選擇最小邊每次從“已加入頂點”和“未加入頂點”之間，選擇權值最小的邊。3.擴展與終止將選中的邊對應的頂點加入生成樹，重復此過程直到所有頂點都被包含。Prim算法動態演示(1)第一步：初始化與起點選擇選擇起始頂點：選擇任意頂點（如頂點A），將其加入生成樹的頂點集合U。初始化lowcost數組：創建數組lowcost，其中lowcost[v]表示頂點v到集合U的最小權值邊的權重。初始時，只有起點的權值為0，其余為無窮大。Prim算法動態演示(2)核心步驟解析：貪心選擇與更新1.貪心選擇頂點在未加入集合U的頂點中，找到lowcost值最小的頂點v，將其加入U，并將對應的最小權值邊加入生成樹。2.更新lowcost數組遍歷新頂點v的所有鄰接頂點w。若w未加入U且邊(v,w)的權值小于lowcost[w]，則更新lowcost[w]為該邊權值，確保始終記錄連接生成樹的最短路徑。Prim算法動態演示(3)第三步：完成最小生成樹迭代過程：重復第二步的貪心策略，每次選擇權值最小的邊，將新的頂點加入集合U。終止條件：當所有頂點都被加入到集合U中時，算法結束。最終結果：此時被選中的邊構成了圖的最小生成樹(MST)，它連接了所有頂點且總權重最小。Prim算法動態演示(3)Prim算法實現代碼核心思想與數據結構lowcost數組記錄圖中各頂點到生成樹集合的最小邊權值。visited數組標記頂點是否已被加入到最小生成樹中。算法步驟1.初始化距離數組。2.循環選擇最近頂點并入樹。3.更新剩余頂點的距離。C語言實現代碼struct{//圖的鄰接矩陣定義最小生成樹的輔助數組VertexTypeadjvex;

//u到v的最小權值邊的頂點VRTypelowcost;

//邊的權值}closedge[MAX_VERTEX_NUM];intLocateVex(Graph&G,VertexTypeu){

//定位頂點for(inti=0;i<G.vexnum;++i){if(G.vexs[i]==u){returni;}}return-1;//未找到}Prim算法實現代碼C語言實現代碼intminimum(Graph&G){

//尋找最小代價邊的頂點intmin=INT_MAX;intk=-1;for(inti=0;i<G.vexnum;++i){if(closedge[i].lowcost!=0&&closedge[i].lowcost<min){min=closedge[i].lowcost;k=i;}}returnk;}Prim算法實現代碼C語言實現代碼voidMiniSpanTree_P(Graph&G,VertexTypeu){//普里姆算法intk=LocateVex(G,u);//找到起始頂點u的位置for(int