數(shù)據(jù)結(jié)構(gòu)基本知識.ppt

1、數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)知識,熟識數(shù)據(jù)結(jié)構(gòu)相關(guān)的概念、知識內(nèi)容 熟記數(shù)據(jù)結(jié)構(gòu)的基本操作及相應(yīng)的代碼實現(xiàn) 理解數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)，能根據(jù)題目要求選擇合適的數(shù)據(jù)結(jié)構(gòu) 掌握基本操作及數(shù)據(jù)結(jié)構(gòu)的基本應(yīng)用，熟練基本應(yīng)用的程序設(shè)計,一、棧 1、棧的定義 棧是一種線性表，對它的插入和刪除都限制地表的同一端進行。這一端叫做棧的“頂”，另一端則叫做棧的“底”。 特點:后進先出(LIFO)、或者先進后出（FILO） 通常?？梢杂庙樞虻姆绞酱鎯?數(shù)組)，分配一塊連續(xù)的存儲區(qū)域存放棧中的表目，并用一個變量t指向當前棧頂（如下圖）。,假設(shè)棧中表目數(shù)的上限為m，所有表目都具有同一類型stype，則可以用下列方式定義棧： Const

2、m=棧表目數(shù)的上限； Var s： array1m of stype ；棧 t： integer； 棧頂指針，初始值為 注意：不一定進棧結(jié)束后才出棧，進出棧可交叉進行。,2、棧的基本操作 棧的基本操作包括初始化（init）、進棧（push）、出棧（pop）和讀取棧頂元素（top）四種。 1） 過程init(s,t) procedure init; begin t:=0; end; 2)、過程push(x)往棧s中壓入一個值為x的數(shù)據(jù)： procedure push（ x：stype)； begin tt+1； stx； x入棧 end；Push,3)、函數(shù)pop從棧中彈出一個表目 functi

3、on pop ：stype； begin popst； 棧頂元素出棧 tt-1； 指針下移 end；pop,4)、函數(shù)top讀棧頂元素 function top ：stype； begin if t=0 then writeln (stack empty) else topst； 返回棧頂元素 end；top,【競賽試題】 以下哪一個不是棧的基本運算( C) (NOIP7) A)刪除棧頂元素 B)刪除棧底的元素 C)判斷棧是否為空 D)將棧置為空棧 一個棧的輸入順序為1、2、3、4、5，下列序列中可能是棧的輸出序列是 ( BCD )。 (A)54312 (B)2415 (C)21543 (D)

4、1253,若已知一個棧的入棧順序是1，2，3，n，其輸出序列為P1，P2，P3，Pn，若P1是n，則Pi是(C ) (NOIP7) A)i B)n-1 C)n-i+1 D)不確定 n-i+1 棧的排列遵循先進后（即后進先出）出的原則 因為P1是n，是出棧的第一個數(shù)字，說明在n之前進棧的數(shù)字都沒有出棧，所以這個順序是確定的。還可以知道，最后出棧的一定是數(shù)字1，也就是Pn。代入這個式子，是正確的。,4、設(shè)有一個順序棧S，元素S1, S2, S3, S4, S5, S6依次進棧，如果6個元素的出棧順序為S2, S3, S4, S6, S5, S1，則順序棧的容量至少應(yīng)為多少？A 3 B) 4 C)

5、5 D) 6 5、向順序棧中壓入新元素時，應(yīng)當（ A ）。 A先移動棧頂指針，再存入元素 B先存入元素，再移動棧頂指針 C先后次序無關(guān)緊要 D同時進行,二、隊列 1 隊列的定義 所謂隊列，就是允許在一端進行插入，在另一端進行刪除的線性表。允許插入的一端稱為隊尾，通常用一個隊尾指針w指向隊尾元素，即w總是指向最后被插入的元素；允許刪除的一端稱為隊首，通常也用一個隊首指針t指向排頭元素。初始時t=w=0（如下圖）。,3,2,6,5,4,1,9,隊列頭 t,隊列尾 w,當他tw時,隊列空,隊列數(shù)組a下標： 1 2 3 4 5 6 7,我們按照如下方式定義隊列： Const m=隊列元素的上限； Ty

6、pe equeue=array1m of qtype； 隊列的類型定義 Var q：equeue； 隊列 t，w：integer； 隊尾指針和隊首指針,2、隊列的基本運算 隊列的運算主要有兩種：入隊（aDD）和出隊（DEL）,1、過程ADD(x)在隊列q的尾端插入元素x procedure ADD( x：qtyper)； begin 后移隊尾指針并插入元素x w:=w+1； qwx； end；ADD,2、函數(shù)DEL取出q隊列的隊首元素 function DEL； begin 取出隊首元素并后移隊首指針 del:=qt； t:=t+1; end；DEL,【競賽試題】 已知隊列（13，2，11，3

7、4，41，77，5，7，18，26，15），第一個進入隊列的元素是13，則第五個出隊列的元素是（B ）。(NOIP9) A） 5 B） 41 C） 77 D） 13 E） 18 設(shè)棧S和隊列Q的初始狀態(tài)為空，元素e 1 ，e 2 ，e 3 ，e 4 ，e 5 ，e 6依次通過棧S，一個元素出棧后即進入隊列Q，若出隊的順序為e 2 ，e 4 ，e 3 ，e 6 ，e 5 ，e 1 ，則棧S的容量至少應(yīng)該為（ B ）。(NOIP8) A）2 B）3 C）4 D）5,棧、隊列屬于線性結(jié)構(gòu)。在這種結(jié)構(gòu)中，不管其存儲方式（順序和鏈式）如何，數(shù)據(jù)元素的邏輯位置之間呈線性關(guān)系，即每一個數(shù)據(jù)元素通常只有一個前

8、驅(qū)（除第一個元素外）和一個后繼（除最后一個元素外）。 但也有很多問題數(shù)據(jù)元素間的邏輯關(guān)系不能用線性結(jié)構(gòu)明確、方便地描述出來。一般來說，至少存在一個結(jié)點（數(shù)據(jù)元素）有多于一個前驅(qū)或后繼的數(shù)據(jù)結(jié)構(gòu)稱為非線性結(jié)構(gòu)。具有非線性結(jié)構(gòu)特征的數(shù)據(jù)結(jié)構(gòu)有兩種 樹，圖,三、樹,一）、.樹的概念 1、樹的定義 樹是一種常見的非線性的數(shù)據(jù)結(jié)構(gòu)。樹的遞歸定義如下： 樹是n(n0)個結(jié)點的有限集，這個集合滿足以下條件： 有且僅有一個結(jié)點沒有前驅(qū)（父親結(jié)點），該結(jié)點稱為樹的根； 除根外，其余的每個結(jié)點都有且僅有一個前驅(qū)； 除根外，每一個結(jié)點都通過唯一的路徑連到根上（否則有環(huán)）。這條路徑由根開始，而未端就在該結(jié)點上，且除根

9、以外，路徑上的每一個結(jié)點都是前一個結(jié)點的后繼（兒子結(jié)點）； 由上述定義可知，樹結(jié)構(gòu)沒有封閉的回路。,樹可以只有根結(jié)點,2、結(jié)點的分類 結(jié)點一般分成三類 根結(jié)點：沒有父親的結(jié)點。在樹中有且僅有一個根結(jié)點。 分支結(jié)點：除根結(jié)點外，有孩子的結(jié)點稱為分支結(jié)點。b，c，x，t，d，i。分支結(jié)點亦是其子樹的根； 葉結(jié)點：沒有孩子的結(jié)點稱為樹葉。w，h，e，f，s，m，o，n，j，u為葉結(jié)點。 根結(jié)點到每一個分支結(jié)點或葉結(jié)點的路徑是唯一的。從根r到結(jié)點i的唯一路徑為rcti。,3、有關(guān)度的定義 結(jié)點的度：一個結(jié)點的子樹數(shù)目稱為該結(jié)點的度（區(qū)分圖中結(jié)點的度）。圖中，結(jié)點i度為3，結(jié)點t的度為2，結(jié)點b的度為1

10、。顯然，所有樹葉的度為0。 樹的度：所有結(jié)點中最大的度稱為該樹的度(寬度）。圖中樹的度為3。,4、樹的深度（高度） 樹是分層次的。結(jié)點所在的層次是從根算起的。根結(jié)點在第一層，根的兒子在第二層，其余各層依次類推。圖中的樹共有五層。在樹中，父結(jié)點在同一層的所有結(jié)點構(gòu)成兄弟關(guān)系。（e和i也是兄弟關(guān)系） 樹中最大的層次稱為樹的深度，亦稱高度。圖中樹的深度為5。,5、森林 所謂森林，是指若干棵互不相交的樹的集合。如圖去掉根結(jié)點r，其原來的三棵子樹Ta，Tb，Tc的集合Ta，Tb，Tc就為森林，這三棵子樹的具體形態(tài)如圖（c）。,6、有序樹和無序樹 按照樹中同層結(jié)點是否保持有序性，可將樹分為有序樹和無序樹。

11、如果樹中同層結(jié)點從左而右排列，其次序不容互換，這樣的樹稱為有序樹；如果同層結(jié)點的次序任意，這樣的樹稱為無序樹。 有序樹 樹中任意節(jié)點的子結(jié)點之間有順序關(guān)系，這種樹稱為有序樹 無序樹 樹中任意節(jié)點的子結(jié)點之間沒有順序關(guān)系，這種樹稱為無序樹,也稱為自由樹，,三）、二叉樹的概念 二叉樹是一種很重要的非線性數(shù)據(jù)結(jié)構(gòu)，它的特點是每個結(jié)點最多有兩個孩子，且其子樹有左右之分（二叉樹是有序樹，次序不能任意顛倒）。（二叉樹可以每個節(jié)點只有一個孩子） 1、二叉樹的遞歸定義和基本形態(tài) 二叉樹是以結(jié)點為元素的有限集，它或者為空，或者滿足以下條件： 有一個特定的結(jié)點稱為根； 余下的結(jié)點分為互不相交的子集L和R，其中L是

12、根的左子樹；R是根的右子樹；L和R又是二叉樹； ？ 二叉樹是不是樹？二叉樹樹？,由上述定義可以看出，二叉樹和樹是兩個不同的概念 樹的每一個結(jié)點可以有任意多個后件，而二叉樹中每個結(jié)點的后繼不能超過2； 樹的子樹可以不分次序（除有序樹外）；而二叉樹的子樹有左右之分。我們稱二叉樹中結(jié)點的左后件為左兒子，右后件為右兒子。 前面引入的有關(guān)樹的一些基本術(shù)語對二叉樹仍然適用。下圖列出二叉樹的五種基本形態(tài)：,2、二叉樹的兩個特殊形態(tài) 滿二叉樹： 如果一棵深度為K的二叉樹，共有2K-1個結(jié)點，即第I層有2I-1的結(jié)點，稱為滿二叉樹。(a) 完全二叉樹：如果一棵二叉樹最多只有最下面兩層結(jié)點度數(shù)可以小于2，并且最下

13、面一層的結(jié)點都集中在該層最左邊的若干位置上，則稱此二叉樹為完全二叉樹（例如下圖(b)） 滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹,3、二叉樹的三個主要性質(zhì) 性質(zhì)1：在二叉樹的第i（1）層上，最多有2i-1個結(jié)點 性質(zhì)2：在深度為k(k1)的二叉樹中最多有2k-1個結(jié)點。 性質(zhì)3：在任何二叉樹中，葉子結(jié)點數(shù)總比度為2的結(jié)點多 1。n0=n2+1,(NOIP9)一個高度為h 的二叉樹最小元素數(shù)目（C）。A） 2h+1B） h C） 2h-1D） 2hE） 2h-1 (NOIP8)按照二叉數(shù)的定義，具有3個結(jié)點的二叉樹有（ C ）種。 A）3 B）4 C）5 D）6 (NOIP8)設(shè)有一

14、棵k叉樹，其中只有度為0和k兩種結(jié)點，設(shè)n 0 ，n k ，分別表示度為0和度為k的結(jié)點個數(shù)，試求出n 0 和n k之間的關(guān)系（n 0 = 數(shù)學表達式，數(shù)學表達式僅含n k 、k和數(shù)字）。,(NOIP7).一棵二叉樹的高度為h，所有結(jié)點的度為0，或為2，則此樹最少有(B )個結(jié)點 （帶個數(shù)進去試試） A)2h-1 B)2h-1 C)2h+1 D)h+1,(NOIP6)已知，按中序遍歷二叉樹的結(jié)果為：abc問：有多少種不同形態(tài)的二叉樹可以得到這一遍歷結(jié)果，并畫出這些二叉樹。 5種 、給出一棵二叉樹的中序遍歷：DBGEACHFI與后序遍歷：DGEBHIFCA畫出此二叉樹。 D B GE A C H

15、FI D GE B HIF C A,A,B,D,E,G,C,F,H,I,1、將一棵有100個結(jié)點的完全二叉樹從根結(jié)點這一層開始，每一層從左到右依次對結(jié)點進行編號，根結(jié)點的編號為1，則編號為49的結(jié)點的左孩子的編號為 A 98 B 99 C 97 D 50 2、對二叉樹從1進行連續(xù)編號，要求每個結(jié)點的編號大于其左右孩子的編號，同一結(jié)點的左右孩子中，其左孩子的編號小于其右孩子的 編號，則可以采取 C 次序的遍歷方法。 A 先序 B中序 C后序 D從根開始的層次遍歷 3、有n個結(jié)點并且其高度為n的二叉樹的數(shù)目是 A、n B、 2n C、 2n-1 D、 2(n-1),4、有64個結(jié)點的完全二叉樹的深

16、度為（ ） A) 8 B) 7 C) 6 D) 5,四）、二叉樹的遍歷 二叉樹的遍歷是不重復(fù)地訪問二叉樹中的每一個結(jié)點。在訪問到每個結(jié)點時，可以取出結(jié)點中的信息，或?qū)Y(jié)點作其它的處理。 如果用L、D、R分別表示遍歷左子樹、訪問根結(jié)點、遍歷右子樹，限定先左后右的次序，三種組合 DLR、LDR、 LRD 這三種遍歷規(guī)則分別稱為先（前）序遍歷、中序遍歷和后序遍歷（以根為標準）。二叉樹的存儲采用動態(tài)的二重鏈表形式。 根左右、左根右、左右根,為了方便敘述，我們以下圖為例解釋三種遍歷規(guī)則，并且分別以二叉鏈表和數(shù)組兩種存儲結(jié)構(gòu)給出三種遍歷的程序。,前序遍歷 前序遍歷的規(guī)則如下： 若二叉樹為空，則退出。否則

17、訪問處理根結(jié)點； 前序遍歷左子樹； 前序遍歷右子樹； a b d e h i c f g,中序遍歷 中序遍歷的規(guī)則如下： 若二叉樹為空，則退出；否則 中序遍歷左子樹； 訪問處理根結(jié)點； 中序遍歷右子樹； 若中序遍歷上圖中的二叉樹，可以得到如下的中序序列： d b h e i a f c g,后序遍歷 后序遍歷的規(guī)則如下： 若二叉樹為空，則退出；否則 后序遍歷左子樹； 后序遍歷右子樹； 訪問處理根結(jié)點； 若后序遍歷上圖中的二叉樹，可以得到如下的后序序列 d h i e b f g c a,五）、由二叉樹的兩種遍歷順序確定樹結(jié)構(gòu) 遍歷二叉樹（如下圖）有三種規(guī)則： 前序遍歷：根左子樹右子樹； 中序遍

18、歷：左子樹根右子樹； 后序遍歷：左子樹右子樹根；,2、(NOIP7)已知一棵二叉樹的結(jié)點名為大寫英文字母，其中序與后序遍歷的順序分別為： 中序遍歷:CBGEAFHDIJ 后序遍歷:CGEBHFJIDA 求該二叉樹的先序遍歷的順序為：,1、給出一棵二叉樹的先序遍歷：ABCDEFGH中序遍歷：CBEDAGHF畫出此二叉樹并寫出后序遍歷結(jié)果。 A B CDE F GH C B ED A GH F,石子合并問題 有n堆石子,每堆有一個重量,每次把2堆石子合并成1堆,付出的代價為這兩堆石子的重量之和,如果把這n堆石子最后合并成1堆石子,怎樣合并才能使付出的代價最小,求出最小的代價.,六）、最優(yōu)二叉樹(哈

19、夫曼樹),顯然圖(D)所示的合并方法付出的代價最小:54 5*2+（2+4）*3+（6+7）*2=54,例如n=5,重量 分別為7、5、2、4、6。,(D)L=6+11+13+24=54,1、最優(yōu)二叉樹的定義 在具有n個帶權(quán)葉結(jié)點的二叉樹中，使所有葉結(jié)點的帶權(quán)路徑長度之和（即二叉樹的帶權(quán)路徑長度）為最小的二叉樹，稱為最優(yōu)二叉樹（又稱最優(yōu)搜索樹或哈夫曼樹），即最優(yōu)二叉樹使 （wk第k個葉結(jié)點的權(quán)值；pk第k個葉結(jié)點的帶權(quán)路徑長度）達到最小。,2、最優(yōu)二叉樹的構(gòu)造方法 假定給出n個結(jié)點ki(i=1n)，其權(quán)值分別為wi(i=1n)。要構(gòu)造以此n個結(jié)點為葉結(jié)點的最優(yōu)二叉樹，其構(gòu)造方法如下： 首先，將

20、給定的n個結(jié)點構(gòu)成n棵二叉樹的集合F=T1，T2，Tn。其中每棵二叉樹Ti中只有一個權(quán)值為wi的根結(jié)點ki，其左、右子樹均為空。然后做以下兩步 在F中選取根結(jié)點權(quán)值最小的兩棵二叉樹作為左右子樹，構(gòu)造一棵新的二叉樹，并且置新的二叉樹的根結(jié)點的權(quán)值為其左、右子樹根結(jié)點的權(quán)值之和； 在F中刪除這兩棵二叉樹，同時將新得到的二叉樹加入F中； 重復(fù)、，直到在F中只含有一棵二叉樹為止。這棵二叉樹便是最優(yōu)二叉樹。 以上構(gòu)造最優(yōu)二叉樹的方法稱為哈夫曼（huffmann）算法。,例如：給定五個結(jié)點k1，k2，k3，k4，k5，其權(quán)值分別為16、2、18、16、23。構(gòu)造最優(yōu)二叉樹的過程如下： 構(gòu)造初始集合F，F(xiàn)中

21、各二叉樹根結(jié)點的權(quán)值分別為16，2，18，16，23（如下圖）：,以具有權(quán)值16及2的根結(jié)點的兩棵二叉樹為左、右子樹，構(gòu)造一棵根權(quán)值為18的新二叉樹，并從F中刪去這兩棵二叉樹（如下圖）：,以同樣的方法，得到一個新二叉樹的集合F，其根結(jié)點的權(quán)值分別為23，18，34（如下圖）：, 又得到一個新二叉樹的集合F，其根結(jié)點的權(quán)值分別為34，41（如下圖）：,最后得到最優(yōu)二叉樹（如下圖），其根結(jié)點的權(quán)值為75，結(jié)點數(shù)為2*5-1=9。,3、哈夫曼編碼 使用頻率高的采用短的的編碼,則總的編碼長度便可減少.,例如:在某通訊中只使用abcd四種字符,其出現(xiàn)頻率分別為:0.4,0.3,0.2,0.1。請進行哈夫

22、曼編碼。使通訊碼盡可能的短 并寫出信息：bbdaac的編碼。,1.給定一個整數(shù)集合3，5，6，9，12，下列二叉樹哪個是該整數(shù)集合對應(yīng)的霍夫曼（Huffman）樹。 （ ）,2、已知如圖所示的哈夫曼樹，那么電文CDAA的編碼是 A 110100 B 11011100 C 010110111 D 11111100,3、若以4，5，6，7,8作為葉子結(jié)點的權(quán)值構(gòu)造哈夫曼樹，則其帶權(quán)路徑長度是 A 、69 B、 70 C 、 73 D、 68,四、 圖的基本概念 1、圖的的定義 如果數(shù)據(jù)元素集合D中的各元素之間存在任意的前驅(qū)和后繼關(guān)系R，則此數(shù)據(jù)結(jié)構(gòu)G=（D，R）稱為圖。如果將數(shù)據(jù)元素抽象為結(jié)點，元

23、素之間的先后關(guān)系用邊表示，則圖亦可以表示為G=（V，E），其中V是結(jié)點的有窮（非空）集合，E為邊的集合。如果元素a是元素b的前驅(qū)，這種先后關(guān)系對應(yīng)的邊用(a，b)表示，即(a，b)E。圖可以分為無向圖和有向圖兩種形式。,2、無向圖和有向圖無向圖：在圖G=（V，E）中，如果對于任意的a，bV，當(a，b)E時，必有（b，a）E（即關(guān)系R對稱），對稱此圖為無向圖。在一無向圖中用不帶箭頭的邊 連接兩個有關(guān)聯(lián)的結(jié)點。在具有n個結(jié)點的無向圖中，邊的最大數(shù)目為： 而邊數(shù)達到最大值的圖稱為無向完全圖。 在無向圖中一個結(jié)點相連的邊數(shù)稱為該結(jié)點的度。 圖(A) V=1,2,3,4 E=(1,2),(1,3),(

24、1,4),(2,3),(2,4),(3,4) 有向圖：如果對于任意的a，bV，當(a，b)E時 ，(b，a)E未必成立，則稱此圖為有向圖。在有向圖中，通常用帶箭頭的邊連接兩個有關(guān)聯(lián)的結(jié)點（方向由前件指向后件）。例如圖（b）為有向圖。有向圖中一個結(jié)點的后件個數(shù)稱為該結(jié)點的出度，其前件個數(shù)稱為該結(jié)點的入度。一個結(jié)點的入度和出度之和稱為該結(jié)點的度。圖中結(jié)點的最大度數(shù)稱為圖的度。例如下圖 (b)）中結(jié)點1的出度和入度分別為1，結(jié)點1和結(jié)點1度都為2。整個圖的度為2。 圖(B) V=1,2,3 E=,4、 路徑和連通集 在圖G=（V，E）中，如果對于結(jié)點a，b，存在滿足下述條件的結(jié)點序列x1xk(k1)

25、 x1=a，xk=b (xi，xi+1)E i=1k-1 則稱結(jié)點序列x1=a，x2，xk=b為結(jié)點a到結(jié)點b的一條路徑，而路徑上邊的數(shù)目k-1稱為該路徑的長度，并稱結(jié)點集合x1，xk為連通集。,V1, v2, v5, v4,5、簡單路徑和回路 如果一條路徑上的結(jié)點除起點x1和終點xk可以相同外，其它結(jié)點均不相同，則稱此路徑為一條簡單路徑。圖(a)中v1v2v3是一條簡單路徑，v1v3v4v1v3不是簡單路徑。x1=xk的簡單路徑稱為回路（也稱為環(huán)）。例如圖(b)中，v1v2v1為一條回路。,3、圖的存儲結(jié)構(gòu) 圖的相鄰矩陣表示法 相鄰矩陣是表示結(jié)點間相鄰關(guān)系的矩陣。若G=（V，E）是一個具有n

26、個結(jié)點的圖，則G的相鄰矩陣是如下定義的二維數(shù)組a，其規(guī)模為n*n,type maxn=頂點數(shù)的上限； var a：array1.maxn，1.maxnof integer； f：array array1.maxnof boolean； 頂點的訪問標志序列,上圖中的圖G1和圖G2對應(yīng)的相鄰矩陣分別為：,0 1 1 1 01 0 1 1 11 1 0 1 01 1 1 0 10 1 0 1 0,相鄰矩陣的特點： 1)無向圖的相鄰矩陣是對稱的，而有向圖則不是。,2)相鄰矩陣方便度數(shù)的計算。用相鄰矩陣表示圖: (1)容易判定任意兩個結(jié)點之間是否有邊相聯(lián); (2)并容易求得各個結(jié)點的度數(shù)。 (對于無權(quán)無

27、向圖的相鄰矩陣，第i行元素值的和就是Vi的度數(shù)；對于無權(quán)有向圖的相鄰矩陣，第i行元素值的和就是Vi的出度，第i列元素值的和就是Vi的入度；)對于有權(quán)無向圖的相鄰矩陣，第i行（或第i列）中元素值0的元素個數(shù)就是Vi的度數(shù)；對于有權(quán)有向圖的相鄰矩陣，第i行中元素值0的元素個數(shù)就是Vi的出度；第i列元素值0的元素個數(shù)就是Vi的入度。,7、圖的遍歷 給出一個圖G和其中任意一個結(jié)點V0，從V0出發(fā)系統(tǒng)地訪問G中所有結(jié)點，每一個結(jié)點被訪問一次，這就叫圖的遍歷。 通常有兩種遍歷方法： 深度優(yōu)先搜索dfs 廣度優(yōu)先搜索bfs 它們對無向圖和有向圖都適用。我們以相鄰矩陣存儲結(jié)構(gòu)給出深度優(yōu)先搜索和廣度優(yōu)先搜索的程

28、序。,8、深度優(yōu)先搜索DFS 深度優(yōu)先搜索類似于樹的前序遍歷，是樹的前序遍歷的推廣。其搜索過程如下： 假設(shè)初始時所有結(jié)點未曾被訪問。深度優(yōu)先搜索從某個結(jié)點V0出發(fā)，訪問此結(jié)點。然后依次從V0的未被訪問的鄰接點出發(fā)深度優(yōu)先遍歷圖，直至圖中所有和V0有路徑相連的結(jié)點都被訪問到。若此時圖中尚有結(jié)點未被訪問，則另選一個未曾訪問的結(jié)點作起始點，重復(fù)上述過程，直至圖中所有結(jié)點都被訪問為止。換句話說，深度優(yōu)先搜索遍歷圖的過程是以V0為起始點，由左而右，依次訪問由V0出發(fā)的每條路徑。,9、廣度優(yōu)先搜索(寬度優(yōu)先搜索）BFS 廣度優(yōu)先搜索類似于樹的按層次遍歷的過程，其搜索過程如下： 假設(shè)從圖中某結(jié)點v0出發(fā)，在訪問了v0之后依次訪問v0的各個未曾訪問的鄰接點，然后分別從這些鄰接點出發(fā)按廣度優(yōu)先搜索的順序遍歷圖，直至圖中所有可被訪問的結(jié)點都被訪問到。若此時圖中尚有結(jié)點未