1、會(huì)計(jì)學(xué)1數(shù)據(jù)結(jié)構(gòu)軟件數(shù)據(jù)結(jié)構(gòu)軟件第1頁/共354頁第2頁/共354頁DS第3頁/共354頁DS數(shù)據(jù)結(jié)構(gòu)Data Structure第4頁/共354頁第5頁/共354頁第6頁/共354頁第7頁/共354頁第8頁/共354頁第9頁/共354頁第10頁/共354頁第11頁/共354頁第12頁/共354頁第13頁/共354頁（第14頁/共354頁第15頁/共354頁 1數(shù)據(jù)的邏輯結(jié)構(gòu) 2、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 3、數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等。 A線性結(jié)構(gòu) B非線性結(jié)構(gòu)A 順序存儲(chǔ) B 鏈?zhǔn)酱鎯?chǔ) 線性表?xiàng)ｊ?duì)樹形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面 第16頁/共354頁第17頁/共354頁nn效率與存

2、貯量效率與存貯量第18頁/共354頁第19頁/共354頁第20頁/共354頁第21頁/共354頁1.簡(jiǎn)要回答下列問題：a. 數(shù)據(jù)與數(shù)據(jù)元素有何區(qū)別？b. 邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)是什么？它們是什么關(guān)系？c. 什么是算法？它有什么特點(diǎn)？第22頁/共354頁 2. 試寫一個(gè)算法，統(tǒng)計(jì)輸入的100個(gè)整數(shù)中奇數(shù)和偶數(shù)的個(gè)數(shù)。 3. 設(shè)計(jì)下面問題算法，并分析最壞情況時(shí)間復(fù)雜性:在數(shù)組 A1.n中查找值為 K的元素，若找到輸出其位置 i ( 0 i n+1),否則輸出0。第23頁/共354頁 4. 設(shè) n 為正整數(shù)，寫出下列程序段的時(shí)間復(fù)雜度：（1）for(I=1;In;I+)m=m+I;for(j=0;jn;

3、j+) count +=m+j;第24頁/共354頁（2）for(I=0;In;I+)m=m+I;for(j=0;j10;) count +=m+j;j+;第25頁/共354頁（3）k=1;s=0;while(snext&jnext; + j; if(!(p-next)|j i-1) return ERROR;/刪除位置不合理 q = p-next; p-next = q-next; /刪除并釋放結(jié)點(diǎn)*e = q- data ;free(q);return OK;/ListDelete_L第78頁/共354頁 兩個(gè)有序單鏈表合并為一個(gè)有序單鏈表(非遞減)MergeList_L(Linklist

4、 La,LinkList Lb,LinkList Lc)pa = La-next; pb = Lb-next;Lc = pc = La;While (pa & pb)If(pa-data data)pc-next = pa;pc = pa; pa = pa-next;elsepc-next = pb;pc = pb; pb= pb-next;pc-next = pa?pa:pb;free(Lb);第79頁/共354頁第80頁/共354頁第81頁/共354頁第82頁/共354頁prior 第83頁/共354頁：AB第84頁/共354頁p第85頁/共354頁第86頁/共354頁第87頁/共354頁

5、bcaP;p-next-prior=p-prior;第88頁/共354頁p-prior-next=p-next;p-next-prior=p-prior;bacp第89頁/共354頁 第90頁/共354頁結(jié)點(diǎn)數(shù)據(jù)占用存儲(chǔ)量量結(jié)點(diǎn)數(shù)據(jù)本身占用存儲(chǔ)存儲(chǔ)密度第91頁/共354頁1.描述以下三個(gè)概念的區(qū)別：頭結(jié)點(diǎn)、頭指針和開始結(jié)點(diǎn)2.從尾指針出發(fā)能訪問到鏈表上所有結(jié)點(diǎn)的鏈表有 。3.假設(shè)有兩個(gè)按元素值遞增的線性表 A、B，編寫算法將兩表合并為一個(gè)按元素值遞減的線性表C。（分別以順序、鏈?zhǔn)綄?shí)現(xiàn)）第92頁/共354頁 4.設(shè)線性表存放在向量 AMAXSIZE的前elenum個(gè)分量中，且遞增有序。試寫一算法

6、，將 x 插入線性表適當(dāng)位置上，以保持線性表的有序性，并且分析算法的時(shí)間復(fù)雜性。 5.以鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)上題。第93頁/共354頁 6.在雙向鏈表上實(shí)現(xiàn)線性表的下列基本運(yùn)算：(1) 初始化(2) 定位(3) 插入(4) 刪除第94頁/共354頁第95頁/共354頁第96頁/共354頁第97頁/共354頁（5）獲得棧頂元素值）獲得棧頂元素值GetTop(s,&e)第98頁/共354頁. 第99頁/共354頁 棧和線性表類似，也有兩種（順序、鏈?zhǔn)剑?shí)現(xiàn)方法第100頁/共354頁 第101頁/共354頁 第102頁/共354頁 top=-1123450?？諚ｍ斨羔榯op,指向?qū)嶋H棧頂后的空位置，初值

7、為-1top123450進(jìn)棧Atop出棧棧滿BCDEF設(shè)數(shù)組維數(shù)為Mtop=-1,?？?，此時(shí)出棧，則下溢（underflow)top=M-1,棧滿，此時(shí)入棧，則上溢（overflow)toptoptoptoptop123450ABCDEFtoptoptoptoptoptop棧空第103頁/共354頁第104頁/共354頁第105頁/共354頁typedef struct node int data; struct node *link;LinkList;結(jié)點(diǎn)定義 .topdata link棧底棧頂?shù)?06頁/共354頁第107頁/共354頁第108頁/共354頁第109頁/共354頁第110頁

8、/共354頁第111頁/共354頁子過程3srr第112頁/共354頁第113頁/共354頁 第114頁/共354頁 第115頁/共354頁 第116頁/共354頁運(yùn)行結(jié)果：1，2，2，3，3，3，第117頁/共354頁主程序(1)print(w) w=3; 3print(2);（1）w=3 top(2) 輸出：3, 3, 3w2print(1);（2）w=2 （1）w=3 top(3) 輸出：2, 2w1print(0);（3）w=1 （2）w=2 （1）w=3 top(4)輸出：1w0（4）w=0 （3）w=1 （2）w=2 （1）w=3 topw(3) 輸出：2, 2(2) 2(1) 3

9、top(4)輸出：1(3) 1(2) 2(1) 3top(2) 輸出：3, 3, 3 (1 ) 3top返回(3) 1(2) 2(1) 3top(4) 0結(jié)束(1)第118頁/共354頁 假設(shè)表達(dá)式中有多種擴(kuò)號(hào)，可以用棧來進(jìn)行擴(kuò)號(hào)匹配檢驗(yàn)，具體做法為：非括號(hào)字符跳過不理；碰上左擴(kuò)號(hào)，入棧；碰上右擴(kuò)號(hào)，出棧，并且檢查出棧元素是否與當(dāng)前右擴(kuò)號(hào)相匹配，若匹配繼續(xù)檢查，否則匹配失敗。請(qǐng)同學(xué)們下去自己編程序試試。第119頁/共354頁第120頁/共354頁第121頁/共354頁 第122頁/共354頁 第123頁/共354頁隊(duì)列的主要操作第124頁/共354頁第125頁/共354頁第126頁/共354頁

10、 第127頁/共354頁p = (QueuePtr)malloc(sizeof(Qnode);p-data = x;p-next = NULL;Q-rear-next = p;Q-rear = p; 第128頁/共354頁if(Empty(Q) return ERROR;else s = Q-front-next;/*指向被刪結(jié)點(diǎn)*/ if(s-next = NULL)Q-front-Next = Null; Q-rear = Q-front;Else Q-front-next = s-next;*e = s-data;free(s);return OK;第129頁/共354頁front=-1

11、rear=-1123450隊(duì)空123450frontJ1,J1,J3入隊(duì)J1J2J3rearrear123450J4,J5,J6入隊(duì)J4J5J6front設(shè)兩個(gè)指針front,rear,約定：rear指示隊(duì)尾元素；front指示隊(duì)頭元素前一位置初值front=rear=-1空隊(duì)列條件：front=rear入隊(duì)列：sq+rear=x;出隊(duì)列：x=sq+front;rearrearfrontrear123450J1,J2,J3出隊(duì)J1J2J3frontfrontfront第130頁/共354頁第131頁/共354頁 ：； 實(shí)現(xiàn)：利用“模”運(yùn)算 入隊(duì)： rear=(rear+1)%M; sqrear

12、=x; 出隊(duì)： front=(front+1)%M; x=sqfront; 隊(duì)滿、隊(duì)空判定條件.第132頁/共354頁rearfrontmaxSize-1入隊(duì): rear=(rear+1) % MaxSize; elementsrear=item出隊(duì)：front=(front+1)%MaxSize; 隊(duì)空：rear = front;隊(duì)滿：(rear+1) % maxSize=front;012front012rear隊(duì)列初始化：front = rear = 0;n存儲(chǔ)隊(duì)列的數(shù)組被當(dāng)作首尾相接的表處理。n隊(duì)頭、隊(duì)尾指針加1時(shí)從MaxSize -1直接進(jìn)到0，可用語言的取模(余數(shù))運(yùn)算實(shí)現(xiàn)。第13

13、3頁/共354頁tJ4,J5,J6出隊(duì)J7,J8,J9入隊(duì)解決方案：1.另外設(shè)一個(gè)標(biāo)志以區(qū)別隊(duì)空、隊(duì)滿2.少用一個(gè)元素空間： 隊(duì)空：front=rear 隊(duì)滿：(rear+1)%M=front第134頁/共354頁第135頁/共354頁void en_cycque(int sq,int front,int rear,int x) if(rear+1)%MAXSIZE)=front) printf(overflow); else rear=(rear+1)%MAXSIZE; sqrear=x; 第136頁/共354頁int del_cycque(int sq,int front,int rear

14、,int *q) if(front=rear) return(0); else front=(front+1)%MAXSIZE; *q=sqfront; return(1); 第137頁/共354頁1. 鐵路進(jìn)行列車調(diào)度時(shí), 常把站臺(tái)設(shè)計(jì)成棧式結(jié)構(gòu)的站臺(tái)，如右圖所示。試問：(1) 設(shè)有編號(hào)為1,2,3,4,5, 6的六輛列車, 順序開入棧式結(jié)構(gòu)的站臺(tái), 則可能的出棧序列有多少種?(2) 若進(jìn)站的六輛列車順序如上所述, 那么是否能夠得到435612, 325641, 154623和135426的出站序列, 如果不能, 說明為什么不能; 如果能, 說明如何得到(即寫出進(jìn)棧或出棧的序列)。 第138

15、頁/共354頁2.假設(shè)以數(shù)組Qm存放循環(huán)隊(duì)列中的元素, 同時(shí)以rear和length分別指示環(huán)形隊(duì)列中的隊(duì)尾位置和隊(duì)列中所含元素的個(gè)數(shù)。試給出該循環(huán)隊(duì)列的隊(duì)空條件和隊(duì)滿條件, 并寫出相應(yīng)的插入(enqueue)和刪除(delqueue)元素的操作。 第139頁/共354頁第140頁/共354頁數(shù)組的性質(zhì) 數(shù)組元素?cái)?shù)目固定元素類型相同下標(biāo)有界且有序 第141頁/共354頁一維數(shù)組數(shù)組圖示 第142頁/共354頁數(shù)組圖示 第143頁/共354頁第144頁/共354頁232221131211aaaaaaA 多維數(shù)組以一維方式存儲(chǔ)，即數(shù)組元素還是數(shù)組！第145頁/共354頁LOC ( i ) = LO

16、C ( i -1 ) + l =+ i*l一維數(shù)組的存儲(chǔ)第146頁/共354頁二維數(shù)組的存儲(chǔ)231322122111aaaaaa a23 a22 a21 a13 a12 a11 a23 a13 a22 a12 a21 a11第147頁/共354頁)( 2 1 02 22 12 021 21 11 01 0 20 10 00aijLocMNANANANAMAAAAMAAAAMAAAA求對(duì)例：第148頁/共354頁limialimimmmimmmiaiiiLOCnjnjknkjnnnnnn*)(),(111143232121第149頁/共354頁第150頁/共354頁。 1, 1221100nna

17、aaa00 1, 12, 11, 22322211211100100nnnnnnaaaaaaaaaaa00第151頁/共354頁jijini; k 1| ;1| ;232jijinji k 第152頁/共354頁 1, 10 , 1111000nnnaaaaa0 1, 122111, 00100nnnaaaaaa0第153頁/共354頁 jijinnjii;2/ ) 1(2/ ) 1( k jijinnjni iin;2/ ) 1() 1(2/ ) 1() 1( k 第154頁/共354頁 第155頁/共354頁 第156頁/共354頁三元組表類型說明：#define SMAX 16typed

18、ef int datatype；typedef structint i,j; /*行列號(hào)*/datatype v;/*元素值*/node;typedef structint m,n,t;/*行、列數(shù)，非零元素個(gè)數(shù)*/node dataSMAX;/*三元組表*/SpMatrix; r ro ow w c co ol l v va al lu ue e 第157頁/共354頁 三元組表示例100001013200M 1 3 2 2 0 2 1 1 1 1 2 0 3 1 0 5 4 3行數(shù) 列數(shù) 元素個(gè)數(shù) 行 列 值第158頁/共354頁000001500390170000000000602228

19、0000000001100910000B 0000280000000091039000000006000017000110150022000A6776轉(zhuǎn)置為 第159頁/共354頁 第160頁/共354頁 行行行行 ( (r ro ow w) ) 列列列列( (c co ol l) ) 值值值值( (v va al lu ue e) ) 行行行行( (r ro ow w) ) 列列列列( (c co ol l) ) 值值值值( (v va al lu ue e) ) 0 0 0 3 3 2 22 2 0 0 0 4 4 9 91 1 1 0 0 6 6 1 15 5 1 1 1 1 1 1 1

20、1 1 2 1 1 1 1 1 11 1 2 2 2 5 5 2 28 8 3 1 1 5 5 1 17 7 3 3 3 0 0 2 22 2 4 2 2 3 3 - - - -6 6 4 3 3 2 2 - - - -6 6 5 3 3 5 5 3 39 9 5 5 5 1 1 1 17 7 6 4 4 0 0 9 91 1 6 5 5 3 3 3 39 9 7 5 5 2 2 2 28 8 7 6 6 0 0 1 16 6 第161頁/共354頁第162頁/共354頁時(shí)間復(fù)雜度：O(n*t) 第163頁/共354頁信息信息n在分析算法的行為時(shí)，可用樹來在分析算法的行為時(shí)，可用樹來描述其執(zhí)行

21、過程描述其執(zhí)行過程第164頁/共354頁 樹是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)，是以分支關(guān)系定義的層次結(jié)構(gòu)(subtree)如果如果n = 0，稱為空樹；，稱為空樹；第165頁/共354頁第166頁/共354頁第167頁/共354頁第168頁/共354頁兄弟兄弟(sibling)-(sibling)-同一雙親的孩子同一雙親的孩子第169頁/共354頁第170頁/共354頁A只有根結(jié)點(diǎn)的樹ABCDEFGHIJKLM有子樹的樹根子樹第171頁/共354頁ABCDEFGHIJKLMABCDEFGHIJKLM 第172頁/共354頁 (d) (d) (d)第173頁/共354頁ABABABAB第174頁/共3

22、54頁A只有根結(jié)點(diǎn)的二叉樹A只有根結(jié)點(diǎn)的二叉樹空二叉樹空二叉樹AB右子樹為空ABAB右子樹為空AB左子樹為空ABAB左子樹為空ABC左、右子樹均非空ABCABC左、右子樹均非空 第175頁/共354頁) 1(21iii個(gè)結(jié)點(diǎn)層上至多有在二叉樹的第12201i12j12222ii12j第176頁/共354頁第177頁/共354頁第178頁/共354頁第179頁/共354頁 第180頁/共354頁第181頁/共354頁123456123456123456123114589121367101415滿二叉樹123114589121367101415123114589121367101415123114

23、589126710完全二叉樹123114589126710123114589126710123456712345671234567滿二叉樹完全二叉樹第182頁/共354頁第183頁/共354頁二叉樹的存儲(chǔ)結(jié)構(gòu)二、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 第184頁/共354頁二叉樹的存儲(chǔ)結(jié)構(gòu)typedef struct node datatype data; struct node *lchild, *rchild;JD, bitree;lchild data rchild 二叉鏈表-2個(gè)指針域 第185頁/共354頁ABCDEFG AB C D E F G在n個(gè)結(jié)點(diǎn)的二叉鏈表中，有n+1個(gè)空指針域二叉樹的存儲(chǔ)結(jié)構(gòu)二叉鏈

24、表圖示第186頁/共354頁二叉樹的存儲(chǔ)結(jié)構(gòu)三叉鏈表-3個(gè)指針域 typedef struct node datatype data; struct node *lchild, *rchild, *parent;JD;lchild data parent rchild第187頁/共354頁二叉樹的存儲(chǔ)結(jié)構(gòu)ABCDEFG A B C D E F G第188頁/共354頁5.3 遍歷二叉樹 遍歷按一定規(guī)律走遍樹的各個(gè)頂點(diǎn)，且使每一頂點(diǎn)僅被訪問一次，即找一個(gè)完整而有規(guī)律的走法，以得到樹中所有結(jié)點(diǎn)的一個(gè)線性排列 第189頁/共354頁5.3 遍歷二叉樹二叉樹的遍歷方法： 1.先序遍歷：先訪問根結(jié)點(diǎn),然

25、后分別先序遍歷左子樹、右子樹 DLR 2.中序遍歷：先中序遍歷左子樹，然后訪問根結(jié)點(diǎn)，最后中序遍歷右子樹 LDR 3.后序遍歷：先后序遍歷左、右子樹，然后訪問根結(jié)點(diǎn)LRD 4.按層次遍歷：從上到下、從左到右訪問各結(jié)點(diǎn) DLR第190頁/共354頁二叉樹的遍歷DLRLDR、LRD、DLRRDL、RLD、DRL第191頁/共354頁二叉樹的遍歷PreOrder ( BinTreeNode*current ) if ( current != NULL ) Visit( currentdata); PreOrder ( currentleftChild ); PreOrder ( currentrig

26、htChild ); 先序遍歷遞歸算法如下：第192頁/共354頁二叉樹的遍歷ADBCD L RAD L RD L RBDCD L R先序遍歷序列：A B D C先序遍歷:第193頁/共354頁二叉樹的遍歷Void PreOderTraverse(BiTree T)if(T! =NULL) printf (T-data); PreOrderTraverse(T-lchild); PreOrderTraverser(T-rchild); /*先序遍歷*/主程序Pre( T )返回返回pre(T R);返回返回pre(T R);ACBDTBprintf(B);pre(T L);BTAprintf(

27、A);pre(T L);ATDprintf(D);pre(T L);DTCprintf(C);pre(T L);C返回T左是空返回pre(T R);T左是空返回T右是空返回T左是空返回T右是空返回pre(T R);第194頁/共354頁二叉樹的遍歷InOrder ( BinTreeNode* current ) if ( current != NULL ) InOrder ( currentleftChild ); Visit( currentdata); InOrder ( currentrightChild ); 中序遍歷地歸算法如下：第195頁/共354頁二叉樹的遍歷ADBCL D RB

28、L D RL D RADCL D R中序遍歷序列：B D A C中序遍歷:第196頁/共354頁LastOrder ( BinTreeNode* current ) if ( current != NULL ) LastOrder ( currentleftChild ); LastOrder ( currentrightChild ); Visit( currentdata); 后序遍歷地歸算法如下：二叉樹的遍歷第197頁/共354頁二叉樹的遍歷ADBC L R DL R DL R DADCL R D后序遍歷序列： D B C A后序遍歷:B第198頁/共354頁二叉樹的遍歷 遞歸算法邏輯清

29、晰、易懂，但在實(shí)現(xiàn)時(shí)，由于函數(shù)調(diào)用棧層層疊加，效率不高，故有時(shí)考慮非遞歸算法。 第199頁/共354頁 二叉樹的遍歷 先找到左下結(jié)點(diǎn)，即沿左鏈一直下來，直到左鏈為空，這時(shí)，所有路過的結(jié)點(diǎn)進(jìn)棧。然后結(jié)點(diǎn)出棧并訪問，對(duì)于每個(gè)出棧結(jié)點(diǎn)，即表示該結(jié)點(diǎn)和其左子樹已被訪問結(jié)束，應(yīng)該訪問該結(jié)點(diǎn)的右子樹。 （1）當(dāng)前指針指向根結(jié)點(diǎn)。 （2）當(dāng)前指針指向其左孩子并進(jìn)棧，重復(fù)（2），直到左孩子為NULL （3）退棧，打印出棧結(jié)點(diǎn)，將當(dāng)前指針指向右孩子， （4）若棧非空或當(dāng)前指針非NULL，執(zhí)行（2）；否則結(jié)束。第200頁/共354頁二叉樹的遍歷InOrder ( BinTreeNode* T ) InitStac

30、k(s);p=T;While(p|!StackEmpty(s) if ( p!= NULL ) Push(s,p);p=p-lchild;ElsePop(s,p); visit(p-data);P=p-rchild;第201頁/共354頁二叉樹的遍歷二叉樹的遍歷方法小結(jié)-+/a*b-efcd先序遍歷：中序遍歷：后序遍歷：層次遍歷：- + a * b - c d / e f-+a*b-cd/ef- +a *b - c d/e f-+a*b-c d/e f第202頁/共354頁二叉樹的遍歷二叉樹的小結(jié)1、 二叉樹： 或?yàn)榭諛?，或由根及兩顆不相交的左子樹、右子樹構(gòu)成，并且左、右子樹本身也是二叉樹；2

31、、 二叉樹即可以用順序結(jié)構(gòu)存儲(chǔ)，也可用鏈?zhǔn)浇Y(jié)構(gòu)存儲(chǔ)；3、 遍歷：按某種搜索路徑訪問二叉樹的每個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)僅被訪問一次。 二叉樹的遍歷可以分解為：訪問根，遍歷左子樹和遍歷右子樹，三種遍歷算法：先序遍歷、中序遍歷、后序遍歷；第203頁/共354頁二叉樹的遍歷應(yīng)用 方法：對(duì)二叉樹進(jìn)行遍歷，判斷被訪問的結(jié)點(diǎn)是否葉子結(jié)點(diǎn)，若是葉子結(jié)點(diǎn)，則將計(jì)數(shù)器加1。int countleaf(BiTree) int n1,n2; if (T= =NULL) return(0); else if (T-lchild= =NULL) & (T-rchild= =NULL) return(1); else n1=cou

32、ntleaf (T-lchild); n2=countleaf (T-rchild); return( n1+n2); 一、統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù)第204頁/共354頁孩子兄弟表示法（二叉樹表示法）5.4 樹的存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)：用二叉鏈表作樹的存儲(chǔ)結(jié)構(gòu)，鏈表中每個(gè)結(jié)點(diǎn)的兩個(gè)指針域分別指向其第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)特點(diǎn) 操作容易 破壞了樹的層次typedef struct node datatype data; struct node *fch, *nsib;JD;abcdefhgi a b c d e f g h i第205頁/共354頁樹的存儲(chǔ)結(jié)構(gòu) 孩子兄弟存儲(chǔ)結(jié)構(gòu)是為每個(gè)結(jié)點(diǎn)設(shè)計(jì)三個(gè)

33、域：一個(gè)數(shù)據(jù)元素域，一個(gè)該結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)指針域，一個(gè)該結(jié)點(diǎn)的下一個(gè)兄弟結(jié)點(diǎn)指針域。 由于樹的孩子兄弟存儲(chǔ)結(jié)構(gòu)有兩個(gè)指針域，并且這兩個(gè)指針是有序的，所以孩子兄弟存儲(chǔ)結(jié)構(gòu)是把樹轉(zhuǎn)換為二叉樹的存儲(chǔ)結(jié)構(gòu)。把樹轉(zhuǎn)換為二叉樹所對(duì)應(yīng)的結(jié)構(gòu)恰好就是這種孩子兄弟存儲(chǔ)結(jié)構(gòu) 孩子兄弟存儲(chǔ)結(jié)構(gòu)的最大優(yōu)點(diǎn)是可方便地實(shí)現(xiàn)樹和二叉樹的相互轉(zhuǎn)換。孩子兄弟存儲(chǔ)結(jié)構(gòu)的缺點(diǎn)也和孩子表示法的缺點(diǎn)一樣：從當(dāng)前結(jié)點(diǎn)查找雙親結(jié)點(diǎn)比較麻煩，需要從樹的根結(jié)點(diǎn)開始逐個(gè)結(jié)點(diǎn)比較查找。第206頁/共354頁樹與二叉樹的轉(zhuǎn)換樹與二叉樹上結(jié)點(diǎn)的對(duì)應(yīng)關(guān)系 二叉樹中各結(jié)點(diǎn)：左孩子 - 該結(jié)點(diǎn)的第一個(gè)孩子右孩子 - 該結(jié)點(diǎn)的第一個(gè)右兄弟注：由一棵樹轉(zhuǎn)換

34、得到的二叉樹必?zé)o右子樹（思考：為什么？）第207頁/共354頁樹與二叉樹的轉(zhuǎn)換ACBED樹ABCDE二叉樹 A B C D E A B C D E A B C D E 對(duì)應(yīng)存儲(chǔ)存儲(chǔ)解釋解釋第208頁/共354頁樹與二叉樹的轉(zhuǎn)換樹根結(jié)點(diǎn) X 的第一個(gè)孩子結(jié)點(diǎn) X 緊鄰的右兄弟二叉樹根結(jié)點(diǎn) X 的左孩子結(jié)點(diǎn) X 的右孩子樹轉(zhuǎn)換成二叉樹第209頁/共354頁樹與二叉樹的轉(zhuǎn)換IACBDHGFEFIABDHGCE樹轉(zhuǎn)換成二叉樹第210頁/共354頁樹與二叉樹的轉(zhuǎn)換 森林轉(zhuǎn)換為二叉樹ADCBEFHIGJEFADCBHIGJADCBEFHIGJADCBEFHIGJ方法： 將各棵樹分別轉(zhuǎn)成二叉樹； 把每棵樹的

35、根結(jié)點(diǎn)用線連起來； 以第一棵樹的根結(jié)點(diǎn)作為二叉樹的根結(jié)點(diǎn)，按順時(shí)針方向旋轉(zhuǎn)。第211頁/共354頁樹與二叉樹的轉(zhuǎn)換ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ 森林轉(zhuǎn)換為二叉樹第212頁/共354頁二叉樹轉(zhuǎn)換成森林抹線：將二叉樹中根結(jié)點(diǎn)與其右孩子連線，及沿右分支搜索到的所有右孩子間連線全部抹掉，使之變成孤立的二叉樹還原：將孤立的二叉樹還原成樹ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ樹與二叉樹的轉(zhuǎn)換第213頁/共354頁樹與森林的遍歷常用方法（前）先根（序）遍歷：先訪問樹的根結(jié)點(diǎn)，然后依次先根遍歷根的每棵子樹后根（序）遍

36、歷：先依次后根遍歷每棵子樹，然后訪問根結(jié)點(diǎn)按層次遍歷：先訪問第一層上的結(jié)點(diǎn)，然后依次遍歷第二層，第n層的結(jié)點(diǎn)第214頁/共354頁樹與森林的遍歷ABCDEFGHIJKLMNO先序遍歷：后序遍歷：層次遍歷：ABEF I GCDHJ KL NOMEI FGB CJK N OL M H D AA B CDE FGH I J K L MNO按廣度按深度第215頁/共354頁樹與森林的遍歷 二、森林 森林的遍歷即多棵樹的遍歷，單棵樹的遍歷與樹的遍歷相同，逐棵樹進(jìn)行遍歷。第216頁/共354頁 先序遍歷森林 若森林非空 先訪問第一棵樹的根結(jié)點(diǎn)， 再先序遍歷第一棵樹根的子森林， 再先序遍歷除去第一棵樹后剩余

37、 的子森林。 轉(zhuǎn)換成二叉樹后與二叉樹的先序遍歷相同樹與森林的遍歷第217頁/共354頁樹與森林的遍歷 中序遍歷森林 若森林非空 中序遍歷第一棵樹根的子森林 訪問第一棵樹的根 中序遍歷去掉第一棵樹后剩余的子森林 轉(zhuǎn)換成二叉樹后與二叉樹的中序遍歷相同第218頁/共354頁樹與森林的遍歷先序遍歷ABCDEFGH IJA B C D E F G H I J中序遍歷B C D A F E H J I G 森林的遍歷第219頁/共354頁先序遍歷ABCDEFGHIJ中序遍歷BCDAFEHJIG樹與森林的遍歷ABCDEFGH IJ 森林轉(zhuǎn)換成的二叉樹的遍歷第220頁/共354頁5.5 哈夫曼樹及應(yīng)用 定義

38、路徑：從樹中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支構(gòu)成這兩個(gè)結(jié)點(diǎn)間的路徑 路徑長(zhǎng)度：路徑上的分支數(shù) 樹的路徑長(zhǎng)度：從樹根到每一個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和 樹的帶權(quán)路徑長(zhǎng)度：樹中所有帶權(quán)結(jié)點(diǎn)的路徑長(zhǎng)度之和結(jié)點(diǎn)到根的路徑長(zhǎng)度權(quán)值其中：記作：kknkkklwlwwpl1哈夫曼樹(Huffman)帶權(quán)路徑長(zhǎng)度最短的樹第221頁/共354頁哈夫曼樹 Huffman樹設(shè)有n個(gè)權(quán)值w1,w2,wn，構(gòu)造一棵有n個(gè)葉子結(jié)點(diǎn)的二叉樹，每個(gè)葉子的權(quán)值為wi,則wpl最小的二叉樹叫Huffman樹。構(gòu)造Huffman樹的方法Huffman算法 構(gòu)造Huffman樹步驟 根據(jù)給定的n個(gè)權(quán)值w1,w2,wn，構(gòu)造n棵只有根結(jié)點(diǎn)的二叉

39、樹，令起權(quán)值為wj 在森林中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹作左右子樹，構(gòu)造一棵新的二叉樹，置新二叉樹根結(jié)點(diǎn)權(quán)值為其左右子樹根結(jié)點(diǎn)權(quán)值之和 在森林中刪除這兩棵樹，同時(shí)將新得到的二叉樹加入森林中 重復(fù)上述兩步，直到只含一棵樹為止，這棵樹即哈夫曼樹第222頁/共354頁哈夫曼樹例 有4個(gè)結(jié)點(diǎn)，權(quán)值分別為7，5，2，4，構(gòu)造有4個(gè)葉子結(jié)點(diǎn)的二叉樹abcd7524WPL=7*2+5*2+2*2+4*2=36dcab2475WPL=7*3+5*3+2*1+4*2=46WPL=7*1+5*2+2*3+4*3=35abcd7524nkKKLWWPL1要使二叉樹WPL小,就須在構(gòu)造樹時(shí), 將權(quán)值大的結(jié)點(diǎn)靠近根.第2

40、23頁/共354頁哈夫曼樹例a7b5c2d4a7b5c2d46a7b5c2d4611a7b5c2d461118構(gòu)造Huffman樹的方法Huffman算法第224頁/共354頁哈夫曼樹例 w=5, 29, 7, 8, 14, 23, 3, 1151429 7823 3 111429 7823 1135887151429233581111358191429238715113581929 23148715292914871529113581923421135819234229148715295811358192342291487152958100第225頁/共354頁哈夫曼編碼哈夫曼編碼 在進(jìn)行數(shù)

41、據(jù)通訊時(shí)，涉及數(shù)據(jù)編碼問題。所謂數(shù)據(jù)編碼就是數(shù)據(jù)與二進(jìn)制字符串的轉(zhuǎn)換。例如：郵局發(fā)電報(bào) 例 要傳輸?shù)脑臑锳BACCDA等長(zhǎng)編碼 A：00 B：01 C：10 D：11發(fā)送方：將ABACCDA 轉(zhuǎn)換成 接收方：將 還原為 ABACCDA不等長(zhǎng)編碼 A：0 B：00 C：1 D：01發(fā)送方：將ABACCDA 轉(zhuǎn)換成 000011010接收方：000011010 轉(zhuǎn)換成 A的編碼是B的前綴AAAACCDABBCCDA原文 電文（二進(jìn)制字符串） 原文發(fā)送方接收方第226頁/共354頁設(shè) A：0 B：110 C：10 D：111發(fā)送方：將 ABACCDA 轉(zhuǎn)換成 總長(zhǎng)度是13所得的譯碼是唯一的前綴編碼

42、： 任何字符編碼不是其它字符編碼的前綴哈夫曼編碼第227頁/共354頁哈夫曼編碼思想：根據(jù)字符出現(xiàn)頻率編碼，使電文總長(zhǎng)最短編碼：根據(jù)字符出現(xiàn)頻率構(gòu)造Huffman樹，然后將樹中結(jié)點(diǎn)引向其左孩子的分支標(biāo)“0”，引向其右孩子的分支標(biāo)“1”；每個(gè)字符的編碼即為從根到每個(gè)葉子的路徑上得到的0、1序列Huffman編碼：數(shù)據(jù)通信用的二進(jìn)制編碼第228頁/共354頁例 要傳輸?shù)淖址?D=C,A,S,T, ; 字符出現(xiàn)頻率 w=2,4,2,3,3CS3364224814T;A00110110T : 00; : 01A : 10C : 110S : 111哈夫曼編碼第229頁/共354頁哈夫曼編碼從Huff

43、man樹根開始，從待譯碼電文中逐位取碼。若編碼是“0”，則向左走；若編碼是“1”，則向右走，一旦到達(dá)葉子結(jié)點(diǎn)，則譯出一個(gè)字符；再重新從根出發(fā)，直到電文結(jié)束例 電文是CAS;CAT;SAT;AT 其編碼 “ 電文為“1101000” 譯文只能是“CAT”CS3364224814T;A00110110T : 00; : 01A : 10C : 110S : 111譯碼：第230頁/共354頁例 某通訊系統(tǒng)只使用8種字符a、b、c、d、e、f、g、h，其使用頻率分別為0.05, 0.29, 0.07, 0.08, 0.14, 0.23, 0.03, 0.11，利用二叉樹設(shè)計(jì)一種不等長(zhǎng)編碼 1）構(gòu)造以

44、 a、b、c、d、e、f、g、h為葉子結(jié)點(diǎn)的二叉樹； 2）將該二叉樹所有左分枝標(biāo)記1，所有右分枝標(biāo)記0； 3）從根到葉子結(jié)點(diǎn)路徑上標(biāo)記作為葉子結(jié)點(diǎn)所對(duì)應(yīng)字符的編碼；哈夫曼編碼第231頁/共354頁a: 0110b: 10c: 1110d: 1111e: 110f: 00g: 0111h: 01029195842100158 7 3 5 8 11231429構(gòu)造以字符使用頻率作為權(quán)值的哈夫曼樹如何得到使二進(jìn)制串總長(zhǎng)最短編碼哈夫曼編碼第232頁/共354頁第233頁/共354頁第章 圖 圖是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，具有多個(gè)直接前驅(qū)和后繼，為復(fù)雜的非線性結(jié)構(gòu)。圖的應(yīng)用已發(fā)展到諸如語言學(xué)、物理、邏輯學(xué)、化

45、學(xué)、電訊工程、計(jì)算機(jī)科學(xué)以及數(shù)學(xué)的各分支中。第234頁/共354頁6.1 圖的定義和術(shù)語圖：G = (V,E) V頂點(diǎn)的有窮、非空集合；E邊的集合有向圖：每條邊都有方向 無向圖：每條遍都沒有方向123G1123G2V(G1)=1,2,3E(G1)=, , V(G2)=1,2,3E(G2)=(1,2),(1,3), (2,3)(2,3)/(3,2)注意：不考慮到自身的邊和重復(fù)出現(xiàn)的邊第235頁/共354頁6.1 圖的定義和術(shù)語完全有向圖：任一頂點(diǎn)到其余n-1個(gè)頂點(diǎn)都有弧完全無向圖：任兩個(gè)頂點(diǎn)都有邊123完全有向圖123完全無向圖 思考：n個(gè)頂點(diǎn)的完全有向圖和完全無向圖個(gè)有多少條邊（?。﹏(n-1

46、)n(n-1)/2第236頁/共354頁6.1 圖的定義和術(shù)語稀疏圖：e= nlgn權(quán)值：給邊/弧賦一個(gè)數(shù) 網(wǎng)：帶權(quán)的圖子圖：G(V,E),G(V,E),若V V,E E,則G是G的子圖鄰接與關(guān)聯(lián)a.有向圖 若vi,vj, vi vj， vi,vj關(guān)聯(lián)于vi,vj；b.無向圖 若（vi,vj）, vi，vj互為鄰接點(diǎn)， （vi,vj）關(guān)聯(lián)于vi,vj；鄰接到鄰接于第237頁/共354頁6.1 圖的定義和術(shù)語頂點(diǎn)的度：關(guān)聯(lián)于該點(diǎn)的邊的數(shù)目 有向圖 路徑：vi vj,vj vk, , vg，則稱（ vi,vj，vk, , vg）為vi 到vg的路徑路徑長(zhǎng)度：路徑所經(jīng)過邊的數(shù)目簡(jiǎn)單路徑：路徑中中間結(jié)

47、點(diǎn)不重復(fù)回路或環(huán)：起點(diǎn)和終點(diǎn)相同的路徑出度：出邊的數(shù)目入度：入邊的數(shù)目頂點(diǎn)數(shù)邊數(shù):)(211nevDenii簡(jiǎn)單環(huán)第238頁/共354頁6.1 圖的定義和術(shù)語強(qiáng)連通圖（有向圖）：jijivvvv 到達(dá);,123強(qiáng)連通分量：有向圖中的極大連通子圖連通圖（無向圖）：都是連通的。jijivvvv;,連通分量：無向圖中的極大連通子圖3123第239頁/共354頁6.2 圖的存儲(chǔ)方式一、鄰接矩陣 N個(gè)頂點(diǎn)的圖 Ann矩陣1,0)(,), 0)(,), 1,njiGEvjvivjviGEvjvivjvijiA或，若（或，若（12340011000140011110第240頁/共354頁6.2 圖的存儲(chǔ)方式

48、無向圖：對(duì)稱方陣，每行（列）的非零元素個(gè)數(shù)為頂點(diǎn)的度有向圖：行非零元素個(gè)數(shù)出度 列非零元素個(gè)數(shù)入度1234001100014001111012340001000010000110第241頁/共354頁6.2 圖的存儲(chǔ)方式鄰接矩陣定義：Typedef structvextype vexsn; /頂點(diǎn)adjtype arcsnn; /矩陣Graph;第242頁/共354頁6.2 圖的存儲(chǔ)方式建立無向網(wǎng)算法：CREATGRAPH(Graph * g)for(i=0;ivexsi=getchar();/讀入頂點(diǎn)信息for(i=0;in;i+)for(j=0;jarcsij=0;/矩陣初始化for(k=

49、0;karcsij=w; g-arcsji=w;O(n+n2+e) O(n2)思考：若為有向圖應(yīng)該如何改第243頁/共354頁6.2 圖的存儲(chǔ)方式二、鄰接鏈表 對(duì)應(yīng)每個(gè)頂點(diǎn)建立一條單鏈表，表上結(jié)點(diǎn)表示該結(jié)點(diǎn)的鄰接點(diǎn)。 頂點(diǎn)信息指向鏈表頂點(diǎn)序號(hào)指向下一結(jié)點(diǎn)第244頁/共354頁6.2 圖的存儲(chǔ)方式12341234無向圖G1有向圖G24321432421110 1 2 3432132410 1 2 3鄰接鏈表思考：在鏈表中如何確定頂點(diǎn)的度？第245頁/共354頁4321432421110 1 2 31234無向圖G17.2 圖的存儲(chǔ)方式在無向圖的鄰接鏈表中頂點(diǎn)的度即為該頂點(diǎn)在所有鏈表中出現(xiàn)次數(shù)。6

50、.2 圖的存儲(chǔ)方式無向圖的鄰接鏈表第246頁/共354頁1234有向圖G2432132410 1 2 36.2 圖的存儲(chǔ)方式在有向圖的鄰接鏈表中： 頂點(diǎn)的出度：該頂點(diǎn)在對(duì)應(yīng)鏈表結(jié)點(diǎn)數(shù)；頂點(diǎn)的入度：結(jié)點(diǎn)序號(hào)在所有鏈表中出現(xiàn)次數(shù)；有向圖的鄰接鏈表第247頁/共354頁6.2 圖的存儲(chǔ)方式1234有向圖G2在有向圖的逆鄰接鏈表中： 頂點(diǎn)的入度：該頂點(diǎn)在對(duì)應(yīng)鏈表結(jié)點(diǎn)數(shù)；頂點(diǎn)的出度：結(jié)點(diǎn)序號(hào)在所有鏈表中出現(xiàn)次數(shù)；有向圖的逆鄰接鏈表41432120 1 2 31第248頁/共354頁6.2 圖的存儲(chǔ)方式 在圖的存儲(chǔ)方式中，以上所學(xué)習(xí)鄰接矩陣和鄰接鏈表是最主要的方式。除此以外還有十字鏈表、鄰接多重表等方式，

51、這里就不一一列舉。 注意：鄰接矩陣表示唯一；鄰接鏈表形態(tài)于邊的輸入次序有關(guān)。第249頁/共354頁6.3 圖的遍歷 圖的遍歷是指沿某條路經(jīng)，對(duì)所有結(jié)點(diǎn)進(jìn)行訪問且每個(gè)結(jié)點(diǎn)只訪問一次。已訪問；未訪問；設(shè)置iivvivisited10圖存在回路重復(fù)訪問1234第250頁/共354頁6.3 圖的遍歷一、深度優(yōu)先搜索（DFS） 類似于樹的先序遍歷，即碰到就訪問。12345142856379101 2 5 3 41 2 4 8 5 3 6 7 9 10第251頁/共354頁6.3 圖的遍歷圖的深度優(yōu)先遍歷算法1（基于鄰接矩陣）DFA(Graph g,int i)visit(g.vexsi);visited

52、i=1;/訪問i頂點(diǎn),并把標(biāo)志置為已訪問for(j=0;jadjvex=0)/若當(dāng)前頂點(diǎn)未訪問DFSL(g,p-adjvex);p=p-next;注：只能遍歷一個(gè)連通分量時(shí)間復(fù)雜度：O(n2) 空間復(fù)雜度：O(n)棧與visitedn第253頁/共354頁6.3 圖的遍歷同一個(gè)圖可以有多種形式的鄰接表 多個(gè)遍歷序列 1234432132410 1 2 3432123410 1 2 3遍歷序列1：1 3 2 4遍歷序列2：1 2 4 3第254頁/共354頁6.3 圖的遍歷問題思考： 前面所講的算法都是只能遍歷一個(gè)連通分量，若對(duì)于具有多個(gè)連通分量的圖應(yīng)該如何遍歷呢255

53、頁/共354頁6.3 圖的遍歷多個(gè)連通分量圖的遍歷算法：void DFS(Graph g,int v)for(j=0;jn;j+) visitedj=0;/標(biāo)志數(shù)組初始化for(j=0;jn;j+) /以未訪問頂點(diǎn)為出發(fā)點(diǎn)遍歷所在連通分量if(!visitedj) DFA(g,j);第256頁/共354頁6.3 圖的遍歷二、廣度優(yōu)先搜索（BFS） 類似于樹的按層次遍歷12345142856379101 2 4 5 31 2 3 4 5 6 7 8 9 10第257頁/共354頁6.3 圖的遍歷訪問一個(gè)頂點(diǎn)BFS算法思想： 訪問其未被訪問的鄰接點(diǎn)1、訪問上一層中第一個(gè)被訪問頂點(diǎn)的未訪問鄰接點(diǎn)2、

54、訪問上一層中第二個(gè)被訪問頂點(diǎn)的未訪問鄰接點(diǎn)n、訪問上一層中第n個(gè)被訪問頂點(diǎn)的未訪問鄰接點(diǎn)第258頁/共354頁6.3 圖的遍歷v引入隊(duì)列，頂點(diǎn)訪問過后即將其入隊(duì)，每次出隊(duì)一個(gè)頂點(diǎn)并訪問其未訪問之鄰接點(diǎn)12345124455331 2543序列：第259頁/共354頁6.3 圖的遍歷廣度優(yōu)先遍歷算法：BFS(Graph g,int i)for(v=0;vn;v+) visitedv=0;InitQueue(Q);for(v=0;vadjvex)EnQueue(Q,p-adjvex); visit(gp-adjvex.vextex); visitedp-adjvex = 1;p=p-next;第2

55、60頁/共354頁6.3 圖的遍歷1234514285637910圖的遍歷小結(jié)：DFS序列：1 2 5 3 4BFS序列：1 2 4 5 3DFS序列：1 2 4 8 5 3 6 7 9 10BFS序列：1 2 3 4 5 6 7 8 9 10第261頁/共354頁6.4 圖的連通性問題一、圖的連通分量 由于調(diào)用一次DFS算法或BFS算法可以對(duì)一個(gè)連通分量進(jìn)行遍歷，所以只要在求多連通分量圖的連通分量個(gè)數(shù)時(shí)只要計(jì)算算法的調(diào)用次數(shù)就行了。int DFS_NUM(Graph g,int v) int count=0;for(j=0;jn;j+) visitedj=0;/標(biāo)志數(shù)組初始化for(j=0;

56、jn;j+) if(!visitedj) DFA(g,j);count+;return (count);第262頁/共354頁6.4 圖的連通性問題二、生成樹和最小生成樹樹無回路的連通圖生成樹：連通圖的極小連通子圖（n個(gè)頂點(diǎn)，n-1條邊）12345123451234512345第263頁/共354頁6.4 圖的連通性問題12345DFS生成樹：由DFS算法遍歷所得生成樹BFS生成樹：由BFS算法遍歷所得生成樹12345DFS生成樹12345BFS生成樹第264頁/共354頁6.4 圖的連通性問題v連通網(wǎng)：各邊帶權(quán)的連通圖；其生成樹權(quán)值為各邊權(quán) 值之和。v最小生成樹：連通網(wǎng)所有生成樹中權(quán)值最小的

57、生成樹。12345最小生成樹111112345非最小生成樹121312345121311連通網(wǎng)第265頁/共354頁6.4 圖的連通性問題vMST（MiniCost Spanning Tree)性質(zhì): 假設(shè)N=(V,E)是一個(gè)連通網(wǎng)，U是頂點(diǎn)集V的一個(gè)非空子集。若（u，v）是一條權(quán)值最小的邊，其中 ,則必存在一棵包含（u，v）的最小生成樹。UVvUu,6155654362123456第266頁/共354頁6.4 圖的連通性問題1、普里姆（Prim算法)取所有已訪問點(diǎn)與未訪問點(diǎn)之連邊中權(quán)值最小者，再將此邊關(guān)聯(lián)之未訪問點(diǎn)變?yōu)橐言L問點(diǎn)，重復(fù)直到無未訪問點(diǎn)。6155654362123456第267頁/

58、共354頁6.4 圖的連通性問題1、普里姆（Prim算法)6155654362123456112345611234564112345645211234564211234564523第268頁/共354頁6.4 圖的連通性問題1、普里姆（Prim算法)6155654362123456112345611234564112345645211234564211234564523第269頁/共354頁6.4 圖的連通性問題 普里姆（Prim算法)數(shù)組變化情況a、U=1,TE=;123456112345611234564112345645211234564211234564523b、U=1,3,TE=(1

59、,3);c、U=1,3,6,TE=(1,3),(3,6);d、U=1,3,6,4,TE=(1,3),(3,6),(6,4);e、U=1,3,6,4,2,TE=(1,3),(3,6),(6,4),(3,2);f 、U=1,3,6,4,2,5,TE=(1,3),(3,6),(6,4),(3,2),(2,5);第270頁/共354頁6.4 圖的連通性問題2、克魯斯卡爾算法（Kruskal算法)6155654362123456具體方法：將n個(gè)單獨(dú)的頂點(diǎn)加入T ，每個(gè)頂點(diǎn)是一個(gè)連通分量。在E中取權(quán)值最小而處于不同連通分量的邊，加入T。依次類推，直到T中所有頂點(diǎn)連通。第271頁/共354頁6.4 圖的連通

60、性問題2、克魯斯卡爾算法（Kruskal算法)6155654362123456112345611234562112345623112345623411234562345第272頁/共354頁6.4 圖的連通性問題2、克魯斯卡爾算法（Kruskal算法)6155654362123456112345611234562112345623112345623411234562345第273頁/共354頁6.4 圖的連通性問題最小生成樹的兩種求法比較：普里姆（Prim算法)時(shí)間復(fù)雜度：O(n2) 時(shí)間復(fù)雜度與邊數(shù)無關(guān)，適合于邊稠密網(wǎng)；克魯斯卡爾算法（Kruskal算法)時(shí)間復(fù)雜度：O(eloge) 時(shí)間復(fù)