pascal第十二講樹(shù)與圖的簡(jiǎn)介

1、ascal第十二講樹(shù)與圖的簡(jiǎn)介數(shù)據(jù)結(jié)構(gòu)1. 線性結(jié)構(gòu)（棧、隊(duì)列）的回顧2. 非線性結(jié)構(gòu)（樹(shù)）的簡(jiǎn)介3. 非線性結(jié)構(gòu)（圖）的簡(jiǎn)介4. 數(shù)據(jù)結(jié)構(gòu)之簡(jiǎn)單總結(jié)1. 線性結(jié)構(gòu)（棧、隊(duì)列）的回顧什么是棧？什么是隊(duì)列？壽光現(xiàn)代中學(xué)棧的應(yīng)用1【括號(hào)匹配】1、棧S初始狀態(tài)為空，現(xiàn)有5個(gè)元素組成的序列1，2，3，4，5，對(duì)該序列在棧S上一次進(jìn)行如下操作（從序列中的1開(kāi)始，出棧后不再進(jìn)棧）：進(jìn)棧、進(jìn)棧、進(jìn)棧、出棧、進(jìn)棧、出棧、進(jìn)棧。問(wèn)出棧的元素序列是_ （noip1998） (A) 5,4,3,2,1 (B) 2,1(C) 2,3 (D) 3,4壽光現(xiàn)代中學(xué)棧的應(yīng)用2【括號(hào)匹配】 判斷包含有括號(hào)，的字符串是否匹配。

2、【樣例1】 輸入：abcabbmaa 輸出：yes【樣例2】 輸入：abcabbmaa 輸出：no壽光現(xiàn)代中學(xué)從字符串中讀入一個(gè)左括號(hào)時(shí)，就將其壓入棧s中；當(dāng)讀入一個(gè)右括號(hào)時(shí),就從棧頂取出左括號(hào)檢查比較,看是否匹配,如果匹配,就將左括號(hào)出棧;否則顯示不匹配。全部字符串讀完后,最后檢查棧是否為空,如果不空,左括號(hào)無(wú)右括號(hào)與之匹配,顯示不匹配?！締?wèn)題分析】壽光現(xiàn)代中學(xué)var i,c:integer; s:string; a:array1.2000 of char; f:boolean;procedure push(l:char); begin inc(c); ac:=l; end;procedur

3、e pop; begin dec(c); end;【參考程序】壽光現(xiàn)代中學(xué)begin f:=true; readln(s); c:=0; for i:=1 to length(s) do begin if f=false then break; if si= then push(); if si= then push(); if si= then push( then begin if ac= then pop else f:=false;end; if si=) then begin if ac=( then pop else f:=false;end; end; if f and (c=0

4、) then writeln(yes) else writeln(no);end.n壽光現(xiàn)代中學(xué) 一矩形陣列由數(shù)字0到9組成,數(shù)字1到9代表細(xì)胞,細(xì)胞的定義為沿細(xì)胞數(shù)字上下左右還是細(xì)胞數(shù)字則為同一細(xì)胞,求給定矩形陣列的細(xì)胞個(gè)數(shù)。輸入：整數(shù)m,n(m行，n列) （1=m=80,1=n0) and (x0) and (yw;直至隊(duì)空為止 end;壽光現(xiàn)代中學(xué)begin fillchar(pic,sizeof(pic),0); num:=0; fillchar(h,sizeof(h),0); readln(m,n); for i:=1 to m do begin readln(s); for j:=

5、1 to n do if sj=0 then pici,j:=0 else pici,j:=1; end; for i:=1 to m do for j:=1 to n do if pici,j=1 then doing(i,j);在矩陣中尋找細(xì)胞 writeln(num);end.壽光現(xiàn)代中學(xué)數(shù)據(jù)結(jié)構(gòu)樹(shù)壽光現(xiàn)代中學(xué) 棧、隊(duì)列屬于線性結(jié)構(gòu)。在這種結(jié)構(gòu)中，不管其存儲(chǔ)方式（順序和鏈?zhǔn)剑┤绾?，?shù)據(jù)元素的邏輯位置之間呈線性關(guān)系，即每一個(gè)數(shù)據(jù)元素通常只有一個(gè)前驅(qū)（除第一個(gè)元素外）和一個(gè)后繼（除最后一個(gè)元素外）。 但也有很多問(wèn)題數(shù)據(jù)元素間的邏輯關(guān)系不能用線性結(jié)構(gòu)明確、方便地描述出來(lái)。一般來(lái)說(shuō)，至少存在一個(gè)

6、結(jié)點(diǎn)（數(shù)據(jù)元素）有多于一個(gè)前驅(qū)或后繼的數(shù)據(jù)結(jié)構(gòu)稱為非線性結(jié)構(gòu)。具有非線性結(jié)構(gòu)特征的數(shù)據(jù)結(jié)構(gòu)有兩種：樹(shù) 圖樹(shù)v0v3v1v6v2v4v5壽光現(xiàn)代中學(xué)一、樹(shù)的概念1、樹(shù)的定義 樹(shù)是一種常見(jiàn)的非線性的數(shù)據(jù)結(jié)構(gòu)。樹(shù)的遞歸定義如下： 樹(shù)是n(n0)個(gè)結(jié)點(diǎn)的有限集，這個(gè)集合滿足以下條件： 有且僅有一個(gè)結(jié)點(diǎn)沒(méi)有前驅(qū)（父親結(jié)點(diǎn)），該結(jié)點(diǎn)稱為樹(shù)的根； 除根外，其余的每個(gè)結(jié)點(diǎn)都有且僅有一個(gè)前驅(qū)； 除根外，每一個(gè)結(jié)點(diǎn)都通過(guò)唯一的路徑連到根上（否則有環(huán)）。這條路徑由根開(kāi)始，而未端就在該結(jié)點(diǎn)上，且除根以外，路徑上的每一個(gè)結(jié)點(diǎn)都是前一個(gè)結(jié)點(diǎn)的后繼（兒子結(jié)點(diǎn)）；由上述定義可知，樹(shù)結(jié)構(gòu)沒(méi)有封閉的回路。 壽光現(xiàn)代中學(xué)壽光現(xiàn)代中

7、學(xué) 2、結(jié)點(diǎn)的分類 結(jié)點(diǎn)一般分成三類根結(jié)點(diǎn)：沒(méi)有父親的結(jié)點(diǎn)。在樹(shù)中有且僅有一個(gè)根結(jié)點(diǎn)。分支結(jié)點(diǎn)：除根結(jié)點(diǎn)外，有孩子的結(jié)點(diǎn)稱為分支結(jié)點(diǎn)。b，c，x，t，d，i。分支結(jié)點(diǎn)亦是其子樹(shù)的根；葉結(jié)點(diǎn)：沒(méi)有孩子的結(jié)點(diǎn)稱為樹(shù)葉。w，h，e，f，s，m，o，n，j，u為葉結(jié)點(diǎn)。根結(jié)點(diǎn)到每一個(gè)分支結(jié)點(diǎn)或葉結(jié)點(diǎn)的路徑是唯一的。從根r到結(jié)點(diǎn)i的唯一路徑為rcti。壽光現(xiàn)代中學(xué) 3、有關(guān)度的定義 結(jié)點(diǎn)的度：一個(gè)結(jié)點(diǎn)的子樹(shù)數(shù)目稱為該結(jié)點(diǎn)的度（區(qū)分圖中結(jié)點(diǎn)的度）。圖中，結(jié)點(diǎn)i度為3，結(jié)點(diǎn)t的度為2，結(jié)點(diǎn)b的度為1。顯然，所有樹(shù)葉的度為0。 樹(shù)的度：所有結(jié)點(diǎn)中最大的度稱為該樹(shù)的度(寬度）。圖中樹(shù)的度為3。壽光現(xiàn)代中學(xué) 4、

8、樹(shù)的深度（高度） 樹(shù)是分層次的。結(jié)點(diǎn)所在的層次是從根算起的。根結(jié)點(diǎn)在第一層，根的兒子在第二層，其余各層依次類推。圖中的樹(shù)共有五層。在樹(shù)中，父結(jié)點(diǎn)在同一層的所有結(jié)點(diǎn)構(gòu)成兄弟關(guān)系。 樹(shù)中最大的層次稱為樹(shù)的深度，亦稱高度。圖中樹(shù)的深度為5。壽光現(xiàn)代中學(xué) 二、樹(shù)的表示方法和存儲(chǔ)結(jié)構(gòu)1、樹(shù)的表示方法 樹(shù)的表示方法一般有兩種：自然界的樹(shù)形表示法：用結(jié)點(diǎn)和邊表示樹(shù)，例如上圖采用的就是自然界的樹(shù)形表示法。樹(shù)形表示法一般用于分析問(wèn)題。壽光現(xiàn)代中學(xué) 括號(hào)表示法： 先將根結(jié)點(diǎn)放入一對(duì)圓括號(hào)中，然后把它的子樹(shù)按由左而右的順序放入括號(hào)中，而對(duì)子樹(shù)也采用同樣方法處理：同層子樹(shù)與它的根結(jié)點(diǎn)用圓括號(hào)括起來(lái)，同層子樹(shù)之間用逗號(hào)

9、隔開(kāi)，最后用閉括號(hào)括起來(lái)。例如圖可寫(xiě)成如下形式（r（a（w，x（d（h），e），b（f），c（s，t（i（m，o，n），j），u）壽光現(xiàn)代中學(xué) 2、樹(shù)的存儲(chǔ)結(jié)構(gòu)樹(shù)的存儲(chǔ)結(jié)構(gòu)一般有兩種靜態(tài)的記錄數(shù)組。所有結(jié)點(diǎn)存儲(chǔ)在一個(gè)數(shù)組中，數(shù)組元素為記錄類型，包括數(shù)據(jù)域和長(zhǎng)度為n(n 為樹(shù)的度)的數(shù)組，分別存儲(chǔ)該結(jié)點(diǎn)的每一個(gè)兒子的下標(biāo)Const n=樹(shù)的度；max=結(jié)點(diǎn)數(shù)的上限； Type node=record 結(jié)點(diǎn)類型 data：datatype； 數(shù)據(jù)域 ch：array1n of integer； 指向各兒子的下標(biāo) end；treetype=array1.maxof node； Var tree：tr

10、eetype； 樹(shù)數(shù)組壽光現(xiàn)代中學(xué)例如圖的樹(shù)，其記錄數(shù)組如下。由于未規(guī)定同層結(jié)點(diǎn)的次序，因此每個(gè)結(jié)點(diǎn)兒子的下標(biāo)序列（Treei.ch）任意。其中Treei.chj=0說(shuō)明結(jié)點(diǎn)i的第j個(gè)兒子不存在。(編號(hào)按層編號(hào))壽光現(xiàn)代中學(xué) 三、二叉樹(shù)的概念 二叉樹(shù)是一種很重要的非線性數(shù)據(jù)結(jié)構(gòu)，它的特點(diǎn)是每個(gè)結(jié)點(diǎn)最多有兩個(gè)孩子，且其子樹(shù)有左右之分（有序樹(shù)，次序不能任意顛倒）。1、二叉樹(shù)的遞歸定義和基本形態(tài) 二叉樹(shù)是以結(jié)點(diǎn)為元素的有限集，它或者為空，或者滿足以下條件：有一個(gè)特定的結(jié)點(diǎn)稱為根；余下的結(jié)點(diǎn)分為互不相交的子集L和R，其中L是根的左子樹(shù)；R是根的右子樹(shù)；L和R又是二叉樹(shù)；？ 二叉樹(shù)是不是樹(shù)？二叉樹(shù)樹(shù)？壽

11、光現(xiàn)代中學(xué)由上述定義可以看出，二叉樹(shù)和樹(shù)是兩個(gè)不同的概念樹(shù)的每一個(gè)結(jié)點(diǎn)可以有任意多個(gè)，而二叉樹(shù)中每個(gè)結(jié)點(diǎn)的后繼不能超過(guò)2；樹(shù)的子樹(shù)可以不分次序（除有序樹(shù)外）；而二叉樹(shù)的子樹(shù)有左右之分。我們稱二叉樹(shù)中結(jié)點(diǎn)的左后件為左兒子，右后件為右兒子。壽光現(xiàn)代中學(xué)前面引入的有關(guān)樹(shù)的一些基本術(shù)語(yǔ)對(duì)二叉樹(shù)仍然適用。下圖列出二叉樹(shù)的五種基本形態(tài)：壽光現(xiàn)代中學(xué) 2、二叉樹(shù)的兩個(gè)特殊形態(tài)滿二叉樹(shù)： 如果一棵深度為K的二叉樹(shù)，共有2K-1個(gè)結(jié)點(diǎn)，即第I層有2I-1的結(jié)點(diǎn)，稱為滿二叉樹(shù)。(a)完全二叉樹(shù)：如果一棵二叉樹(shù)最多只有最下面兩層結(jié)點(diǎn)度數(shù)可以小于2，并且最下面一層的結(jié)點(diǎn)都集中在該層最左邊的若干位置上，則稱此二叉樹(shù)為完

12、全二叉樹(shù)（例如下圖(b)）壽光現(xiàn)代中學(xué) 3、二叉樹(shù)的三個(gè)主要性質(zhì)性質(zhì)1：在二叉樹(shù)的第i（1）層上，最多有2i-1個(gè)結(jié)點(diǎn)證明 數(shù)學(xué)歸納法證明歸納基礎(chǔ) i=1時(shí)，有2i-1=20=1,因?yàn)榈谝粚又挥幸粋€(gè)根結(jié)點(diǎn)，所以命題成立。歸納假設(shè) 假設(shè)對(duì)于所有的j（1=ji）命題成立，即第j層上至多有2j-1個(gè)結(jié)點(diǎn)，證明j=i時(shí)命題亦成立。歸納步驟 根據(jù)歸納假設(shè)，第i-1層的結(jié)點(diǎn)數(shù)至多是第2i-2個(gè)結(jié)點(diǎn)。由于二叉樹(shù)的每個(gè)結(jié)點(diǎn)至多有2個(gè)孩子，故第i層上至多有2*2i-2=2i-1個(gè)結(jié)點(diǎn)。壽光現(xiàn)代中學(xué)性質(zhì)2：在深度為k(k1)的二叉樹(shù)中最多有2k-1個(gè)結(jié)點(diǎn)。證明：根據(jù)性質(zhì)1，深度為k的二叉樹(shù)最多有：20+21+.+

13、2k-1=2k-1（等比數(shù)列求和乘2做減法）壽光現(xiàn)代中學(xué)性質(zhì)3：在任何二叉樹(shù)中，葉子結(jié)點(diǎn)數(shù)總比度為2的結(jié)點(diǎn)多1。n0=n2+1設(shè)n0為二叉樹(shù)的葉結(jié)點(diǎn)數(shù)；n1為二叉樹(shù)中度為1的結(jié)點(diǎn)數(shù)；n2為二叉樹(shù)中度為2的結(jié)點(diǎn)數(shù)，顯然所有結(jié)點(diǎn)數(shù)目 n=n0+n1+n2 （1）所有這些分支同時(shí)又為度為1和度為2的結(jié)點(diǎn)發(fā)出的。再加上根結(jié)點(diǎn)，因此又有 n=1+n1+2n2 (2)由上兩個(gè)等式求得：n0=1+n2壽光現(xiàn)代中學(xué)例題：如果一棵m度的樹(shù)中有N1個(gè)度為1的頂點(diǎn)，N2個(gè)度為2的頂點(diǎn)，N3個(gè)度為3的頂點(diǎn)，Nm個(gè)度為m的頂點(diǎn)，求該樹(shù)中葉子頂點(diǎn)個(gè)數(shù)。分析：設(shè)葉子結(jié)點(diǎn)數(shù)為N0 所有結(jié)點(diǎn)數(shù)為n，邊數(shù)(分支）為b，則有： n

14、=b+1 (1) 又b= N1+2N2+3N3+.+M*NM (2)又：n= N0+N1+N2+.+NM (3) (2),(3)代入（1）得出： N0 =N2+2N3+3N4+.+(M-1)NM+1壽光現(xiàn)代中學(xué)四、二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)有兩種形式順序存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)壽光現(xiàn)代中學(xué)1、順序存儲(chǔ)結(jié)構(gòu)將每個(gè)結(jié)點(diǎn)依次存放在一維數(shù)組中，用數(shù)組下標(biāo)指示結(jié)點(diǎn)編號(hào)，編號(hào)的方法是從根結(jié)點(diǎn)開(kāi)始編號(hào)1，然后由左而右進(jìn)行連續(xù)編號(hào)。每個(gè)結(jié)點(diǎn)的信息包括一個(gè)數(shù)據(jù)域（data）；三個(gè)指針域，其中有父結(jié)點(diǎn)編號(hào)（prt）、左兒子結(jié)點(diǎn)編號(hào)（lch）和右兒子結(jié)點(diǎn)編號(hào)（rch）。滿二叉樹(shù)和完全二叉樹(shù)一般采用順序存儲(chǔ)結(jié)構(gòu) C

15、onst m=樹(shù)中結(jié)點(diǎn)數(shù)上限； Type node=record 結(jié)點(diǎn)類型 data：datatype； 數(shù)據(jù)值 prt，lch，rch：0m； 父結(jié)點(diǎn)、左兒子、右兒子編號(hào) end； treetype=array1m of node； 二叉樹(shù)的順序表類型 Var Tree：treetype； 二叉樹(shù)壽光現(xiàn)代中學(xué)例如，采用數(shù)組tree存儲(chǔ)二叉樹(shù)（如下圖）壽光現(xiàn)代中學(xué)五、二叉樹(shù)的遍歷 二叉樹(shù)的遍歷是不重復(fù)地訪問(wèn)二叉樹(shù)中的每一個(gè)結(jié)點(diǎn)。在訪問(wèn)到每個(gè)結(jié)點(diǎn)時(shí)，可以取出結(jié)點(diǎn)中的信息，或?qū)Y(jié)點(diǎn)作其它的處理。 如果用L、D、R分別表示遍歷左子樹(shù)、訪問(wèn)根結(jié)點(diǎn)、遍歷右子樹(shù)，限定先左后右的次序，三種組合 DLR、LD

16、R、 LRD這三種遍歷規(guī)則分別稱為先（前）序遍歷、中序遍歷和后序遍歷（以根為標(biāo)準(zhǔn)）。二叉樹(shù)的存儲(chǔ)采用動(dòng)態(tài)的二重鏈表形式。壽光現(xiàn)代中學(xué)為了方便敘述，我們以下圖為例解釋三種遍歷規(guī)則，我們?cè)趯?xiě)遍歷子過(guò)程前先定義樹(shù)結(jié)構(gòu)如下：program shudebianli;type asdf=record name:char;結(jié)點(diǎn)名字 father:integer;父結(jié)點(diǎn)信息 left:integer;左孩子信息 right:integer;右孩子信息 end;var l,i,h,a:longint; s:string; t:array1.100 of asdf;壽光現(xiàn)代中學(xué)前序遍歷前序遍歷的規(guī)則如下：若二叉樹(shù)

17、為空，則退出。否則 訪問(wèn)處理根結(jié)點(diǎn)； 前序遍歷左子樹(shù)； 前序遍歷右子樹(shù)； a b d e h i c f g壽光現(xiàn)代中學(xué) procedure front(i:integer);begin if # then begin write(); if ti.left0 then front(ti.left); if ti.right0 then front(ti.right);end;end;壽光現(xiàn)代中學(xué)中序遍歷中序遍歷的規(guī)則如下： 若二叉樹(shù)為空，則退出；否則 中序遍歷左子樹(shù)； 訪問(wèn)處理根結(jié)點(diǎn)； 中序遍歷右子樹(shù)；若中序遍歷上圖中的二叉樹(shù)，可以得到如下的中序序列： d b h

18、 e i a f c g 壽光現(xiàn)代中學(xué) procedure mid(i:integer);begin if # then begin if ti.left0 then mid(ti.left); write(); if ti.right0 then mid(ti.right); end;end;壽光現(xiàn)代中學(xué)后序遍歷后序遍歷的規(guī)則如下： 若二叉樹(shù)為空，則退出；否則 后序遍歷左子樹(shù)； 后序遍歷右子樹(shù)； 訪問(wèn)處理根結(jié)點(diǎn)； 若后序遍歷上圖中的二叉樹(shù)，可以得到如下的后序序列 d h i e b f g c a壽光現(xiàn)代中學(xué) procedure back(i:integer);b

19、egin if # then begin if ti.left0 then back(ti.left); if ti.right0 then back(ti.right); write(); end;end;壽光現(xiàn)代中學(xué)六、由二叉樹(shù)的兩種遍歷順序確定樹(shù)結(jié)構(gòu)遍歷二叉樹(shù)（如下圖）有三種規(guī)則： 前序遍歷：根左子樹(shù)右子樹(shù)； 中序遍歷：左子樹(shù)根右子樹(shù)； 后序遍歷：左子樹(shù)右子樹(shù)根；壽光現(xiàn)代中學(xué)【例題1】根據(jù)兩種遍歷順序確定樹(shù)結(jié)構(gòu)輸入：二叉樹(shù)的前序遍歷順序與中序遍歷順序輸出： 二叉樹(shù)的后序遍歷順序樣例：輸入：abcdefgcbdafeg輸出：cdbfgea壽光現(xiàn)代中學(xué)var sx

20、,sz:string; 算法procedure work(sx,sz:string);sx:先序序列; sz：中序序列 var l,k:integer; begin if sx then begin l:=length(sx); k:=pos(sx1,sz); 根在中序序列中的位置 work(copy(sx,2,k-1),copy(sz,1,k-1); 遞歸調(diào)用左子樹(shù) work(copy(sx,k+1,l-k),copy(sz,k+1,l-k); 遞歸調(diào)用右子樹(shù) write(sx1); 后序輸出根結(jié)點(diǎn) end; end;begin readln(sx); readln(sz); work(sx

21、,sz); writeln;end.壽光現(xiàn)代中學(xué)數(shù)據(jù)結(jié)構(gòu)圖壽光現(xiàn)代中學(xué)一、圖的基本概念二、圖的存儲(chǔ)結(jié)構(gòu)三、圖的遍歷壽光現(xiàn)代中學(xué) 圖是由一個(gè)頂點(diǎn)的集合V和一個(gè)頂點(diǎn)間關(guān)系的集合E組成： 記 G=（V，E） V：頂點(diǎn)的有限非空集合。 E：頂點(diǎn)間關(guān)系的有限集合（邊集）。 存在一個(gè)結(jié)點(diǎn)v，可能含有多個(gè)前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)。一、 圖的基本概念125341253412534圖2圖3圖1 1、圖的的定義壽光現(xiàn)代中學(xué)無(wú)向圖： 在圖G=（V，E）中，如果對(duì)于任意的頂點(diǎn)a，bV，當(dāng)(a，b)E時(shí)，必有（b，a）E（即關(guān)系R對(duì)稱），此圖稱為無(wú)向圖。無(wú)向圖中用不帶箭頭的邊表示頂點(diǎn)的關(guān)系 V=1, 2, 3, 4, 5 E

22、=(1, 2),(1, 3),(1, 4),(2,3),(2,5),(3, 5),(4,5) 125342、無(wú)向圖和有向圖壽光現(xiàn)代中學(xué)有向圖： 如果對(duì)于任意的頂點(diǎn)a，bV，當(dāng)(a，b)E時(shí) ，(b，a)E未必成立，則稱此圖為有向圖。在有向圖中，通常用帶箭頭的邊連接兩個(gè)有關(guān)聯(lián)的結(jié)點(diǎn)。V=1, 2, 3, 4,5 E= , , , , , 12534壽光現(xiàn)代中學(xué)在無(wú)向圖中：頂點(diǎn)v的度是指與頂點(diǎn)v相連的邊的數(shù)目D(v)。D(2)=33、頂點(diǎn)的度、入度和出度在有向圖中：入度以該頂點(diǎn)為終點(diǎn)的邊的數(shù)目和 . ID(3)=2 出度以該頂點(diǎn)為起點(diǎn)的邊的數(shù)目和 . OD(3)=1度數(shù)為奇數(shù)的頂點(diǎn)叫做奇點(diǎn)，度數(shù)為

23、偶數(shù)的點(diǎn)叫做偶點(diǎn)。度：等于該頂點(diǎn)的入度與出度之和。 D(5)=ID(5)+OD(5)=1+2=3 1253412534結(jié)論：圖中所有頂點(diǎn)的度=邊數(shù)的兩倍圖1:無(wú)向圖圖2：有向圖無(wú)向完全圖壽光現(xiàn)代中學(xué) 在圖G=（V，E）中，如果對(duì)于結(jié)點(diǎn)a，b，存在滿足下述條件的結(jié)點(diǎn)序列x1xk(k1) x1=a，xk=b (xi，xi+1)E i=1k-1則稱結(jié)點(diǎn)序列x1=a，x2，xk=b為結(jié)點(diǎn)a到結(jié)點(diǎn)b的一條路徑，而路徑上邊的數(shù)目（k-1）稱為該路徑的長(zhǎng)度。1253412534圖1圖2圖1: 1、(1,2,3,5) 長(zhǎng)度=3 2、(1,2,3,5,2) 長(zhǎng)度=4 3、(1,2,5,4,1) 長(zhǎng)度=4圖2:

24、(1,2,5,4) 長(zhǎng)度=3（1）、如果一條路徑上的結(jié)點(diǎn)除起點(diǎn)x1和終點(diǎn)xk可以相同外，其它結(jié)點(diǎn)均不相同，則稱此路徑為一條簡(jiǎn)單路徑。（2）、x1=xk的簡(jiǎn)單路徑稱為回路（也稱為環(huán)）4、路徑、簡(jiǎn)單路徑、回路壽光現(xiàn)代中學(xué)5、連通、連通圖、連通分量 (無(wú)向圖)連通：“連成一片”。連通圖：“能連成一片的圖”。1253412534678圖一：連通圖圖二：非連通圖定義：連通：如果存在一條從頂點(diǎn)u到v有路徑，則稱u和v是連通的。連通圖：圖中任意的兩個(gè)頂點(diǎn)u和v都是連通的，稱為連通圖。 否則稱為非連通圖。連通分量：無(wú)向圖中的極大連通子圖。圖二中有3個(gè)連通分量：1 2 4 5 3 6 7 8求連通分量數(shù)，最大連

25、通分量等。有向圖：強(qiáng)連通、強(qiáng)連通圖、強(qiáng)連通分量 壽光現(xiàn)代中學(xué)6、帶權(quán)圖 圖中的邊可以加上表示某種含義的數(shù)值，數(shù)值稱為邊的權(quán)，此圖稱為帶權(quán)圖。也稱為網(wǎng)。 一般的圖邊上沒(méi)有數(shù)字，邊僅表示兩個(gè)頂點(diǎn)的相連接關(guān)系。12534234213212534壽光現(xiàn)代中學(xué)二、圖的存儲(chǔ)結(jié)構(gòu)ABDCE12345頂點(diǎn)：數(shù)組或記錄邊：鄰接矩陣/鄰接表 G=( V,E )壽光現(xiàn)代中學(xué) 鄰接矩陣是表示結(jié)點(diǎn)間相鄰關(guān)系的矩陣。若G=（V，E）是一個(gè)具有n個(gè)結(jié)點(diǎn)的圖，則G的鄰接矩陣是如下定義的二維數(shù)組 a1.n,1.n。ai,j=1 (或權(quán)值)：無(wú)向圖：有邊( i , j )和邊( j , i ) 有向圖：有邊0: i 到 j 無(wú)邊

26、1、圖的鄰接矩陣表示法壽光現(xiàn)代中學(xué)125340 1 1 1 01 0 1 0 11 1 0 0 11 0 0 0 10 1 1 1 01 2 3 4 51 23451253423421320 2 2 3 02 0 1 0 32 1 0 0 23 0 0 0 40 3 2 4 01 2 3 4 51 2345125340 1 0 1 00 0 1 0 11 0 0 0 00 0 0 0 00 0 1 1 01 2 3 4 51 2345對(duì)角線為0：自身不相連。無(wú)向圖：是對(duì)稱矩陣。有向圖一般不是。第i行非0 的個(gè)數(shù)是結(jié)點(diǎn)i的度壽光現(xiàn)代中學(xué)具體到題目時(shí)，數(shù)據(jù)的給出格式多種多樣：1）、直接給出鄰接矩陣

27、，直接讀即可。如：輸入文件內(nèi)容：50 2 2 3 02 0 1 0 32 1 0 0 23 0 0 0 40 3 2 4 0maxn=100a:array1.maxn,1.maxn of integerfillchar(a,sizeof(a),0);readln(n);for i:=1 to n do for j:=1 to n do read(ai,j);125342342132壽光現(xiàn)代中學(xué)2）、給出邊的頂點(diǎn)。如輸入文件：兩個(gè)頂點(diǎn)及權(quán)值571 2 21 3 21 4 32 3 12 5 33 5 24 5 4125342342132readln(n); readln(m);for k:=1

28、to m do begin readln(i,j,x); ai,j:=x; aj,i:=x; end壽光現(xiàn)代中學(xué)62 3 63 4 5 63 1 4 63 2 3 53 2 4 64 1 2 3 51235463)、給出每個(gè)頂點(diǎn)的鄰接點(diǎn) readln(n); for i:=1 to n do begin read(k); for j:=1 to k do begin read(x); ai,x:=1;ax,i:=1; end; end;壽光現(xiàn)代中學(xué)125344無(wú)權(quán)圖:設(shè)置結(jié)點(diǎn)指針結(jié)點(diǎn)鄰接點(diǎn)指針2、鄰接表 :1234523413512515234鄰結(jié)點(diǎn)頭結(jié)點(diǎn)壽光現(xiàn)代中學(xué)type point=no

29、de; node=record v:integer; next:point; end;var a:array1.maxvof point;vnext readln(n1,n2); new(p); p.v:=n2; p.next:=an1; an1:=p; new(p); p.v:=n1; p.next:=an2; an2:=p;壽光現(xiàn)代中學(xué)125342342132123452232431231531221521354233244頭指針鄰接點(diǎn)指針結(jié)點(diǎn)鄰接點(diǎn)指針鄰接點(diǎn)邊權(quán)值下一個(gè)鄰接點(diǎn)指針有權(quán)圖：壽光現(xiàn)代中學(xué)type edge = node; node = record v: integer; w

30、eight : integer; next : edge; end; vpoint = record v: integer; link : edge; end;var a : array1.maxn of vpoint;vlinkvweightnext壽光現(xiàn)代中學(xué)鄰接矩陣和鄰接表的優(yōu)缺點(diǎn)：125340 1 1 1 01 0 1 0 11 1 0 0 11 0 0 0 10 1 1 1 01 2 3 4 51 23451234523413512515234鄰結(jié)點(diǎn)頭結(jié)點(diǎn)鄰接表鄰接矩陣壽光現(xiàn)代中學(xué)鄰接矩陣：代碼書(shū)寫(xiě)簡(jiǎn)單，找鄰接點(diǎn)慢鄰接表：代碼書(shū)寫(xiě)較復(fù)雜，找鄰接點(diǎn)快一般采用鄰接矩陣壽光現(xiàn)代中學(xué)1763

31、245980 1 0 0 0 0 0 0 01 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 10 0 0 0 0 0 1 0 00 0 0 0 0 1 0 0 00 0 0 0 0 0 0 0 00 0 0 0 1 0 0 0 01234521679鄰結(jié)點(diǎn)頭結(jié)點(diǎn)67895鄰接表鄰接矩陣壽光現(xiàn)代中學(xué)稀疏圖：邊表type node=record w:integer; /邊權(quán) u,v:integer; /兩個(gè)結(jié)點(diǎn) end;var e: array1.maxn*(maxn-1) div 2 of node; /邊壽光

32、現(xiàn)代中學(xué)三、圖的遍歷 給出一個(gè)圖G，從某一個(gè)初始點(diǎn)出發(fā)，按照一定的搜索方法對(duì)圖中的每一個(gè)結(jié)點(diǎn)訪問(wèn)僅且訪問(wèn)一次的過(guò)程。 訪問(wèn)結(jié)點(diǎn)：處理結(jié)點(diǎn)的過(guò)程。如輸出、查找結(jié)點(diǎn)的信息。 按照搜索方法的不同，通常有兩種遍歷方法： 1、深度優(yōu)先搜索dfs 2、廣度優(yōu)先搜索bfs 壽光現(xiàn)代中學(xué)1、深度優(yōu)先搜索DFS遍歷算法（遞歸過(guò)程）： 1)從某一初始出發(fā)點(diǎn)i開(kāi)始訪問(wèn)： 輸出該點(diǎn)編號(hào)；并對(duì)該點(diǎn)作被訪問(wèn)標(biāo)志（以免被重復(fù)訪問(wèn)）。 2)再?gòu)膇的其中一個(gè)未被訪問(wèn)的鄰接點(diǎn)j作為初始點(diǎn)出發(fā)繼續(xù)深搜。 當(dāng)i的所有鄰接點(diǎn)都被訪問(wèn)完，則退回到i的父結(jié)點(diǎn)的另一個(gè)鄰接點(diǎn)k再繼續(xù)深搜。直到全部結(jié)點(diǎn)訪問(wèn)完光現(xiàn)代中學(xué)

33、實(shí)現(xiàn):a1.maxn,1.maxn:邊的鄰接矩陣。1：有邊；0：無(wú)邊f(xié)1.maxn:boolean 標(biāo)記是否被訪問(wèn)過(guò)。 True: 已訪問(wèn)；flase：沒(méi)訪問(wèn)。初始值：false10121 41 51 64 8 5 34 35 76 27 102 93 77 2Procedure init; /初始化 begin readln(n); readln(m); for i:=1 to m do begin readln(x,y); ax,y:=1; ay,x:=1; end; end;壽光現(xiàn)代中學(xué)procedure dfs(k:integer);/從k點(diǎn)出發(fā)遍歷 var j:integer; /局

34、部變量？ begin write(k, ); fk:=true; for j:=1 to n do if (fj=false)and(ak,j=1) then dfs(j); end;上圖的遍歷結(jié)果：Dfs(1)?壽光現(xiàn)代中學(xué)主程序begin fillchar(f,sizeof(f),false); for i:=1 to n do if not fi then dfs(i);end;壽光現(xiàn)代中學(xué)求無(wú)向的連通分量 sum:=0; for i:=1 to n do if not fi then begin inc(sum); dfs(i); end; writeln(sum);12534678壽

35、光現(xiàn)代中學(xué)2、廣度優(yōu)先搜索(寬度優(yōu)先搜索）BFS 按層次遍歷： 從圖中某結(jié)點(diǎn)i出發(fā)，在訪問(wèn)了i之后依次訪問(wèn)i的各個(gè)未曾訪問(wèn)的鄰接點(diǎn)，然后分別從這些鄰接點(diǎn)出發(fā)按廣度優(yōu)先搜索的順序遍歷圖，直至圖中所有可被訪問(wèn)的結(jié)點(diǎn)都被訪問(wèn)到光現(xiàn)代中現(xiàn)： 隊(duì)列：q1.maxn f1.n:boolean: 判重headtail壽光現(xiàn)代中學(xué)procedure bfs(i:integer);/ bfs.pas var j,k:integer; begin fillchar(q,sizeof(q),0); head:=0; tail:=1; q1:=i; fi:=true

36、; while headtail do /隊(duì)列非空 begin inc(head); /出隊(duì) k:=qhead; write(k, ); for j:=1 to n do if (ak,j=1)and(fj=false) then begin inc(tail); /進(jìn)隊(duì) qtail:=j; fj:=true; end; end; end;壽光現(xiàn)代中學(xué)3、圖的遍歷的簡(jiǎn)單應(yīng)用1、犯罪團(tuán)伙【問(wèn)題描述】 警察抓到了n個(gè)罪犯，警察根據(jù)經(jīng)驗(yàn)知道他們屬于不同的犯罪團(tuán)伙，卻不能判斷有多少個(gè)團(tuán)伙，但通過(guò)警察的審訊，知道其中的一些罪犯之間相互認(rèn)識(shí)，已知同一犯罪團(tuán)伙的成員之間直接或間接認(rèn)識(shí)，有可能一個(gè)犯罪團(tuán)伙只有一個(gè)人。請(qǐng)你根據(jù)已知罪犯之間的關(guān)系，確定犯罪團(tuán)伙的數(shù)量。已知罪犯的編號(hào)從1至n?！据斎搿?第一行：n（1000,罪犯數(shù)量）。 第二行：m（5000，關(guān)系數(shù)量）。 以下m行，每行兩個(gè)數(shù)：i 和j，中間一個(gè)空格隔開(kāi)，表示罪犯i和罪犯j相互認(rèn)識(shí)?！据敵觥?一個(gè)整數(shù)，犯罪團(tuán)伙的數(shù)量。壽光現(xiàn)代中學(xué)【樣例輸入】118 1 24 53 41 35 67 105 108 9【樣例輸出】 3樣例說(shuō)明：共三個(gè)集團(tuán)。壽光現(xiàn)代中學(xué)把n個(gè)人看成圖的n個(gè)頂點(diǎn)；相互認(rèn)識(shí)的連一無(wú)向條邊。相互認(rèn)識(shí)的所有人構(gòu)成一個(gè)極大連通子圖。問(wèn)題轉(zhuǎn)化為：求無(wú)向圖的連通分量 （有多少個(gè)極大