簡單的數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)為了編寫一個“好”的程序，必須分析待處理的對象特性以及各處理對象之間存在的關(guān)系.這就需要學(xué)習(xí)“數(shù)據(jù)結(jié)構(gòu)”。因此，簡單地說來，數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機(jī)的操作對象以及它們之間的關(guān)系和操作等等的學(xué)科。在信息學(xué)奧賽中需要學(xué)習(xí)線性表、樹、圖三種數(shù)據(jù)結(jié)構(gòu)，在后面我們將一一介紹.4.1棧線性表是最常用且比較簡單的一種數(shù)據(jù)結(jié)構(gòu)，它是由有限個數(shù)據(jù)元素組成的有序集合，每個數(shù)據(jù)元素有一個數(shù)據(jù)項或者含多個數(shù)據(jù)項.例如我們前面所學(xué)過的數(shù)組是線性的數(shù)據(jù)結(jié)構(gòu).下面介紹的棧是一種線性表，但是對它的插人和刪除等操作都限制在表的同一端進(jìn)行，即棧頂，而另一端則稱為是棧底.打個形象地比喻，用桶堆積物品，先堆進(jìn)來的壓在底下，隨后一件一件往上堆.取走時，只能從上面一件一件取.堆和取都在頂部進(jìn)行，底部一般是不動的.所以，棧也稱為后進(jìn)先出表（LIFO表）.通常?？梢杂庙樞虻姆绞酱鎯?，分配一塊連續(xù)的存儲區(qū)域來存放棧中的數(shù)據(jù)項，即用定長為N的數(shù)組S來表示，并用一個變量TOP指向當(dāng)前棧頂（如圖4-1-1）.若TOP=0，表示?？眨琓0P=N時棧滿.我們一般把插人操作稱為進(jìn)棧（PUSH），此時TOP加1，刪除操作則稱為出棧（POP），則TOP減1.當(dāng)TOP<0時為下溢.用Pascal語言來模擬棧的定義和操作.1棧的定義：CONSTN棧數(shù)據(jù)項的上限TYPEstack=array[1..n]ofstype；{styp代表數(shù)據(jù)項類型}VARs：stack；2進(jìn)棧過程push（s，x，top）——往棧S中壓人一個值為X的數(shù)據(jù)項procedurepush(vars:stack；x：stype；vartop：integer)；BEGINiftop=0thenwrite’underflow’)else

BEGINBEGINtop:=top+1s[top]:=xENDEND出棧函數(shù)pop(s,top)——從棧中彈出一個數(shù)據(jù)項functionpop(vars：stack；vartop：integer):stype；BEGINiftop=0thenwriteln(’underflow’)elseBEGINpop:=s[top；top:=top-1ENDEND讀數(shù)函數(shù)stop(s,top)——讀棧頂?shù)臄?shù)據(jù)項functionstop(vars:stackt：integer)：stypeBEGINiftop=0thenwriteln(’stackempty’)elsestop:=s[top；END棧的用途極為廣泛，在源程序編譯中表達(dá)式的計算、過程的嵌套調(diào)用和遞歸調(diào)用等都要用到棧.從歷屆初賽可以看出，棧也是屬于比較容易出題的知識點，選擇題、解答題等題型都有可能出現(xiàn).例、設(shè)輸入元素為1、2、3、P和A，輸人次序為123PA，如圖4.1.2所示，元素經(jīng)過棧后到達(dá)輸出序列，當(dāng)所有元素均到達(dá)輸出序列后，有哪些序列可以作為高級語言的變量名？高級語言變量名的定義規(guī)則：以字母開頭，字母與數(shù)字的組合.由于必須以字母開頭，所以，第一個可能出現(xiàn)的字母是P，那么必然要求123已經(jīng)先后入棧，這樣便可得到以P開頭的、并且123按逆序排列的(即321)、同時A位于P后任一位置的變量名序列.此外，還需要考慮以A開頭的可能情況，這只有一種情形:AP321.所以AP321，PA321，P3A21，P32A1，P321A可以作為高級語言的變量名.例、 中綴表達(dá)式A-（B+C/D）*E的后綴形式是什么？中綴形式：即一般情況下的表達(dá)方式，將運(yùn)算符寫于參與運(yùn)算的操作數(shù)的中間，操作數(shù)依原序列排。后綴形式：式中不再引人括號，運(yùn)算符放在參與運(yùn)算的操作數(shù)之后，操作數(shù)的排列依原序列，所有計算按運(yùn)算符出現(xiàn)的順序，嚴(yán)格地由左而右進(jìn)行（不再考慮運(yùn)算符的優(yōu)先規(guī)則）.所以利用椎棧的特性，可以得出本題的答案是ABCD/+E*-。前綴表達(dá)式：同后綴表達(dá)式一樣，不包含括號，運(yùn)算符放在兩個運(yùn)算對象的前，如一A*+B/CDE?！揪毩?xí)題】單項選擇題1、 設(shè)棧S的初始狀態(tài)為空，元素a，b，c，d，e，f依次入棧，出棧順序為b，d，c，f，e，a那么棧容量至少應(yīng)該是（ ）。A.6 B.5 C.4 D.3 E.22、 一個棧的入棧序列為a，b，c，d，e，則棧的不可能輸出序列為（）A、edcba B、decbaC、dceabD、abcde3.設(shè)棧的輸人序列為1、2、3、 、n，輸出序列為al、a2、 、an，若存在1<=k<=n使得ak=n，則當(dāng)k<=i<=n時，ai為（）.A.n-i+1 B.n-（i-k） C不確定4、 設(shè)棧的輸入序列是（1、2、3、4），則（）不可能是其出棧序列.A.1243 B.2134C.1432 D.4312E.32145、 已知一算術(shù)表達(dá)式的中綴形式為A+B*C—D/E，其后綴形式為ABC*+DE/一，其前綴形式為（）.A.-A+B*C/DEB.-A+B*CD/EC.-+*ABC/DED.-+A*BC/DE6、 設(shè)棧的輸入序列是1、2、…、n，若輸出序列的第一個元素是n，則第i個輸出元素是（）入不確定 B.n-i+lC.i D.n-i4.2隊列隊列是限定在一端進(jìn)行插入，另一端進(jìn)行刪除的特殊線性表。正像排隊買東西，排在前面人買完東西后離開隊伍（刪除），而后來的人總是排在隊伍末尾（插入）.通常把隊列的刪除和插分別稱為出隊和人隊.允許出隊的一端稱為隊首，允許人隊的一端稱為隊尾.所有需要進(jìn)隊數(shù)據(jù)項，只能從隊尾進(jìn)人，隊列中的數(shù)據(jù)項只能從隊首離去.由于總是先入隊的元素先出隊（排隊的人先買完東西），這種

表也稱為“先進(jìn)先出"(FIFO)表.隊列可以用數(shù)組Q[1?m]來存儲，數(shù)組的上界m即是隊列所容許的最大容量.在隊列的算中需設(shè)兩個指針：head隊首指針，指向?qū)嶋H隊頭元素的前一個位置tail隊尾指針，指向?qū)嶋H隊尾元素所在的位置隊列中擁有的元素個數(shù)為：L=tail—head.一般情況下，兩個指針的初值設(shè)為O,這時隊列為空，沒有元素.用Pascal用Pascal語言模擬隊列的定義和操作.1.隊列的定義CONSTm耿列元素的上限;TYPE｛隊列的類型定義｝equeue=array[1..m]ofqtype；｛隊列的類型定義｝VARq：equeue；headtail：integer；2.人隊過程add(q，x，taxi)｛隊列｝｛隊首指針與隊尾指針｝在隊列的尾端插入元素xprocedureadd(varq：equeue；x：qtype；vattail：integer)；BEGIN｛隊列滿上溢｝iftail：mthenwriteln(’overflow’)｛隊列滿上溢｝elseBEGINtail:=tail+l；q[tail]:=x；ENDEND；3.出隊過程del(q，y，head，tail) 取出q隊列的隊首元素Yproceduredel(varqequeue；Vary：qtype；Varhead，tail：integer)；BEGINifhead=tailthenwriteln(’underflow’) ｛歹0表空下溢｝elseBEGINhead:=head+1;y:=q[head];ENDEND對循環(huán)隊列的操作要區(qū)別于一般隊列：初始時隊列空，隊首指針和隊尾指針均指向存儲空間的最后一個位置，即head=tail：m.TOC\o"1-5"\h\z入隊運(yùn)算時，尾指針進(jìn)一，即 -[tail:=tail+l；iftail=m+1thentail:=1這兩條語句可用一條語句替代：tail:=tailmodm+1 '■ ■-出隊運(yùn)算時，首指針進(jìn)一，即 "-I-head:=head+1；ifhead=m+1thenhead:=1這兩條語句可用一條語句替代：head:=headmodm+1隊列空時，head=tail隊列滿時，head=tailmodm+1為了區(qū)分隊列空和隊列滿，改用“隊尾指針追上隊首指針’’這一特征作為隊列滿標(biāo)志.這種處理方法的缺點是浪費(fèi)隊列空間的一個存儲單元.所以，我們重新得到另外兩種循環(huán)隊列的運(yùn)算.1.人隊過程add(q，x，taxi) 在隊列的尾端插入元素xprocedureadd(vatq：equeue；x：qtype；vartajl：integer)；VARt：integer；BEGINt:=tailmodm+1；ift=headthenwriteln('full')elseBEGINtai：l=t；q[tail]:=xENDEND2.出隊過程del（q，y，head，tail） 取出q隊列的隊首元素yproceduredel（varq：equeue；vary：qtype；varhead：integer）；BEGINifhead二tailwriteln（'empty’）elseBEGINhead:=headmodm+1y:=q[head]；ENDEND【練習(xí)題】單項選擇題：1.若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當(dāng)一和front的值分別為0和3。當(dāng)從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別為多少？A.1和5 B.邪4TOC\o"1-5"\h\zC.4和2 D.和12.設(shè)棧S和隊列Q的初始狀態(tài)為空，元素e1、e2、e3、e4、e5和e6依次通過棧S，一個元素出棧后即進(jìn)入隊列Q，若6個元素出隊的序列是e2、e4、e3、e6、e5、e1，則棧S的容量至少應(yīng)該是（）.A.6 B.4C.3 D.23.如右圖所示的循環(huán)隊列中元素數(shù)目是（）.其中仙* :、'tail=32指向隊尾元素，head=15指向隊首元素的前 /一個空位置，隊列空間m=60.A.42 B.16C.17 D.414.3樹前兩節(jié)學(xué)習(xí)的棧和隊列屬于線性結(jié)構(gòu).在這種結(jié)構(gòu)中，數(shù)據(jù)元素的邏輯位置之間呈線性關(guān)系，每一個數(shù)據(jù)元素通常只有一個前件（除第一個元素外）和一個后件（除最后一個元素外）.在實際生活中，可以用線性結(jié)構(gòu)描述數(shù)據(jù)元素之間邏輯關(guān)系的問題是很廣泛的，但也有很多問題不能依靠線性結(jié)構(gòu)來解決，例如家譜、行政組織機(jī)構(gòu)等都是非線性的數(shù)據(jù)結(jié)構(gòu).其中樹就是一種非線性的數(shù)據(jù)結(jié)構(gòu).一）樹的遞歸定義為樹（Tree）是n（n、O）個結(jié)點的有限集T，T為空時稱為空樹，否則它滿足如下兩個條件：（1有且僅有一個特定的稱為根（Root）的結(jié)點；

（2其余的結(jié)點可分為m（m》0）個互不相交的子集，T1,T2,…，Tm,其中每個子集本身又是一棵樹，并稱其為根的子樹（Subtree）.比如在現(xiàn)實生活中，有如下血統(tǒng)關(guān)系的家族可用樹形圖（圖4-3-1）表示：張源有三個孩子張明、張亮和張麗；張明有兩個孩子張林和張維；張亮有三個孩子張平和張群；張麗有兩個孩子張晶和張磊.以上表示很像一棵倒畫的樹.其中“樹根”是張源，樹的“分支點”是張明、張亮和張平，該家族的其余成員均是“樹葉”，而樹枝（即圖中的線段）則描述了家族成員之間的關(guān)系.顯然，以張源為根的樹是一個大家庭.它可以分成張明、張亮和張麗為根的三個小家庭；每個小家庭又都是一個樹形結(jié)構(gòu).以下介紹幾個關(guān)于樹的基本概念.度.一個結(jié)點的子樹數(shù)目稱為該結(jié)點的度.所有結(jié)點中最大的度稱為該樹的度.如圖4-3-2,結(jié)點i的度為3,結(jié)點t的度為2，結(jié)點b的度為1.顯然，所有樹葉的度為0，該樹的度為3.2.樹的層次和高度.樹是分層次的，結(jié)點所在的層次是從根算起的，根節(jié)點在第一層，根的后件在第二層，其余各層依此類推.樹中最大的層次稱為樹的深度，亦稱高度.如圖中，樹共有5層，樹的高度為5.3.森林.若十棵互不相交的樹的集合。如圖去掉根結(jié)點r,其原來的三棵子樹的集合即為森林。（二）二叉樹二叉樹（BinaryTree）是樹形結(jié)構(gòu)的一個重要類型.許多實際問題抽象出來的數(shù)據(jù)結(jié)構(gòu)往往是二叉樹的形式，即使是一般的樹也能簡單地轉(zhuǎn)換為二叉樹，而且二又樹的存儲結(jié)構(gòu)及其算法都較為簡單，因此二又樹顯得特別重要.但是值得特別注意的是：二叉樹并非是樹的特殊情形，它們是兩種不同的數(shù)據(jù)結(jié)構(gòu).下面給出二叉樹的遞歸定義：二叉樹是n（n>0）個結(jié)點的有限集，它或者是空集（n=0），或者由一個根結(jié)點及兩棵互不相交的、分別稱作這個根的左子樹和右子樹的二叉樹組成.二叉樹的五種基本形態(tài)如圖4-3-3所示.二叉樹具有以下重要性質(zhì)：性質(zhì)1二叉樹第i層上的結(jié)點數(shù)目最多為2i-i(iNl):性質(zhì)2深度為k的二叉樹至多有2k-1個結(jié)點(k\1).，性質(zhì)3在任意一棵二叉樹中，若終端結(jié)點的個數(shù)為n0,度為2的結(jié)點數(shù)為n2,

則n0=n2+1.例、有n個結(jié)點的二叉樹，已知葉結(jié)點個數(shù)為n0,寫出求度為1的結(jié)點的個數(shù)nl的計算公式；若此樹是深度為k的完全二叉樹，寫出n為最小的公式；若二叉樹中僅有度為0和度為2的結(jié)點，寫出求該二叉樹結(jié)點個數(shù)n的公式.(1祀度為2的結(jié)點個數(shù)為n2，則n=n0+n1+n2 ①又因為除了根結(jié)點以外，其余結(jié)點均由父結(jié)點射出，所以n=l+nl+2②12由①②兩式得n1=n+1-2n0當(dāng)樹是深度為k的完全二叉樹時，n的最小值n.=2k-1min當(dāng)二叉樹中僅有度為0和度為2的結(jié)點時，n=n0+n2.n=2n2+1所以：n0=n2+1n=2n0-1滿二叉樹和完全二叉樹是二叉樹的兩種特殊情形.1.滿二叉樹(FullBinaryuTree)一棵深度為k且有2k-1個結(jié)點的二叉樹稱為滿二叉樹.滿二叉樹的特點：每一層上的結(jié)點數(shù)都達(dá)到最大值.即對給定的高度，它是具有最多結(jié)點數(shù)的二叉樹.滿二叉樹中不存在度數(shù)為1的結(jié)點，每個分支結(jié)點均有兩棵高度相同的子樹，且樹葉都在最下一層上.可以驗證具有n個葉結(jié)點的滿二叉樹共有2n-1個結(jié)點.如圖(a)是一個深度為4的滿二叉樹.2.完全二叉樹(CompleteBinaryTree)若一棵二叉樹至多只有最下面的兩層上結(jié)點的度數(shù)可以小于2,并且最下一層上的結(jié)點都集中在該層最左邊的若干位置上，則此二叉樹稱為完全二叉樹.特點：滿二叉樹是完全二叉樹，完全二叉樹不一定是滿二叉樹.在滿二叉樹的最下一層上，從最右邊開始連續(xù)刪去若干結(jié)點后得到的二叉樹仍然是一棵完全二叉樹.在完全二又樹中，若某個結(jié)點沒有左孩子，則它一定沒有右孩子，即該結(jié)點必是葉結(jié)點.如圖(b)是一棵完全二叉樹.0)滿二叉樹 .(b)完全二又樹，性質(zhì)4 具有n個結(jié)點的完全二叉樹的深度為[lgn或11g(n+1)]證明：設(shè)所求完全二叉樹的深度為k.由完全二叉樹定義可得：深度為k得完全二叉樹的前k—l層是深度為k一1的滿二叉樹，一共有2k-1-1個結(jié)點.由于完全二叉樹深度為k，故第k層上還有若干個結(jié)點，因此該完全二叉樹的結(jié)點個數(shù)：n>2k-1-1.另一方面，由性質(zhì)2可得：n^2k一'1，艮即 k-1-2<n^2k一'1由此可推出：2k-1^n<2k，取對數(shù)后有：k-1^lgn<k又因k一1和k是相鄰的兩個整數(shù)，故有k-1=[lgn]，由此即得：k=[lgn]+l例、 已知一棵完全二叉樹共有892個結(jié)點，試求：(1)樹的高度(2)葉子結(jié)點數(shù)(3)單支結(jié)點數(shù)(4)最后一個非終端結(jié)點的序號【解答】(1)已知深度為k的二叉樹至多有2k-1個結(jié)點(kN1)，由于29-l<892<210-1所以樹的高度為l0.(2對完全二叉樹來說，度為1的結(jié)點只能是0或1.由n=n0+nl+n2和n0=n2++1設(shè)nl=0，則有：892=n0+0+n2=n2+1+n2=2n2+1，因得到的n2不為整數(shù)而出錯；設(shè)n1=1，則有：892：n0+1+n2：n2+l+1+n2=2n2+2，得到0n2=445，代入n0=n2+1則最后得到n0=446，故葉子結(jié)點數(shù)為446.由(2)可知單支結(jié)點數(shù)為1.對有n個結(jié)點的完全二又樹，最后一個樹葉結(jié)點，即序號為n的葉結(jié)點其雙親結(jié)點n/2，即為最后一個非終端結(jié)點，也即序號為向下取整(892/2)=446.此外，由(2)可知:n2=44，n1=1；則最后一個非終端結(jié)點的序號為：445+1=446。(三)二叉樹的遍歷所謂遍歷(Traversal)是指沿著某條搜索路線，依次對樹中每個結(jié)點均做一次訪問。訪問結(jié)點所做的操作依賴具體的應(yīng)用問題。遍歷是二叉樹上最重要的運(yùn)算之一，是二叉樹上進(jìn)行其它運(yùn)算之基礎(chǔ).1遍歷方案從二叉樹的遞歸定義可知，一棵非空的二叉樹由根結(jié)點及左、右子樹這三個基本部分組成.因此，在任一給定結(jié)點上，可以按某種次序執(zhí)行三個操作：(1訪問結(jié)點本身(N);遍歷該結(jié)點的左子樹(L)；遍歷該結(jié)點的右子樹(R).以上三種操作有六種執(zhí)行次序：NLRLNR、LRN、NRL、RNL、RLN.注意：前三種次序與后三種次序?qū)ΨQ，故只討論先左后右的前三種次序.2三種遍歷的命名根據(jù)訪問結(jié)點操作發(fā)生位置命名：NLR：前序遍歷(PreorderTraversal亦稱(先序遍歷))——訪問結(jié)點的操作發(fā)生在遍歷其左右子樹之前.LNR：中序遍歷(InorderTraversal)——訪問結(jié)點的操作發(fā)生在遍歷其左右子樹之中(間).LRN：后序遍歷(PostorderTraversal)——訪問結(jié)點的操作發(fā)生在遍歷其左右子樹之后.由于被訪問的結(jié)點必是某子樹的根，所以N(Node)、L(Leftsubtree)和R(Rightsubtree)又可解釋為根、根的左子樹和根的右子樹.NLR、LNR和LRN分別又稱為先根遍歷、中根遍歷和后根遍歷.

3.遍歷算法.為了敘述方便，我們以如下圖為例解釋三種遍歷的方法.①中序遍歷的遞歸算法定義：若二叉樹非空，則依次執(zhí)行如下操作：遍歷左子樹;訪問根結(jié)點；遍歷右子樹.按照以上算法，可以得到圖中二叉樹的中序序列為dbheiafcg.先序遍歷的遞歸算法定義：若二叉樹非空，則依次執(zhí)行如下操作：訪問根結(jié)點；遍歷左子樹；遍歷右子樹.如上例中二又樹可以得到前序序列為abdehicfg.后序遍歷得遞歸算法定義：若二叉樹非空，則依次執(zhí)行如下操作：遍歷左子樹；遍歷右子樹；訪問根結(jié)點.如上例中二叉樹可以得到后序序列為dhiebfgca.例、有二叉樹中序序列為ABCEFGHD，后序序列為：ABFHGEDC.請畫出此二叉樹，并求前序序列.根據(jù)后序序列知根節(jié)點為C因此左子樹：中序序列為AB后序序列為AB右子樹：中序序列為EFGHD后序序列為FHGED依次推得該二叉樹的結(jié)構(gòu)圖.前序序列為：CBADEGFH.【練習(xí)題】一、選擇題一棵非空二叉樹的前序遍歷序列和后序遍歷序列正好相反，則該二叉樹一定滿足.A.所有結(jié)點均無左孩子 B所有的結(jié)點均無右孩子C.只有一個葉子結(jié)點 D是任意一棵二叉樹一棵完全二叉樹上有1001個結(jié)點，其中葉子結(jié)點的個數(shù)是.A.250 B.500C.254 D.505E.以上答案都不對設(shè)深度為k的二叉樹上只有度為0和度為2的結(jié)點，則這類二叉樹上所含的結(jié)點總數(shù)為.A.k+1B.2kC.2k-l D.2k+1設(shè)有13個值，用它們組成一棵哈夫曼樹，則該哈夫曼樹共有個結(jié)點.TOC\o"1-5"\h\zA.13 B.12C.26 D.25將有關(guān)二叉樹的概念推廣到三叉樹，則一棵有244個結(jié)點的完全三叉樹的高度是 .A.4 B.5C.6 D.7設(shè)樹T的高度為4,其中度為1、2、3和4的結(jié)點個數(shù)分別為4、2、l、1，則T中的葉子數(shù)為.A.5 B.6C.7 D.8某二叉樹中序序列為abcdefg，后序序列為bdcafge，則前序序列是 .A.egfacbdB.eacbdgfC.eagcfbdD.以上答案都不對在一棵度為3的樹中，度為3的結(jié)點個數(shù)為2個，度為2的結(jié)點數(shù)為1個，度為1的結(jié)點數(shù)為2個，則度為0的結(jié)點個數(shù)為.TOC\o"1-5"\h\zA.4 B.5C.6 D.7在一棵具有K層的滿三叉樹中，結(jié)點總數(shù)為.A.(3k-1)/2 B.3k-lC.(3k-1)/3 D.3k滿二叉樹的葉結(jié)點為N，則它的結(jié)點總數(shù)為.A.NB.2NC.2N-1D.2N+1E.2 N-1二、問題解答已知，按中序遍歷二叉樹的結(jié)果為：abc.問：有多少種不同形態(tài)的二叉樹可以得到這一遍歷結(jié)果，并畫出這些二叉樹.一棵樹的前序遍歷為：ABDECFGHI，中序遍歷為：DBEAFCHIG，求后序遍歷。4.4圖圖（Graph）是一種復(fù)雜的非線性結(jié)構(gòu).在人工智能、工程、數(shù)學(xué)、物理、化學(xué)、生物和計算機(jī)科學(xué)等領(lǐng)域中，圖結(jié)構(gòu)有著廣泛的應(yīng)用.奧林匹克信息學(xué)競賽的許多試題，亦需要用圖來描述數(shù)據(jù)元素間的聯(lián)系.圖G由兩個集合V和E組成，記為：G=（V，E），其中：V是頂點的有窮非空集合，E是V中頂點偶對（稱為邊）的有窮集.通常，也將圖G的頂點集和邊集分別記為V（C）和E（G）.E（G）可以是空集.若E（G）為空，則圖G只有頂點而沒有邊.（一）有向圖和無向圖1有向圖若圖G中的每條邊都是有方向的，則稱G為有向圖（Digraptl）.在有向圖中，一條有向邊是由兩個頂點組成的有序?qū)?，有序?qū)νǔＳ眉饫ㄌ柋硎?有向邊也稱為弧（Arc），邊的始點稱為弧尾（Tail），終點稱為弧頭（Head）.例如＜vi，七＞表示一條有向邊，vi是邊的始點（起點），v是邊的終點.因此，＜Vi,七＞和＜七，Vi＞是兩條不同的有向邊.下面（a）圖中G1是一個有向圖.圖中邊的方向是用從始點指向終點的箭頭表示的，該圖的頂點集和邊集分別為：v（G1）={v1，v2，v3}E（G1）={＜V，v＞，＜v，v＞，＜v，v＞}l2 2l 2 3J2無向圖若圖G中的每條邊都是沒有方向的，則稱G為無向圖（Undigraph）.無向圖中的邊均是頂點的無序?qū)?，無序?qū)νǔＳ脠A括號表示.例如無序?qū)Γㄆ?，七）和（v.,vi）表示同一條邊.下面4-4-1（b）中的G2和圖4-4-1（c）中的G3均是無向圖，它們的頂點集和邊集分別為：V（G2）={vl，v2，v3，v4}E（G）={（V，V），（v，v），（v，v），（v，v），（v，v），（V，V）}TOC\o"1-5"\h\zl2 1 3 l4 2 3 24 34,）V（G）={v，V，v，v，v，v，v}l2 3 4 5 6 /E（G）={（V，v），（V，v），（V，v），（v，v），（v，v），（V，V）}3 l2 l3 2 4 2 5 3 6 3 /3圖G的頂點數(shù)n和邊數(shù)e的關(guān)系(1若G是無向圖，則O忍e忍n(n—1)/2恰有n(n—■1)/2條邊的無向圖稱無向完全圖(Undireet—edCompleteGraph)(2若G是有向圖，則O^e^n(n—1).恰有n(n—1)條邊的有向圖稱為有向完全圖(DirectedCompleteGraph).注意：完全圖具有最多的邊數(shù).任意一對頂點間均有邊相連.例如上面圖4-4-1(b)的G2就是具有4個頂點的無向完全圖.圖的邊和頂點的關(guān)系無向邊和頂點關(guān)系若(Vj,v.)是一條無向邊，則稱頂點vi和V.互為鄰接點(Adjacent),或稱vi和V.相接連；并稱(Vj,v.)依附或關(guān)聯(lián)(Incident)于頂點vj和v.,或稱(v^v.)與頂點vi和v.相關(guān)聯(lián).例如圖4-4-1(b)G2中：①與頂點vi相鄰接的頂點是v,v和V；②關(guān)聯(lián)于頂點V的邊是(v,v),(v,v)和(v,v)2 3 4 2 1 2 23/ 2^4^2有向邊和頂點關(guān)系若＜vi?v.＞是一條有向邊，則稱頂點vi鄰接到v.,頂點vi鄰接于頂點v.；并稱邊＜七，v.＞關(guān)聯(lián)于vi和v.或稱＜匕，V.〉與頂點vi和v.相關(guān)聯(lián).例如在圖4-4-1(a)Gl中，關(guān)聯(lián)于頂點v2的孤是＜vl，v2＞,＜v2,vi＞和＜v2，v3＞.3.頂點的度(Degree)無向圖中頂點v的度(Degree)無向圖中頂點v的度(Degree)是關(guān)聯(lián)于該頂點的邊的數(shù)目，記為D(v).例如圖4-4-l(b)G2中頂點vl的度為3.(2)有向圖頂點v的度(InDegree)有向圖中，以頂點v為終點的邊的數(shù)目稱為v的人度(Indegree)，記為ID(v).例如在圖4-4-l(a)G1中頂點^的入度為1.有向圖中，以頂點v為始點的邊的數(shù)目，稱為v的出度(Outdegree),記為OD(v).例如在圖4-4-1(a)Gl中頂點v2的出度為所以在有向圖中，頂點v的度定義為該頂點的人度和出度之和，即D(v)=ID(v)+OD(v).例如在圖4-4-1(a)G1中頂點v2的人度為l,出度為2,則度為3.從上述我們可以得知，無論有向圖還是無向圖，頂點數(shù)n、邊數(shù)e和度數(shù)之間有如下關(guān)系:子圖設(shè)G=(V,E)是一個圖，若v’是V的子集，E’是E的子集，且E’中的邊所關(guān)聯(lián)的頂點均在V’中，則G’=(V’，E’)也是一個圖，并稱其為G的子圖(Subgraph).例如圖4-4-2(a)給出了有向圖G1的若干子圖；圖4-4-2(b)?J m卜居1■叫給出了無向圖G2的若干個子圖.再比如，設(shè)V’={v〔，v2，v3}，E’={(v〔，v2)，(v2，v4)}，顯然，V’屬于V(G2)，E’屬于E(G2)，但因為E’中序偶對(v2,v4)所關(guān)聯(lián)的頂點v4不在V’中，所以(V’，E’)不是圖，也就不可能是G2的子圖.四)路徑(Path)1無向圖的路徑在無向圖G中，若存在一個頂點序列vp，v^’vi2，…，vim，vq，使得(vp，VC，El，vi2)，…，Em，七)均屬于E(G)，則稱頂點vp到vq存在一條路徑(Path).2有向圖的路徑在有向圖G中，路徑也是有向的，它由E(G)中的有向邊＜vp，vii＞，＜筆1，％＞，…，＜服七＞組成.3路徑長度路徑長度定義為該路徑上邊的數(shù)目.4簡單路徑若一條路徑上除了vp和vq可以相同外，其余頂點均不相同，則稱此路徑為一條簡單路徑.例如在圖G2中頂點序列vi，v2,v3,v4是一條從頂點vi到頂點v4的長度為3的簡單路徑.例如在圖G2中，頂點序列vi，v2，v4，vi，v3是一條從頂點vi到頂點v3的長度為4的路徑，但不是簡單路徑；5簡單回路或簡單環(huán)(Cycle)

起點和終點相同(vp=vq)的簡單路徑稱為簡單回路或簡單環(huán)(cycle).例如圖G2中，頂點序列v/v2,v4,v1是一個長度為3的簡單環(huán).例如圖4-4-1中有向圖G1中，頂點序列vi，v2,vi是一長度為2的有向簡單環(huán).6有根圖和圖的根在一個有向圖中，若存在一個頂點v，從該頂點有路徑可以到達(dá)圖中其它所有頂點，則稱此有向圖為有根圖，v稱作圖的根.連通圖和連通分量1.頂定間的連通性在無向圖G中，若從頂點v±到頂點七有路徑(當(dāng)然從V到匕也一定有路徑)，則稱七和七是連通的.2連通圖若V(G)中任意兩個不同的頂點v±和七都連通(即有路徑)，則稱G為連通圖(Con-nectedGraph).例如圖4-4-1中G2和G3是連通圖.連通分量無向圖G的極大連通子圖稱為G的連通分量(connectedComponent).注意：任何連通圖分量只有一個，即是其自身；另外非連通的無向圖有多個連通分量.例如圖4-4-3中的G4是非連通圖.它有兩個連通分量Hl和H2.陽口14.屯向中專■丘的季if酒同匚圖44-3具有兩個分量的非連通圖G4強(qiáng)連通圖和強(qiáng)連通分量1強(qiáng)連通圖有向圖G中，若對于V(G)中任意兩個不同的頂點v±和七，都存在從七到v以及從v到七的路徑，則稱G是強(qiáng)連通圖. ''2強(qiáng)連通分量有向圖的極大強(qiáng)連通子圖稱為G的強(qiáng)連通分量.強(qiáng)連通圖只有一個強(qiáng)連通分量，即是其自身.非強(qiáng)連通的有向圖有多個強(qiáng)連通分量.例如圖4-4-4中的G1不是強(qiáng)連通圖，因為v3到v2沒有路徑，但它有兩個強(qiáng)連通分量，如圖4-4-5所示.

A-a"r,「i璀"疑*葉屈JI： ty■o六）圖的存儲結(jié)構(gòu)圖的存儲方法有很多，我們這里只介紹圖的鄰接矩陣表示法.在圖的鄰接矩陣表示法中：用鄰接矩陣表示頂點間的相鄰關(guān)系；用一個順序表來存儲頂點信息.設(shè)G：（V，E）是具有n個頂點的圖，則G的鄰接矩陣是具有如下性質(zhì)的n階方陣，其規(guī)模為nXn：,r..7 [L：砒知.隊例如圖4-4-6中無向圖G5和有向圖G6的鄰接矩陣分別為A1和A2.例58G是一個非連通無向圖，共有28條邊，則該圖至少有個頂點.8個頂點的完全圖共有28條邊，再加一個孤立頂點使G成為非連通的.其他情況，由于點未充分利用必定多于9個.所以答案是9.（七）圖的遍歷給出一個圖G和其中任意一個結(jié)點V0，從V0出發(fā)系統(tǒng)地訪問G中所有結(jié)點，每一個結(jié)點被訪問一次，這就叫圖的遍歷.遍歷圖的結(jié)果是按訪問順序?qū)⒔Y(jié)點排成一個線性序列.通常有兩種遍歷方法：深度優(yōu)先搜索和廣度優(yōu)先搜索，他們對

無向圖和有向圖都適用.1深度優(yōu)先搜索深度優(yōu)先搜索類似于樹的前序遍歷，是樹的前序遍歷的推廣.假設(shè)初始時所有結(jié)點未曾被訪問，深度優(yōu)先搜索從某個結(jié)點V0出發(fā)，然后依次訪問從V0的未被訪問的鄰接點出發(fā)深度