數(shù)據(jù)結(jié)構(gòu)（Java版）課件 呂云翔 第6、7章 圖、排序

第6章圖目錄2第6.1節(jié)第6.2節(jié)第6.3節(jié)第6.4節(jié)第6.5節(jié)第6.6節(jié)圖概述圖的存儲(chǔ)結(jié)構(gòu)圖的遍歷最小生成樹(shù)最短路徑拓?fù)渑判蚝完P(guān)鍵路徑6.1圖概述6.1.1圖的基本概念6.1.2圖的抽象數(shù)據(jù)類(lèi)型描述圖概述在離散數(shù)學(xué)中，圖論研究圖的純數(shù)學(xué)性質(zhì)；在數(shù)據(jù)結(jié)構(gòu)中，圖結(jié)構(gòu)研究計(jì)算機(jī)中如何存儲(chǔ)圖以及如何實(shí)現(xiàn)圖的操作和應(yīng)用。圖是刻畫(huà)離散結(jié)構(gòu)的一種有力工具。在運(yùn)籌規(guī)劃、網(wǎng)絡(luò)研究和計(jì)算機(jī)程序流程分析中都存在圖的應(yīng)用問(wèn)題。我們也經(jīng)常用圖來(lái)表達(dá)文字難以描述的信息，如城市交通圖、鐵路網(wǎng)等。4網(wǎng)絡(luò)研究運(yùn)籌規(guī)劃程序流程分析描述信息圖的基本概念圖是一種數(shù)據(jù)元素間具有“多對(duì)多”關(guān)系的非線性數(shù)據(jù)結(jié)構(gòu)，由頂點(diǎn)集V和邊集E組成，記作G=(V,E)。其中V是有窮非空集合，v∈V稱(chēng)為頂點(diǎn)；E是有窮集合，e∈E稱(chēng)為邊。

5

圖的基本概念6線性結(jié)構(gòu)樹(shù)“一對(duì)一”的線性關(guān)系“一對(duì)多”的層次關(guān)系每一個(gè)數(shù)據(jù)元素都可以和其他的任意數(shù)據(jù)元素相關(guān)。每個(gè)元素可以有多個(gè)前驅(qū)元素和多個(gè)后繼元素，任意兩個(gè)元素可以相鄰。與線性結(jié)構(gòu)和樹(shù)相比圖更為復(fù)雜圖圖的基本概念7e=(u,v)表示頂點(diǎn)u和頂點(diǎn)v間的一條無(wú)向邊，也可以簡(jiǎn)稱(chēng)為邊。(u,v)間沒(méi)有方向，即(u,v)和(v,u)是相同的。e=<u,v>表示頂點(diǎn)u到頂點(diǎn)v間的一條有向邊，也叫弧。u叫始點(diǎn)或弧尾，v叫終點(diǎn)或弧頭。<u,v>是有方向的，因此<u,v>和<v,u>是不同的。零圖是指E為空集的圖，也就是圖中只有頂點(diǎn)存在，沒(méi)有邊。030102無(wú)向邊有向邊零圖

圖的基本概念8無(wú)向圖指全部由無(wú)向邊構(gòu)成的圖。有向圖指全部由有向邊構(gòu)成的圖。完全圖是指邊數(shù)達(dá)到最大值的圖，即在頂點(diǎn)數(shù)為n的無(wú)向圖中邊數(shù)為n(n-1)2，在頂點(diǎn)數(shù)為n的有向圖中邊數(shù)為n(n-1)。040506無(wú)向圖有向圖圖的基本概念907.稠密圖稠密圖是指邊數(shù)較少的圖，如e<nlog2n，反之則為稀疏圖。08.子圖設(shè)有兩個(gè)圖G=(V,E)和G′=(V′,E′)，如果有V′?V和E′?E，則稱(chēng)G′是G的子圖，記作G′?G。09.生成子圖如果G′=(V′,E′)是G=(V,E)的子圖，并且V′=V，則稱(chēng)G′是G的生成子圖。10.鄰接點(diǎn)在一個(gè)無(wú)向圖中若存在邊(u,v)，則稱(chēng)頂點(diǎn)u和v互為鄰接點(diǎn)。邊(u,v)是頂點(diǎn)u和v關(guān)聯(lián)的邊，頂點(diǎn)u和v是邊(u,v)關(guān)聯(lián)的頂點(diǎn)。圖的基本概念10R111213頂點(diǎn)的度頂點(diǎn)的度是指與該頂點(diǎn)關(guān)聯(lián)的邊的數(shù)目。頂點(diǎn)u的度記作D(u)。在有向圖中頂點(diǎn)的度有入度和出度兩種。對(duì)于頂點(diǎn)u，入度指的是以u(píng)為終點(diǎn)的弧的數(shù)目，記為ID(u)；出度指的是以u(píng)為起點(diǎn)的弧的數(shù)目，記為OD(u)。全部頂點(diǎn)的度之和為邊數(shù)的兩倍。路徑路徑是指從頂點(diǎn)u到頂點(diǎn)v所經(jīng)過(guò)的頂點(diǎn)序列。路徑長(zhǎng)度是指路徑上邊的數(shù)目。沒(méi)有頂點(diǎn)重復(fù)出現(xiàn)的路徑叫初等路徑?；芈返谝粋€(gè)和最后一個(gè)頂點(diǎn)相同的路徑稱(chēng)為回路或環(huán)，除了第一個(gè)和最后一個(gè)頂點(diǎn)以外，其他頂點(diǎn)都不重復(fù)出現(xiàn)的回路叫初等回路。圖的基本概念11連通分量是指無(wú)向圖中的極大連通子圖。15連通分量強(qiáng)連通分量是指有向圖中的極大連通子圖。17強(qiáng)連通分量在有向圖中若任意兩個(gè)頂點(diǎn)均是連通的，則稱(chēng)該圖為強(qiáng)連通圖。16強(qiáng)連通圖在無(wú)向圖中若頂點(diǎn)u和頂點(diǎn)v間有路徑，則稱(chēng)u和v是連通的。連通圖是指任意兩個(gè)頂點(diǎn)均是連通的圖。14連通圖

強(qiáng)連通圖強(qiáng)連通分量連通分量連通圖圖的基本概念1218.生成樹(shù)和生成森林生成樹(shù)是指包含圖中的全部頂點(diǎn)，但只有構(gòu)成樹(shù)的n-1條邊的生成子圖。對(duì)于非連通圖，每個(gè)連通分量可形成一棵生成樹(shù)，所有生成樹(shù)組成的集合叫該非連通圖的生成森林。19.網(wǎng)網(wǎng)指的是邊上帶有權(quán)值的圖。通常權(quán)為非負(fù)實(shí)數(shù)，可以表示從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的距離、時(shí)間和代價(jià)等。圖的抽象數(shù)據(jù)類(lèi)型描述13圖的抽象數(shù)據(jù)類(lèi)型用Java抽象類(lèi)描述如下：6.2圖的存儲(chǔ)結(jié)構(gòu)6.2.1鄰接矩陣6.2.2鄰接表圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu)需要存儲(chǔ)頂點(diǎn)的值以及與頂點(diǎn)相關(guān)聯(lián)的頂點(diǎn)和邊的信息。頂點(diǎn)間沒(méi)有次序關(guān)系，各條邊之間也沒(méi)有次序關(guān)系，但是表示和存儲(chǔ)一個(gè)圖必須約定好頂點(diǎn)次序。邊集合表達(dá)每對(duì)頂點(diǎn)間的鄰接關(guān)系，是二維線性關(guān)系。圖的存儲(chǔ)結(jié)構(gòu)可用矩陣來(lái)形容。15

鄰接矩陣矩陣的存儲(chǔ)結(jié)構(gòu)常見(jiàn)有鄰接矩陣、鄰接表、十字鏈表3種。

鄰接表

十字鏈表圖的存儲(chǔ)結(jié)構(gòu)邊采用順序存儲(chǔ)結(jié)構(gòu)，用二維數(shù)組存儲(chǔ)，稱(chēng)為圖的鄰接矩陣。邊采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，存儲(chǔ)行的后繼，即矩陣行的單鏈表，稱(chēng)為圖的鄰接表。邊采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，存儲(chǔ)行和列的后繼，即矩陣十字鏈表，稱(chēng)為圖的鄰接多重表。16鄰接矩陣——存儲(chǔ)結(jié)構(gòu)17

分析可得，在無(wú)向圖的鄰接矩陣中第i行或者第i列的非零元素的個(gè)數(shù)為第i個(gè)頂點(diǎn)的度；在有向圖的鄰接矩陣中第i行的非∞元素的個(gè)數(shù)為第i個(gè)頂點(diǎn)的出度，第i列非∞元素的個(gè)數(shù)為第i個(gè)頂點(diǎn)的入度。無(wú)向圖的鄰接矩陣是對(duì)稱(chēng)的，有向圖的鄰接矩陣不一定是對(duì)稱(chēng)的。

鄰接矩陣圖的鄰接矩陣可以用二維數(shù)組進(jìn)行表示，鄰接矩陣類(lèi)的Java語(yǔ)言描述如右圖：18鄰接矩陣2.圖的鄰接矩陣類(lèi)的基本操作的實(shí)現(xiàn)1)圖的創(chuàng)建【算法6.1】創(chuàng)建無(wú)向圖【算法6.2】創(chuàng)建有向圖19鄰接矩陣2.圖的鄰接矩陣類(lèi)的基本操作的實(shí)現(xiàn)1)圖的創(chuàng)建【算法6.3】創(chuàng)建無(wú)向網(wǎng)20鄰接矩陣2.圖的鄰接矩陣類(lèi)的基本操作的實(shí)現(xiàn)1)圖的創(chuàng)建【算法6.4】創(chuàng)建有向網(wǎng)21鄰接矩陣222.圖的鄰接矩陣類(lèi)的基本操作的實(shí)現(xiàn)2)頂點(diǎn)的定位頂點(diǎn)定位算法locateVex(x)是根據(jù)x的值取得其在頂點(diǎn)集中的位置，若不存在則返回-1?！舅惴?.5】頂點(diǎn)的定位。鄰接矩陣232.圖的鄰接矩陣類(lèi)的基本操作的實(shí)現(xiàn)3)查找第一個(gè)鄰接點(diǎn)查找第一個(gè)鄰接點(diǎn)算法firstAdj(i)是指給定一個(gè)頂點(diǎn)在頂點(diǎn)集中的位置i，返回其第一個(gè)鄰接點(diǎn)，若不存在則返回-1?！舅惴?.6】查找第一個(gè)鄰接點(diǎn)。鄰接矩陣242.圖的鄰接矩陣類(lèi)的基本操作的實(shí)現(xiàn)4)查找下一個(gè)鄰接點(diǎn)查找下一個(gè)鄰接點(diǎn)算法nextAdj(i,j)是指給定兩個(gè)頂點(diǎn)在頂點(diǎn)集中的位置i、j，第j個(gè)頂點(diǎn)是第i個(gè)頂點(diǎn)的鄰接點(diǎn)，返回第j個(gè)頂點(diǎn)之后的下一個(gè)鄰接點(diǎn)，若不存在則返回-1。【算法6.7】查找下一個(gè)鄰接點(diǎn)。鄰接矩陣——性能分析2501圖的鄰接矩陣表示存儲(chǔ)了任意兩個(gè)頂點(diǎn)間的鄰接關(guān)系或邊的權(quán)值，能夠?qū)崿F(xiàn)對(duì)圖的各種操作，其中判斷兩個(gè)頂點(diǎn)間是否有邊相連、獲得和設(shè)置邊的權(quán)值等操作的時(shí)間復(fù)雜度為O(1)。02但是，與順序表存儲(chǔ)線性表的性能相似，由于采用數(shù)組存儲(chǔ)，每插入或者刪除一個(gè)元素需要移動(dòng)大量元素，使得插入和刪除操作的效率很低，而且數(shù)組容量有限，當(dāng)擴(kuò)充容量時(shí)需要復(fù)制全部元素，效率更低。在圖的鄰接矩陣中每個(gè)矩陣元素表示兩個(gè)頂點(diǎn)間的鄰接關(guān)系，無(wú)邊或有邊。即使兩個(gè)頂點(diǎn)之間沒(méi)有鄰接關(guān)系，也占用一個(gè)存儲(chǔ)單元存儲(chǔ)0或者-1。對(duì)于一個(gè)有n個(gè)頂點(diǎn)的完全圖，其鄰接矩陣有n(n-1)/2個(gè)元素，此時(shí)鄰接矩陣的存儲(chǔ)效率較高；當(dāng)圖中的邊數(shù)較少時(shí)，鄰接矩陣變得稀疏，存儲(chǔ)效率較低，此時(shí)可用圖的鄰接表進(jìn)行存儲(chǔ)。何時(shí)選擇鄰接矩陣？鄰接矩陣26【例6.1】n個(gè)頂點(diǎn)的無(wú)向圖采用鄰接矩陣存儲(chǔ)，回答下列問(wèn)題：（1）圖中有多少條邊？（2）任意兩個(gè)頂點(diǎn)i和j之間是否有邊相連？（3）任意一個(gè)頂點(diǎn)的度是多少？解：（1）鄰接矩陣中非零元素個(gè)數(shù)的總和除以2。（2）當(dāng)鄰接矩陣A中A[i][j]=1(或A[j][i]=1)時(shí)表示兩頂點(diǎn)之間有邊相連。（3）計(jì)算鄰接矩陣上該頂點(diǎn)對(duì)應(yīng)的行上非零元素的個(gè)數(shù)。鄰接表271.圖的鄰接表存儲(chǔ)結(jié)構(gòu)鄰接表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)圖，是由一個(gè)順序存儲(chǔ)的頂點(diǎn)表和多個(gè)鏈?zhǔn)酱鎯?chǔ)的邊表組成的。邊表的個(gè)數(shù)和圖的頂點(diǎn)數(shù)相同。頂點(diǎn)表由頂點(diǎn)結(jié)點(diǎn)組成，每個(gè)頂點(diǎn)結(jié)點(diǎn)又由數(shù)據(jù)域和指針域組成，其中數(shù)據(jù)域data存放頂點(diǎn)值，指針域firstArc指向邊表中的第一個(gè)邊結(jié)點(diǎn)。邊表由邊結(jié)點(diǎn)組成，每個(gè)邊結(jié)點(diǎn)又由adjVex、nextArc、value幾個(gè)域組成，其中value存放邊的信息，例如權(quán)值；adjVex存放與結(jié)點(diǎn)鄰接的頂點(diǎn)在圖中的位置；nextArc指向下一個(gè)邊結(jié)點(diǎn)。鄰接表頂點(diǎn)結(jié)點(diǎn)類(lèi)的描述鄰接表的頂點(diǎn)結(jié)點(diǎn)類(lèi)的Java描述如下：28鄰接表邊結(jié)點(diǎn)類(lèi)的描述鄰接表的邊結(jié)點(diǎn)類(lèi)的Java描述如下：29鄰接表30鄰接表類(lèi)的描述圖的鄰接表類(lèi)的描述如下：鄰接表31鄰接表2.圖的鄰接表的基本操作的實(shí)現(xiàn)1)圖的創(chuàng)建【算法6.8】創(chuàng)建無(wú)向圖【算法6.9】創(chuàng)建有向圖32鄰接表2.圖的鄰接表的基本操作的實(shí)現(xiàn)1)圖的創(chuàng)建【算法6.10】創(chuàng)建無(wú)向網(wǎng)33鄰接表2.圖的鄰接表的基本操作的實(shí)現(xiàn)1)圖的創(chuàng)建【算法6.11】創(chuàng)建有向網(wǎng)34鄰接表352.圖的鄰接表的基本操作的實(shí)現(xiàn)2)在圖中插入邊結(jié)點(diǎn)插入邊結(jié)點(diǎn)的算法addArc(i,j,value)是指在邊鏈表中加入一個(gè)由第i個(gè)頂點(diǎn)指向第j個(gè)頂點(diǎn)的權(quán)值為value的邊結(jié)點(diǎn)，采用頭插法進(jìn)行插入?！舅惴?.12】插入邊結(jié)點(diǎn)。鄰接表363)查找第一個(gè)鄰接點(diǎn)【算法6.13】查找第一個(gè)鄰接點(diǎn)。4)查找下一個(gè)鄰接點(diǎn)【算法6.14】查找下一個(gè)鄰接點(diǎn)。鄰接表37用鄰接矩陣存儲(chǔ)圖可以很好地確定兩個(gè)頂點(diǎn)間是否有邊，但是查找頂點(diǎn)的鄰接點(diǎn)，需要訪問(wèn)對(duì)應(yīng)一行或一列的所有數(shù)據(jù)元素，并且無(wú)論兩個(gè)頂點(diǎn)間是否有邊都要保留存儲(chǔ)空間。用鄰接表存儲(chǔ)圖可以方便地找到頂點(diǎn)的鄰接點(diǎn)，對(duì)于稀疏圖來(lái)說(shuō)節(jié)省存儲(chǔ)空間，但若要確定兩個(gè)頂點(diǎn)間是否有邊相連則需要遍歷單鏈表，比鄰接矩陣復(fù)雜。6.3圖的遍歷6.3圖的遍歷-問(wèn)題描述圖的遍歷是指從圖的任意一個(gè)頂點(diǎn)出發(fā)對(duì)圖的每個(gè)頂點(diǎn)訪問(wèn)且僅訪問(wèn)一次的過(guò)程，因?yàn)閳D中可能存在回路，為了避免對(duì)一個(gè)頂點(diǎn)的重復(fù)訪問(wèn)可以增設(shè)一個(gè)輔助數(shù)組visited[0...n-1]，全部初始化為0，一旦第i個(gè)頂點(diǎn)被訪問(wèn)，置visited[i]=1。圖的遍歷和樹(shù)的遍歷相比更加復(fù)雜，需要考慮以下3個(gè)問(wèn)題。(1)指定遍歷的第一個(gè)頂點(diǎn)。(2)由于一個(gè)頂點(diǎn)和多個(gè)頂點(diǎn)相鄰，需要在多個(gè)鄰接頂點(diǎn)間確定訪問(wèn)次序。(3)由于圖中存在回路，必須對(duì)訪問(wèn)過(guò)的頂點(diǎn)做標(biāo)記，防止出現(xiàn)重復(fù)訪問(wèn)同一頂點(diǎn)的情況。396.3圖的遍歷-遍歷方法遍歷方法廣度優(yōu)先搜索深度優(yōu)先搜索406.3圖的遍歷-廣度優(yōu)先搜索0102030405建立訪問(wèn)標(biāo)識(shí)數(shù)組visited[n]并初始化為0,n為圖頂點(diǎn)的個(gè)數(shù)隊(duì)列初始化訪問(wèn)所有臨界點(diǎn)重復(fù)步驟(3)，直到隊(duì)列為空。改變i值，0≤i<n，跳到步驟(2)繼續(xù)進(jìn)行，直到i=n-1訪問(wèn)所有頂點(diǎn)將隊(duì)首元素頂點(diǎn)vi從隊(duì)列中取出，依次訪問(wèn)它的未被訪問(wèn)的鄰接點(diǎn)vj、vk、…，并將其入隊(duì)。取出頂點(diǎn)，添加鄰接點(diǎn)添加未訪問(wèn)頂點(diǎn)將未訪問(wèn)頂點(diǎn)vi入隊(duì)416.3圖的遍歷-廣度優(yōu)先搜索算法展示426.3圖的遍歷-深度優(yōu)先搜索01020304以未訪問(wèn)頂點(diǎn)vi為起始點(diǎn)訪問(wèn)其未訪問(wèn)鄰接點(diǎn)vj頂點(diǎn)入隊(duì)，訪問(wèn)其臨界點(diǎn)從vj出發(fā)遞歸進(jìn)行步驟(2)，直到所有鄰接點(diǎn)均被訪問(wèn)訪問(wèn)所有臨界點(diǎn)改變i值，0≤i<n，跳到步驟(2)繼續(xù)進(jìn)行，直到i=n-1訪問(wèn)所有頂點(diǎn)建立訪問(wèn)標(biāo)識(shí)數(shù)組visited[n]并初始化為0,n為圖頂點(diǎn)的個(gè)數(shù)隊(duì)列初始化436.3圖的遍歷-深度優(yōu)先搜索算法展示446.3圖的遍歷-廣度度優(yōu)先搜索算法應(yīng)用【例6.2】編程利用廣度優(yōu)先搜索算法確定無(wú)向圖的連通分量。456.3圖的遍歷-廣度優(yōu)先搜索算法應(yīng)用【例6.2】編程利用廣度優(yōu)先搜索算法確定無(wú)向圖的連通分量。第1個(gè)連通塊：123第2個(gè)連通塊：45第3個(gè)連通塊：6466.3圖的遍歷-遍歷算法應(yīng)用【例6.3】已知一個(gè)連通圖如下所示，試給出圖的鄰接矩陣和鄰接表存儲(chǔ)示意圖，若從頂點(diǎn)v1出發(fā)對(duì)該圖進(jìn)行遍歷，分別給出一個(gè)按深度優(yōu)先遍歷和廣度優(yōu)先遍歷的頂點(diǎn)序列。476.3圖的遍歷-遍歷算法應(yīng)用【例6.3】解：深度優(yōu)先遍歷序列：v1v2v3v4v5v6廣度優(yōu)先遍歷序列：v1v2v4v6v3v5鄰接矩陣和鄰接表表示如左圖所示。

486.3圖的遍歷-遍歷算法應(yīng)用【例6.4】已知無(wú)向圖G的鄰接表如圖所示，分別寫(xiě)出從頂點(diǎn)1出發(fā)的深度遍歷和廣度遍歷序列，并畫(huà)出相應(yīng)的生成樹(shù)。49【例6.4】解：由章節(jié)給出的算法可知深度優(yōu)先遍歷序列為1，2，3，4，5，6。對(duì)應(yīng)的生成樹(shù)如圖所示。廣度優(yōu)先遍歷序列為1，2，4，3，5，6。對(duì)應(yīng)的生成樹(shù)如圖所示。深度優(yōu)先遍歷序列對(duì)應(yīng)的生成樹(shù)廣度優(yōu)先遍歷序列對(duì)應(yīng)的生成樹(shù)6.3圖的遍歷-遍歷算法應(yīng)用506.3圖的遍歷-遍歷算法應(yīng)用【例6.5】假設(shè)有如圖所示的有向網(wǎng)圖，利用Dijkstra算法求從頂點(diǎn)v1到其他各頂點(diǎn)的最短路徑。51【例6.5】解：從源點(diǎn)v1到其他各頂點(diǎn)的最短路徑如表所示。源點(diǎn)終點(diǎn)最短路徑最短路徑長(zhǎng)度v1v1v1v1v1v3v5v2v6v4v1v3v1v5v1v3v2v1v3v2v6v1v3v2v415152540456.3圖的遍歷-遍歷算法應(yīng)用526.3圖的遍歷-遍歷算法應(yīng)用【例6.6】編寫(xiě)程序?qū)崿F(xiàn)如圖所示的連通無(wú)向網(wǎng)的最小生成樹(shù)。53[['A','D'],['D','F'],['F','C'],['D','B'],['B','E']]6.3圖的遍歷-遍歷算法應(yīng)用輸出：546.4最小生成樹(shù)6.4.1最小生成樹(shù)的基本概念6.4.2Kruskal算法6.4.3Prim算法6.4.1最小生成樹(shù)的概念01連通圖的生成樹(shù)是圖的極小連通子圖，它包含圖中的全部頂點(diǎn)，但只有構(gòu)成一棵樹(shù)的邊。一個(gè)有n個(gè)頂點(diǎn)的連通圖的生成樹(shù)只有n-1條邊。若有n個(gè)頂點(diǎn)而少于n-1條邊，則為非連通圖，若多于n-1條邊，則一定形成回路。根據(jù)生成算法不同又分為廣度優(yōu)先生成樹(shù)和深度優(yōu)先生成樹(shù)。連通圖的生成樹(shù)02對(duì)于非連通圖，每個(gè)連通分量中的頂點(diǎn)集和遍歷經(jīng)過(guò)的邊一起構(gòu)成若干棵生成樹(shù)，共同組成了該非連通圖的生成森林。生成森林03在一個(gè)網(wǎng)的所有生成樹(shù)中權(quán)值總和最小的生成樹(shù)稱(chēng)為最小代價(jià)生成樹(shù)，簡(jiǎn)稱(chēng)為最小生成樹(shù)最小生成樹(shù)566.4.1最小生成樹(shù)的概念具有n個(gè)頂點(diǎn)和n-1條邊01只能使用圖中的邊構(gòu)造最小生成樹(shù)02不能使用產(chǎn)生回路的邊03最小生成樹(shù)3大原則576.4.2Kruskal算法算法原理：Kruskal算法是依次找出權(quán)值最小的邊建立最小生成樹(shù)，每次新增的邊不能使生成樹(shù)產(chǎn)生回路，直到找到n-1條邊。21(2)在圖G的邊集中選取權(quán)值最小的邊，若該邊未使生成樹(shù)T形成回路，則加入到TE中，否則丟棄，直到生成樹(shù)中包含了n-1條邊(1)將T的初始狀態(tài)置為僅含有源點(diǎn)的集合設(shè)圖是由n個(gè)頂點(diǎn)組成的連通無(wú)向網(wǎng)，是圖G的最小生成樹(shù),其中V是T的頂點(diǎn)集，TE是T的邊集586.4.3

Prim算法12

頂點(diǎn)到頂點(diǎn)集合的距離：頂點(diǎn)到頂點(diǎn)集合中所有頂點(diǎn)的距離的最小值，記為|u,V|=min|u,v|3

兩個(gè)頂點(diǎn)集合之間的距離：頂點(diǎn)集合U的頂點(diǎn)到頂點(diǎn)集合V的距離的最小值，記為|U,V|=min|u,V|兩個(gè)頂點(diǎn)之間的距離：將頂點(diǎn)u鄰接到頂點(diǎn)v的關(guān)聯(lián)邊的權(quán)值，記為|u,v|。若兩個(gè)頂點(diǎn)之間不相連，則這兩個(gè)頂點(diǎn)之間的距離為無(wú)窮大596.4.3Prim算法-類(lèi)描述606.4.3Prim算法-類(lèi)描述616.5最短路徑6.5.1單源最短路徑6.5.2求任意兩個(gè)頂點(diǎn)間的最短路徑6.5.1單源最短路徑-Dijkstra算法B在最短路徑中長(zhǎng)度最短的最短路徑一定有且僅有一條弧，弧的權(quán)值是從源點(diǎn)出發(fā)的所有弧的權(quán)中的最小值C長(zhǎng)度次短的最短路徑有兩種情況：其一。只包含一條從源點(diǎn)出發(fā)的弧，弧上的權(quán)值大于已求得最短路徑的弧的權(quán)值，小于其他從源點(diǎn)出發(fā)的弧的權(quán)值；其二，一條只經(jīng)過(guò)已求得最短路徑的頂點(diǎn)的路徑A基本思想是“按最短路徑長(zhǎng)度遞增的次序”產(chǎn)生最短路徑算法思想與原理636.5.1單源最短路徑-Dijkstra算法1.保存當(dāng)前最短路徑保存當(dāng)前已經(jīng)得到的從源點(diǎn)到各個(gè)其余頂點(diǎn)的最短路徑算法細(xì)節(jié)引入一個(gè)輔助向量D，它的每個(gè)分量D[i]存放當(dāng)前所找到的從源點(diǎn)到終點(diǎn)的最短路徑長(zhǎng)度。2.更新最短路徑若源點(diǎn)到該頂點(diǎn)有弧，存在一條路徑，長(zhǎng)度為弧上的權(quán)值，每求得一條到達(dá)某個(gè)頂點(diǎn)的最短路徑就需要檢查是否存在經(jīng)過(guò)這個(gè)頂點(diǎn)的其他路徑，若存在，判斷其長(zhǎng)度是否比當(dāng)前求得的路徑長(zhǎng)度短，若是，則修改當(dāng)前路徑64Dijkstra算法構(gòu)造最短路徑的類(lèi)Java語(yǔ)言描述如下：6.5.1單源最短路徑-Dijkstra算法65

6.5.1單源最短路徑-Dijkstra算法666.5.2兩點(diǎn)最短路徑-Floyd算法用n階方陣序列來(lái)描述Floyd算法，其中D-1[i][j]表示從頂點(diǎn)出發(fā)不經(jīng)過(guò)其他頂點(diǎn)直接到達(dá)頂點(diǎn)的路徑長(zhǎng)度，即D-1[i][j]=G.arcs[i][j]，D(k)[i][j]表示從頂點(diǎn)vi到頂點(diǎn)vj的中間可能經(jīng)過(guò)v0，…,vk，而不可能經(jīng)過(guò)vk+1,…,vn-1等頂點(diǎn)的最短路徑長(zhǎng)度，所以D(n-1)[i][j]是從頂點(diǎn)vi到頂點(diǎn)vj的最短路徑長(zhǎng)度，和路徑長(zhǎng)度序列相對(duì)應(yīng)的是路徑的n階方陣序列p(-1),p(0),p(1),…,p(n-1)算法描述圖例分析其中，k表示在路徑中新增的頂點(diǎn)，i為路徑的源點(diǎn)，j為路徑的終點(diǎn)。676.5.2兩點(diǎn)最短路徑-Floyd算法Floyd算法構(gòu)造最短路徑的類(lèi)用Java語(yǔ)言描述如右：686.6拓?fù)渑判蚝完P(guān)鍵路徑6.6.1拓?fù)渑判?.6.2關(guān)鍵路徑有向圖表示活動(dòng)之間相互制約的關(guān)系，稱(chēng)為頂點(diǎn)活動(dòng)網(wǎng)(AOV）弧表示活動(dòng)之間的優(yōu)先關(guān)系活動(dòng)指在生產(chǎn)實(shí)踐中，幾乎所有的工程都可以分解為若干個(gè)具有相對(duì)獨(dú)立性的子工程頂點(diǎn)表示活動(dòng)6.6.1

AOV概念引入和圖表示在AOV網(wǎng)中存在一條從頂點(diǎn)u到頂點(diǎn)v的弧，則活動(dòng)u一定優(yōu)先于活動(dòng)v發(fā)生，否則活動(dòng)u、v的發(fā)生順序可以是任意的，且不能存在閉環(huán)。706.6.1拓?fù)渑判?概念和算法原理對(duì)AOV網(wǎng)進(jìn)行拓?fù)渑判蚣礃?gòu)造一個(gè)包含圖中所有頂點(diǎn)的拓?fù)溆行蛐蛄?，若在AOV網(wǎng)中存在一條從頂點(diǎn)u到頂點(diǎn)v的弧，則在拓?fù)溆行蛐蛄兄许旤c(diǎn)u必須先于頂點(diǎn)v，否則頂點(diǎn)u、v的順序可以是任意的。概念(1)在AOV網(wǎng)中選擇一個(gè)沒(méi)有前驅(qū)的頂點(diǎn)并輸出。(2)從AOV網(wǎng)中刪除該頂點(diǎn)以及從它出發(fā)的弧。(3)重復(fù)步驟(1)和(2)直到AOV網(wǎng)為空，或者剩余子圖中不存在沒(méi)有前驅(qū)的頂點(diǎn)，此時(shí)說(shuō)明AOV網(wǎng)中存在環(huán)。算法步驟整個(gè)拓?fù)渑判蚩梢苑殖汕蟾鱾€(gè)頂點(diǎn)的入度和一個(gè)拓?fù)湫蛄械倪^(guò)程。應(yīng)用716.6.1拓?fù)渑判?具體算法【算法6.16】求各頂點(diǎn)的入度。726.6.1拓?fù)渑判?具體算法【算法6.17】計(jì)算AOV的一個(gè)拓?fù)湫蛄?，若存在返回拓?fù)湫蛄?，否則返回None。736.6.2關(guān)鍵路徑SWOTAOE網(wǎng)（邊活動(dòng)網(wǎng)絡(luò)）以弧表示活動(dòng)，弧上的權(quán)值表示進(jìn)行該項(xiàng)活動(dòng)需要的時(shí)間，頂點(diǎn)表示事件關(guān)鍵路徑工程開(kāi)始事件的頂點(diǎn)稱(chēng)為源點(diǎn)，工程結(jié)束事件的頂點(diǎn)稱(chēng)為匯點(diǎn)，從源點(diǎn)到匯點(diǎn)的最短路徑稱(chēng)為關(guān)鍵路徑關(guān)鍵活動(dòng)當(dāng)e(i)=l(i),稱(chēng)為關(guān)鍵活動(dòng)最早開(kāi)始時(shí)間和最晚開(kāi)始時(shí)間從V0到Vi的最長(zhǎng)路徑叫做事件的最早發(fā)生時(shí)間，記為e(i)。最晚開(kāi)始時(shí)間指的是在不推遲整個(gè)工程的前提下，活動(dòng)最晚必須開(kāi)始的時(shí)間，記為l(i)。746.6.2關(guān)鍵路徑-算法原理從源點(diǎn)出發(fā)，令ve(0)=0，其余各頂點(diǎn)的ve(j)=max(ve(i)+|i,l|)，其中，T是所有以第j個(gè)頂點(diǎn)為頭的弧的集合。若得到的拓?fù)渑判蛐蛄兄许旤c(diǎn)的個(gè)數(shù)小于網(wǎng)中的頂點(diǎn)個(gè)數(shù)n，則說(shuō)明網(wǎng)中有環(huán)，不能求出關(guān)鍵路徑，算法結(jié)束1從Vn-1匯點(diǎn)出發(fā)，令vl(n-1)=ve(n-1)，按逆拓?fù)渑判蚯笃溆喔黜旤c(diǎn)許的最晚開(kāi)始時(shí)間為vl(i)=min(vl(j)-|i,j|)，其中，S是所有以第j個(gè)頂為尾的弧的集合。2每一項(xiàng)活動(dòng)ai的最早開(kāi)始時(shí)間為e(i)=ve(j)，最晚開(kāi)始時(shí)間為l(i)=vl(j)-|i,j|。若ai滿足e(i)=l(i),則它是關(guān)鍵活動(dòng)。3756.6.2關(guān)鍵路徑-具體算法【算法6.18】若拓?fù)湫蛄写嬖?，返回各頂點(diǎn)的最早發(fā)生時(shí)間ve與逆拓?fù)湫蛄袟，否則返回None,None。766.6.2關(guān)鍵路徑-具體算法【算法6.19】求各頂點(diǎn)的最晚發(fā)生時(shí)間并輸出關(guān)鍵活動(dòng)。776.7小結(jié)SOTW圖的常見(jiàn)存儲(chǔ)結(jié)構(gòu)有鄰接矩陣、鄰接表、十字鏈表3種。鄰接矩陣是圖，用二維數(shù)組存儲(chǔ)；鄰接表和十字鏈表是圖的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)由廣度優(yōu)先遍歷和深度優(yōu)先遍歷得到的生成樹(shù)分別稱(chēng)為廣度優(yōu)先生成樹(shù)和深度優(yōu)先生成樹(shù)。在一個(gè)網(wǎng)的所有生成樹(shù)中權(quán)值總和最小的生成樹(shù)稱(chēng)為最小代價(jià)生成樹(shù)，簡(jiǎn)稱(chēng)為最小生成樹(shù)，最小生成樹(shù)不一定唯一。建立最小生成樹(shù)的方法有Kruskal算法和Prim算法圖是一種數(shù)據(jù)元素間具有“多對(duì)多”關(guān)系的非線性數(shù)據(jù)結(jié)構(gòu)，由頂點(diǎn)集V和邊集E組成，記作G=(V,E)圖的遍歷是指從圖的任意一個(gè)頂點(diǎn)出發(fā)對(duì)圖的每個(gè)頂點(diǎn)訪問(wèn)且僅訪問(wèn)一次的過(guò)程。圖的遍歷方式分為兩種，即廣度優(yōu)先搜索遍歷和深度優(yōu)先搜索遍歷總結(jié)79SOTW用戶可以使用有向圖表示活動(dòng)之間相互制約的關(guān)系，頂點(diǎn)表示活動(dòng)，弧表示活動(dòng)之間的優(yōu)先關(guān)系，這種有向圖稱(chēng)為頂點(diǎn)活動(dòng)網(wǎng)(AOV)。若在AOV網(wǎng)中存在一條從頂點(diǎn)u到頂點(diǎn)v的弧，則活動(dòng)u一定優(yōu)先于活動(dòng)v發(fā)生。AOE網(wǎng)絡(luò)常用來(lái)表示工程的進(jìn)行，一個(gè)工程的AOE網(wǎng)應(yīng)該是只有一個(gè)源點(diǎn)和一個(gè)匯點(diǎn)的有向無(wú)環(huán)圖。由于AOE網(wǎng)中的某些活動(dòng)可以并行進(jìn)行，故完成整個(gè)工程的最短時(shí)間即從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑的長(zhǎng)度，這條路徑稱(chēng)為關(guān)鍵路徑，構(gòu)成關(guān)鍵路徑的弧即為關(guān)鍵活動(dòng)。最短路徑的求解問(wèn)題主要分為兩類(lèi)，即求某個(gè)頂點(diǎn)到其余頂點(diǎn)的最短路徑、求每一對(duì)頂點(diǎn)間的最短路徑，可以分別使用Dijkstra算法和Floyd算法解決這兩類(lèi)問(wèn)題若以弧表示活動(dòng)，弧上的權(quán)值表示進(jìn)行該項(xiàng)活動(dòng)需要的時(shí)間，頂點(diǎn)表示事件，這種有向網(wǎng)稱(chēng)為邊活動(dòng)網(wǎng)絡(luò)，簡(jiǎn)稱(chēng)為AOE網(wǎng)?？偨Y(jié)80第7章排序目錄82排序概述插入排序交換排序選擇排序歸并排序第一節(jié)第二節(jié)第三節(jié)第四節(jié)第五節(jié)第一節(jié)排序概述1.1排序的基本概念84排序是指將一組數(shù)據(jù)按照關(guān)鍵字值的大小(遞增或者遞減)次序進(jìn)行排列。排序是線性表、二叉樹(shù)等數(shù)據(jù)結(jié)構(gòu)的一種基本操作。作為排序依據(jù)的數(shù)據(jù)項(xiàng)叫關(guān)鍵字。關(guān)鍵字關(guān)鍵字能唯一標(biāo)識(shí)一條記錄，叫主關(guān)鍵字關(guān)鍵字標(biāo)識(shí)多條記錄，叫次關(guān)鍵字例如學(xué)號(hào)、班級(jí)、成績(jī)等數(shù)據(jù)項(xiàng)均可以作為學(xué)生信息數(shù)據(jù)元素的關(guān)鍵字，按主關(guān)鍵字進(jìn)行排序，結(jié)果唯一；按非主關(guān)鍵字進(jìn)行排序，結(jié)果不唯一，班級(jí)學(xué)生的次序不能確定，哪個(gè)在前后都有可能。1.1排序的基本概念85按照排序過(guò)程中所涉及的存儲(chǔ)器的不同可將排序分為內(nèi)部排序和外部排序兩種類(lèi)型。

內(nèi)部排序是指排序序列完全存放在內(nèi)存中的排序過(guò)程；

外部排序是指需要將數(shù)據(jù)元素存儲(chǔ)在外部存儲(chǔ)器上的排序過(guò)程。排序又可分為穩(wěn)定排序和不穩(wěn)定排序。

穩(wěn)定排序是指在用某種排序算法依據(jù)關(guān)鍵字進(jìn)行排序后具有相同關(guān)鍵字的數(shù)據(jù)元素的位置關(guān)系與排序前相同的排序過(guò)程，反之則為不穩(wěn)定排序。1.2排序算法的性能評(píng)價(jià)86排序算法的性能評(píng)價(jià)時(shí)間復(fù)雜度：算法執(zhí)行過(guò)程中的比較和移動(dòng)次數(shù)來(lái)計(jì)算空間復(fù)雜度：用外部存儲(chǔ)空間的大小來(lái)計(jì)算

排序往往處于軟件的核心部分，經(jīng)常被使用，所以其性能的優(yōu)劣對(duì)軟件質(zhì)量的好壞起著重要的作用1.3待排序的記錄和順序表的類(lèi)描述87因?yàn)榇判虻臄?shù)據(jù)元素通常存儲(chǔ)在順序表中，所以本章中的排序算法都是以順序表為基礎(chǔ)進(jìn)行設(shè)計(jì)的。待排序的記錄的類(lèi)Python語(yǔ)言描述如下：1.3待排序的記錄和順序表的類(lèi)描述88

待排序的順序表的類(lèi)Python語(yǔ)言描述如下：第二節(jié)插入排序2.1直接插入排序90直接插入算法的實(shí)現(xiàn)直接插入排序是指將一條待排序的記錄按照其關(guān)鍵字值的大小插入到已排序的記錄序列中的正確位置，依次重復(fù)，直到全部記錄都插入完成。其主要步驟如下：

(1)將list[i]存放在臨時(shí)變量p中。(2)將p與list[i-1]、list[i-2]、…、list[0]依次比較，若有p<list[j].key(j=i-1、i-2、…、0)，則將list[j]后移一個(gè)位置，直到p≥list[j].key為止。當(dāng)p≥list[j].key時(shí)將p插入到list[j+1]的位置。(3)令i=1、2、3、…、n-1，重復(fù)步驟(1)、(2)、(3)。2.1直接插入排序91假設(shè)一組待排序的記錄的關(guān)鍵字序列為{2,45,36,72,34}，直接插入排序的過(guò)程如圖7.1所示。2.1直接插入排序92【算法7.1】直接插入排序。2.1直接插入排序性能分析931.時(shí)間復(fù)雜度※有序表中逐個(gè)插入的操作進(jìn)行了n-1趟，每趟的插入操作的時(shí)間主要耗費(fèi)在關(guān)鍵字的比較和數(shù)據(jù)元素的移動(dòng)上。

2.1直接插入排序性能分析942.空間復(fù)雜度由于其僅使用了一個(gè)輔助存儲(chǔ)單元p，所以空間復(fù)雜度為O(1)。2.算法穩(wěn)定性在使用直接插入排序后具有相同關(guān)鍵字的數(shù)據(jù)元素的位置關(guān)系與排序前相同，因此直接插入排序是一種穩(wěn)定的排序算法。2.2希爾排序95希爾排序算法的實(shí)現(xiàn)希爾排序是D.L.Shell在1959年提出的，又稱(chēng)縮小增量排序，是對(duì)直接插入排序的改進(jìn)算法，其基本思想是分組的直接插入排序。由直接插入排序算法分析可知，數(shù)據(jù)序列越接近有序時(shí)間效率越高，當(dāng)n較小時(shí)時(shí)間效率也較高。希爾排序正是針對(duì)這兩點(diǎn)對(duì)直接插入排序算法進(jìn)行改進(jìn)。希爾排序算法的描述如下:(1)將一個(gè)數(shù)據(jù)元素序列分組，每組由若干個(gè)相隔一段距離的元素組成，在一個(gè)組內(nèi)采用直接插入算法進(jìn)行排序。(2)增量的初值通常為數(shù)據(jù)元素序列的一半，以后每趟增量減半，最后值為1。隨著增量逐漸減小，組數(shù)也減少，組內(nèi)元素的個(gè)數(shù)增加，數(shù)據(jù)元素序列接近有序。2.2希爾排序96主要步驟(1)設(shè)定一個(gè)增量序列{d0,d1，…,1}。(2)根據(jù)當(dāng)前增量di將間隔為di的數(shù)據(jù)元素組成一個(gè)子表，共di個(gè)子表。(3)對(duì)各子表中的數(shù)據(jù)元素進(jìn)行直接插入排序。(4)重復(fù)步驟(2)、(3)，直到進(jìn)行完di=1，此時(shí)序列已按關(guān)鍵字值排序。2.2希爾排序97假設(shè)一組待排序的記錄的關(guān)鍵字序列為{2,18,23,56,78,70,45,36,72,34}，增量分別取5、3、1，則希爾排序的過(guò)程如圖7.2所示。2.2希爾排序算法性能分析981.時(shí)間復(fù)雜度希爾排序的關(guān)鍵字比較次數(shù)和數(shù)據(jù)元素的移動(dòng)次數(shù)取決于增量的選擇，目前還沒(méi)有更好的選取增量序列的方法。Hibbard提出了一種增量序列{2k-1,2k-1-1,…,7,3,1}，可以使時(shí)間復(fù)雜度達(dá)到O(n3/2)。需要注意的是，在增量序列中應(yīng)沒(méi)有除1以外的公因子，并且最后一個(gè)增量值必須為1。2.2希爾排序992.空間復(fù)雜度希爾排序仍只使用了一個(gè)額外的存儲(chǔ)空間p，其空間復(fù)雜度為O(1)。3.算法穩(wěn)定性希爾排序算法在比較過(guò)程中會(huì)錯(cuò)過(guò)關(guān)鍵字相等的數(shù)據(jù)元素的比較，算法不能控制穩(wěn)定，因此希爾排序是一種不穩(wěn)定的排序算法。第三節(jié)交換排序3.1冒泡排序101冒泡排序算法的實(shí)現(xiàn)冒泡排序是兩兩比較待排序記錄的關(guān)鍵字，如果次序相反則交換兩個(gè)記錄的位置，直到序列中的所有記錄有序。若按升序排序，每趟將數(shù)據(jù)元素序列中的最大元素交換到最后的位置，就像氣泡從水里冒出一樣。其主要步驟如下：(1)設(shè)交換次數(shù)k=1。(2)在常數(shù)為n的序列{a[0],a[1],…,a[n-1]}中從頭到尾比較a[i]和a[i+1]，若a[i].key>a[i+1].key，則交換兩個(gè)元素的位置，其中，0≤i<n-i。(3)k增加1。(4)重復(fù)步驟(2)、(3)，直到k=n-1或者步驟(2)中未發(fā)生交換為止。3.1冒泡排序102假設(shè)一組待排序的記錄的關(guān)鍵字序列為{2,23,18,56,78,70,45,36,72,34}，冒泡排序的過(guò)程如圖7.3所示。3.2快速排序103快速排序算法的實(shí)現(xiàn)快速排序是一種分區(qū)交換排序算法，是冒泡排序的改進(jìn)，其采用了分治策略，將問(wèn)題劃分成若干個(gè)規(guī)模更小但和原問(wèn)題相似的子問(wèn)題，然后用遞歸方法解決這些子問(wèn)題，最終將它們組合成原問(wèn)題的解?？焖倥判?qū)⒁判虻男蛄蟹殖瑟?dú)立的兩個(gè)部分，其中一部分的關(guān)鍵字值都比另一部分的關(guān)鍵字值大，然后分別對(duì)這兩個(gè)部分進(jìn)行快速排序，排序過(guò)程遞歸進(jìn)行，整個(gè)序列最終達(dá)到有序。獨(dú)立的兩個(gè)部分的劃分方法為在序列中任意選取一條記錄，然后將所有關(guān)鍵字值比它大的記錄放到它的后面，將所有關(guān)鍵字值比它小的記錄放到它的前面。這條記錄叫支點(diǎn)。3.1冒泡排序104主要步驟(1)設(shè)置兩個(gè)變量low、high，分別表示待排序序列的起始下標(biāo)和終止下標(biāo)。(2)設(shè)置變量p=list[low]。(3)從下標(biāo)為high的位置從后向前依次搜索，當(dāng)找到第1個(gè)比p的關(guān)鍵字值小的記錄時(shí)將該數(shù)據(jù)移動(dòng)到下標(biāo)為low的位置上，low加1。(4)從下標(biāo)為low的位置從前向后依次搜索，當(dāng)找到第1個(gè)比p的關(guān)鍵字值大的記錄時(shí)將該數(shù)據(jù)移動(dòng)到下標(biāo)為high的位置上，high減1。(5)重復(fù)步驟(3)和(4)，直到high=low為止。(6)list[low]=p。3.1冒泡排序105假設(shè)一組待排序的記錄的關(guān)鍵字序列為{45,53,18,36,72,30,48,93,15,36}，以排序碼45進(jìn)行第一次劃分的過(guò)程如圖7.4所示。3.1冒泡排序1063.1冒泡排序算法性能分析1071.時(shí)間復(fù)雜度

3.1