pascal第十二講樹與圖的簡介

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

2、【樣例1】 輸入：abcabbmaa 輸出：yes【樣例2】 輸入：abcabbmaa 輸出：no壽光現(xiàn)代中學(xué)從字符串中讀入一個左括號時，就將其壓入棧s中；當(dāng)讀入一個右括號時,就從棧頂取出左括號檢查比較,看是否匹配,如果匹配,就將左括號出棧;否則顯示不匹配。全部字符串讀完后,最后檢查棧是否為空,如果不空,左括號無右括號與之匹配,顯示不匹配?！締栴}分析】壽光現(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ì)胞個數(shù)。輸入：整數(shù)m,n(m行，n列) （1=m=80,1=n0) and (x0) and (yw;直至隊空為止 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)樹壽光現(xiàn)代中學(xué) 棧、隊列屬于線性結(jié)構(gòu)。在這種結(jié)構(gòu)中，不管其存儲方式（順序和鏈?zhǔn)剑┤绾危瑪?shù)據(jù)元素的邏輯位置之間呈線性關(guān)系，即每一個數(shù)據(jù)元素通常只有一個前驅(qū)（除第一個元素外）和一個后繼（除最后一個元素外）。 但也有很多問題數(shù)據(jù)元素間的邏輯關(guān)系不能用線性結(jié)構(gòu)明確、方便地描述出來。一般來說，至少存在一個

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

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

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

9、隔開，最后用閉括號括起來。例如圖可寫成如下形式（r（a（w，x（d（h），e），b（f），c（s，t（i（m，o，n），j），u）壽光現(xiàn)代中學(xué) 2、樹的存儲結(jié)構(gòu)樹的存儲結(jié)構(gòu)一般有兩種靜態(tài)的記錄數(shù)組。所有結(jié)點(diǎn)存儲在一個數(shù)組中，數(shù)組元素為記錄類型，包括數(shù)據(jù)域和長度為n(n 為樹的度)的數(shù)組，分別存儲該結(jié)點(diǎn)的每一個兒子的下標(biāo)Const n=樹的度；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ù)組壽光現(xiàn)代中學(xué)例如圖的樹，其記錄數(shù)組如下。由于未規(guī)定同層結(jié)點(diǎn)的次序，因此每個結(jié)點(diǎn)兒子的下標(biāo)序列（Treei.ch）任意。其中Treei.chj=0說明結(jié)點(diǎn)i的第j個兒子不存在。(編號按層編號)壽光現(xiàn)代中學(xué) 三、二叉樹的概念 二叉樹是一種很重要的非線性數(shù)據(jù)結(jié)構(gòu)，它的特點(diǎn)是每個結(jié)點(diǎn)最多有兩個孩子，且其子樹有左右之分（有序樹，次序不能任意顛倒）。1、二叉樹的遞歸定義和基本形態(tài) 二叉樹是以結(jié)點(diǎn)為元素的有限集，它或者為空，或者滿足以下條件：有一個特定的結(jié)點(diǎn)稱為根；余下的結(jié)點(diǎn)分為互不相交的子集L和R，其中L是根的左子樹；R是根的右子樹；L和R又是二叉樹；？ 二叉樹是不是樹？二叉樹樹？壽

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

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

13、2k-1=2k-1（等比數(shù)列求和乘2做減法）壽光現(xiàn)代中學(xué)性質(zhì)3：在任何二叉樹中，葉子結(jié)點(diǎn)數(shù)總比度為2的結(jié)點(diǎn)多1。n0=n2+1設(shè)n0為二叉樹的葉結(jié)點(diǎn)數(shù)；n1為二叉樹中度為1的結(jié)點(diǎn)數(shù)；n2為二叉樹中度為2的結(jié)點(diǎn)數(shù)，顯然所有結(jié)點(diǎn)數(shù)目 n=n0+n1+n2 （1）所有這些分支同時又為度為1和度為2的結(jié)點(diǎn)發(fā)出的。再加上根結(jié)點(diǎn)，因此又有 n=1+n1+2n2 (2)由上兩個等式求得：n0=1+n2壽光現(xiàn)代中學(xué)例題：如果一棵m度的樹中有N1個度為1的頂點(diǎn)，N2個度為2的頂點(diǎn)，N3個度為3的頂點(diǎn)，Nm個度為m的頂點(diǎn)，求該樹中葉子頂點(diǎn)個數(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é)四、二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)有兩種形式順序存儲結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)壽光現(xiàn)代中學(xué)1、順序存儲結(jié)構(gòu)將每個結(jié)點(diǎn)依次存放在一維數(shù)組中，用數(shù)組下標(biāo)指示結(jié)點(diǎn)編號，編號的方法是從根結(jié)點(diǎn)開始編號1，然后由左而右進(jìn)行連續(xù)編號。每個結(jié)點(diǎn)的信息包括一個數(shù)據(jù)域（data）；三個指針域，其中有父結(jié)點(diǎn)編號（prt）、左兒子結(jié)點(diǎn)編號（lch）和右兒子結(jié)點(diǎn)編號（rch）。滿二叉樹和完全二叉樹一般采用順序存儲結(jié)構(gòu) C

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

16、R、 LRD這三種遍歷規(guī)則分別稱為先（前）序遍歷、中序遍歷和后序遍歷（以根為標(biāo)準(zhǔn)）。二叉樹的存儲采用動態(tài)的二重鏈表形式。壽光現(xiàn)代中學(xué)為了方便敘述，我們以下圖為例解釋三種遍歷規(guī)則，我們在寫遍歷子過程前先定義樹結(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ī)則如下：若二叉樹

17、為空，則退出。否則 訪問處理根結(jié)點(diǎn)； 前序遍歷左子樹； 前序遍歷右子樹； 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ī)則如下： 若二叉樹為空，則退出；否則 中序遍歷左子樹； 訪問處理根結(jié)點(diǎn)； 中序遍歷右子樹；若中序遍歷上圖中的二叉樹，可以得到如下的中序序列： 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ī)則如下： 若二叉樹為空，則退出；否則 后序遍歷左子樹； 后序遍歷右子樹； 訪問處理根結(jié)點(diǎn)； 若后序遍歷上圖中的二叉樹，可以得到如下的后序序列 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é)六、由二叉樹的兩種遍歷順序確定樹結(jié)構(gòu)遍歷二叉樹（如下圖）有三種規(guī)則： 前序遍歷：根左子樹右子樹； 中序遍歷：左子樹根右子樹； 后序遍歷：左子樹右子樹根；壽光現(xiàn)代中學(xué)【例題1】根據(jù)兩種遍歷順序確定樹結(jié)構(gòu)輸入：二叉樹的前序遍歷順序與中序遍歷順序輸出： 二叉樹的后序遍歷順序樣例：輸入：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)用左子樹 work(copy(sx,k+1,l-k),copy(sz,k+1,l-k); 遞歸調(diào)用右子樹 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é)一、圖的基本概念二、圖的存儲結(jié)構(gòu)三、圖的遍歷壽光現(xiàn)代中學(xué) 圖是由一個頂點(diǎn)的集合V和一個頂點(diǎn)間關(guān)系的集合E組成： 記 G=（V，E） V：頂點(diǎn)的有限非空集合。 E：頂點(diǎn)間關(guān)系的有限集合（邊集）。 存在一個結(jié)點(diǎn)v，可能含有多個前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)。一、 圖的基本概念125341253412534圖2圖3圖1 1、圖的的定義壽光現(xiàn)代中學(xué)無向圖： 在圖G=（V，E）中，如果對于任意的頂點(diǎn)a，bV，當(dāng)(a，b)E時，必有（b，a）E（即關(guān)系R對稱），此圖稱為無向圖。無向圖中用不帶箭頭的邊表示頂點(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、無向圖和有向圖壽光現(xiàn)代中學(xué)有向圖： 如果對于任意的頂點(diǎn)a，bV，當(dāng)(a，b)E時 ，(b，a)E未必成立，則稱此圖為有向圖。在有向圖中，通常用帶箭頭的邊連接兩個有關(guān)聯(lián)的結(jié)點(diǎn)。V=1, 2, 3, 4,5 E= , , , , , 12534壽光現(xiàn)代中學(xué)在無向圖中：頂點(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:無向圖圖2：有向圖無向完全圖壽光現(xiàn)代中學(xué) 在圖G=（V，E）中，如果對于結(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）稱為該路徑的長度。1253412534圖1圖2圖1: 1、(1,2,3,5) 長度=3 2、(1,2,3,5,2) 長度=4 3、(1,2,5,4,1) 長度=4圖2:

24、(1,2,5,4) 長度=3（1）、如果一條路徑上的結(jié)點(diǎn)除起點(diǎn)x1和終點(diǎn)xk可以相同外，其它結(jié)點(diǎn)均不相同，則稱此路徑為一條簡單路徑。（2）、x1=xk的簡單路徑稱為回路（也稱為環(huán)）4、路徑、簡單路徑、回路壽光現(xiàn)代中學(xué)5、連通、連通圖、連通分量 (無向圖)連通：“連成一片”。連通圖：“能連成一片的圖”。1253412534678圖一：連通圖圖二：非連通圖定義：連通：如果存在一條從頂點(diǎn)u到v有路徑，則稱u和v是連通的。連通圖：圖中任意的兩個頂點(diǎn)u和v都是連通的，稱為連通圖。 否則稱為非連通圖。連通分量：無向圖中的極大連通子圖。圖二中有3個連通分量：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)。 一般的圖邊上沒有數(shù)字，邊僅表示兩個頂點(diǎn)的相連接關(guān)系。12534234213212534壽光現(xiàn)代中學(xué)二、圖的存儲結(jié)構(gòu)ABDCE12345頂點(diǎn)：數(shù)組或記錄邊：鄰接矩陣/鄰接表 G=( V,E )壽光現(xiàn)代中學(xué) 鄰接矩陣是表示結(jié)點(diǎn)間相鄰關(guān)系的矩陣。若G=（V，E）是一個具有n個結(jié)點(diǎn)的圖，則G的鄰接矩陣是如下定義的二維數(shù)組 a1.n,1.n。ai,j=1 (或權(quán)值)：無向圖：有邊( i , j )和邊( j , i ) 有向圖：有邊0: i 到 j 無邊

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對角線為0：自身不相連。無向圖：是對稱矩陣。有向圖一般不是。第i行非0 的個數(shù)是結(jié)點(diǎn)i的度壽光現(xiàn)代中學(xué)具體到題目時，數(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)。如輸入文件：兩個頂點(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)、給出每個頂點(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無權(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)值下一個鄰接點(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é)鄰接矩陣：代碼書寫簡單，找鄰接點(diǎn)慢鄰接表：代碼書寫較復(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; /兩個結(jié)點(diǎn) end;var e: array1.maxn*(maxn-1) div 2 of node; /邊壽光

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

33、實現(xiàn):a1.maxn,1.maxn:邊的鄰接矩陣。1：有邊；0：無邊f(xié)1.maxn:boolean 標(biāo)記是否被訪問過。 True: 已訪問；flase：沒訪問。初始值：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é)求無向的連通分量 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ā)，在訪問了i之后依次訪問i的各個未曾訪問的鄰接點(diǎn)，然后分別從這些鄰接點(diǎn)出發(fā)按廣度優(yōu)先搜索的順序遍歷圖，直至圖中所有可被訪問的結(jié)點(diǎn)都被訪問到光現(xiàn)代中現(xiàn)： 隊列：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 /隊列非空 begin inc(head); /出隊 k:=qhead; write(k, ); for j:=1 to n do if (ak,j=1)and(fj=false) then begin inc(tail); /進(jìn)隊 qtail:=j; fj:=true; end; end; end;壽光現(xiàn)代中學(xué)3、圖的遍歷的簡單應(yīng)用1、犯罪團(tuán)伙【問題描述】 警察抓到了n個罪犯，警察根據(jù)經(jīng)驗知道他們屬于不同的犯罪團(tuán)伙，卻不能判斷有多少個團(tuán)伙，但通過警察的審訊，知道其中的一些罪犯之間相互認(rèn)識，已知同一犯罪團(tuán)伙的成員之間直接或間接認(rèn)識，有可能一個犯罪團(tuán)伙只有一個人。請你根據(jù)已知罪犯之間的關(guān)系，確定犯罪團(tuán)伙的數(shù)量。已知罪犯的編號從1至n?！据斎搿?第一行：n（1000,罪犯數(shù)量）。 第二行：m（5000，關(guān)系數(shù)量）。 以下m行，每行兩個數(shù)：i 和j，中間一個空格隔開，表示罪犯i和罪犯j相互認(rèn)識?！据敵觥?一個整數(shù)，犯罪團(tuán)伙的數(shù)量。壽光現(xiàn)代中學(xué)【樣例輸入】118 1 24 53 41 35 67 105 108 9【樣例輸出】 3樣例說明：共三個集團(tuán)。壽光現(xiàn)代中學(xué)把n個人看成圖的n個頂點(diǎn)；相互認(rèn)識的連一無向條邊。相互認(rèn)識的所有人構(gòu)成一個極大連通子圖。問題轉(zhuǎn)化為：求無向圖的連通分量 （有多少個極大