計(jì)算機(jī)統(tǒng)考重難點(diǎn)班講義(數(shù)據(jù)結(jié)構(gòu)第三講

1、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)重難點(diǎn)串講重難點(diǎn)串講講師：翔高教育一級(jí)培訓(xùn)師地點(diǎn)：上海第第5章章 圖圖重難點(diǎn)導(dǎo)航重難點(diǎn)導(dǎo)航v 圖的存儲(chǔ)結(jié)構(gòu)，尤其是鄰接矩陣和鄰接表圖的存儲(chǔ)結(jié)構(gòu)，尤其是鄰接矩陣和鄰接表v 圖的遍歷算法；廣度優(yōu)先搜索遍歷和深度優(yōu)先搜索圖的遍歷算法；廣度優(yōu)先搜索遍歷和深度優(yōu)先搜索遍歷。圖的遍歷是圖各種運(yùn)算的基礎(chǔ)遍歷。圖的遍歷是圖各種運(yùn)算的基礎(chǔ)v 最小生成樹(shù)的生成算法以及過(guò)程，熟練掌握最小生成樹(shù)的生成算法以及過(guò)程，熟練掌握prim和和kruskal算法，特別是利用兩算法手工模擬生成算法，特別是利用兩算法手工模擬生成樹(shù)的生成過(guò)程樹(shù)的生成過(guò)程v 圖的應(yīng)用：最小生成樹(shù)，拓?fù)渑判颍P(guān)鍵路徑，最圖的應(yīng)用：最小生

2、成樹(shù)，拓?fù)渑判?，關(guān)鍵路徑，最短路徑短路徑3鄰接矩陣表示法鄰接矩陣表示法( (數(shù)組表示法數(shù)組表示法) )用一個(gè)一維數(shù)組存放圖的頂點(diǎn)數(shù)據(jù)用一個(gè)一維數(shù)組存放圖的頂點(diǎn)數(shù)據(jù)用一個(gè)矩陣用一個(gè)矩陣ann來(lái)存放圖的邊的信息來(lái)存放圖的邊的信息: 有向有向/ /無(wú)向圖無(wú)向圖: : a i j 0 0 反之反之1 若若 或或 (vi, vj) e(g)有向有向/ /無(wú)向網(wǎng)無(wú)向網(wǎng): : a i j 或或 0 0 反之反之wij 若若 或或 (vi, vj) e(g)圖的鄰接矩陣定義：圖的鄰接矩陣定義：typedef struct /弧結(jié)點(diǎn)與矩陣的類型弧結(jié)點(diǎn)與矩陣的類型 vrtype adj; /vrtype/vrty

3、pe為弧的類型。圖為弧的類型。圖-0,1;-0,1;網(wǎng)網(wǎng)-權(quán)值權(quán)值 infotype *info; /與弧相關(guān)的信息的指針與弧相關(guān)的信息的指針, ,可省略可省略arccell, adjmatrixmax_nmax_n;typedef struct/圖的類型圖的類型 vertextype vexsmax_n;/頂點(diǎn)向量頂點(diǎn)向量 adjmatrix arcs;/鄰接矩陣鄰接矩陣 int vexnum, arcnum;/頂點(diǎn)數(shù)，邊數(shù)頂點(diǎn)數(shù)，邊數(shù) graphkind kind；/圖類型圖類型mgraph; v1v7v4v3v5v6v2v10v21v32v43v54v65v760123456001110

4、00100011112100000131000000401000105010010060110000g.arcs=g.vexs=無(wú)向圖的鄰接矩?zé)o向圖的鄰接矩陣陣存放頂點(diǎn)的數(shù)組表示邊的矩陣v10v21v32v43v54v65v76v8701234567000000000100000001211010000310000000401000100501110000600010100700001010g.arcs=g.vexs=v1v7v4v3v5v6v2v8有向圖的鄰接矩有向圖的鄰接矩陣陣存放頂點(diǎn)的數(shù)組存放頂點(diǎn)的數(shù)組表示弧的矩陣表示弧的矩陣v4的出邊鄰接點(diǎn)v4的入邊鄰接點(diǎn)無(wú)無(wú)向圖鄰接矩陣的特點(diǎn)：向圖鄰

5、接矩陣的特點(diǎn)：8 對(duì)稱矩陣對(duì)稱矩陣8 頂點(diǎn)頂點(diǎn)vivi的度等于第的度等于第i i行非零元個(gè)數(shù)，或第行非零元個(gè)數(shù)，或第i i列非列非零元個(gè)數(shù)：零元個(gè)數(shù)：8 矩陣非零元總數(shù)等于邊數(shù)的矩陣非零元總數(shù)等于邊數(shù)的2 2倍倍 1010.td(vi)nknkikarcsgkiarcsg有向圖鄰接矩陣的特點(diǎn)：有向圖鄰接矩陣的特點(diǎn)：8 是非對(duì)稱矩陣是非對(duì)稱矩陣8 第第i i行非零元個(gè)數(shù)等于頂點(diǎn)行非零元個(gè)數(shù)等于頂點(diǎn)vivi的出度；第的出度；第i i列非列非零元個(gè)數(shù)等于頂點(diǎn)零元個(gè)數(shù)等于頂點(diǎn)vivi的入度：的入度：8 矩陣非零元總數(shù)等于邊數(shù)矩陣非零元總數(shù)等于邊數(shù) 10.od(vi)nkkiarcsg10.)(nkik

6、arcsgviida0b1c2d30123031512963428g.arcs=g.vexs=有向網(wǎng)的鄰接矩陣示例：有向網(wǎng)的鄰接矩陣示例：68314592adcb7.2.1 鄰接表表示法鄰接表表示法將每個(gè)頂點(diǎn)的鄰接點(diǎn)串成一個(gè)單鏈表：將每個(gè)頂點(diǎn)的鄰接點(diǎn)串成一個(gè)單鏈表：鄰接點(diǎn)鄰接點(diǎn)adjvex后繼指針后繼指針nextarc邊信息指針邊信息指針info頂點(diǎn)數(shù)據(jù)頂點(diǎn)數(shù)據(jù)data邊鏈頭指針邊鏈頭指針firstarc邊結(jié)點(diǎn)邊結(jié)點(diǎn)頂點(diǎn)結(jié)點(diǎn)頂點(diǎn)結(jié)點(diǎn)v1v7v4v3v5v6v2012345689datav1v2v3v4v5v6v71321546010firstarc645021g.vertices無(wú)向圖的鄰接表

7、：無(wú)向圖的鄰接表：adjvex nextarc無(wú)向圖鄰接表的特點(diǎn)：無(wú)向圖鄰接表的特點(diǎn)：8 頂點(diǎn)頂點(diǎn)vivi的度等于的度等于vivi所引導(dǎo)的單鏈表的長(zhǎng)度所引導(dǎo)的單鏈表的長(zhǎng)度8 邊結(jié)點(diǎn)的個(gè)數(shù)等于邊數(shù)的邊結(jié)點(diǎn)的個(gè)數(shù)等于邊數(shù)的2 2倍倍 有向圖的鄰接表：v1v7v4v3v5v6v2v8012345689datav1v2v3v4v5v6v7v81327654firstarcadjvex nextarc5427245g.vertices有向圖鄰接表的特點(diǎn)：8 頂點(diǎn)頂點(diǎn)vi引導(dǎo)的單鏈表是出邊鏈，鏈表的長(zhǎng)度等引導(dǎo)的單鏈表是出邊鏈，鏈表的長(zhǎng)度等于于vi的出度的出度8 找一個(gè)頂點(diǎn)的出邊容易，找入邊需要遍歷整個(gè)找一

8、個(gè)頂點(diǎn)的出邊容易，找入邊需要遍歷整個(gè)鄰接表鄰接表8 邊結(jié)點(diǎn)的個(gè)數(shù)等于邊數(shù)邊結(jié)點(diǎn)的個(gè)數(shù)等于邊數(shù)深度優(yōu)先搜索遍歷深度優(yōu)先搜索遍歷(dfs)(dfs)8depth first search;8類似于樹(shù)的先根遍歷類似于樹(shù)的先根遍歷; ;8優(yōu)先向縱深訪問(wèn)優(yōu)先向縱深訪問(wèn)dfsdfs遍歷過(guò)程：遍歷過(guò)程：1. 從圖從圖g中選某個(gè)頂點(diǎn)中選某個(gè)頂點(diǎn)v作為出發(fā)點(diǎn)；作為出發(fā)點(diǎn)；2. 訪問(wèn)訪問(wèn)v；3. 依次從依次從v的未被訪問(wèn)的鄰接點(diǎn)出發(fā)，深度優(yōu)先搜的未被訪問(wèn)的鄰接點(diǎn)出發(fā)，深度優(yōu)先搜索遍歷圖索遍歷圖g, 直至與直至與v相通的頂點(diǎn)都被訪問(wèn)完；相通的頂點(diǎn)都被訪問(wèn)完；4. 如果此時(shí)圖如果此時(shí)圖g中還有頂點(diǎn)未曾被訪問(wèn)，則從這些

9、中還有頂點(diǎn)未曾被訪問(wèn)，則從這些未被訪問(wèn)的頂點(diǎn)中再選一個(gè)頂點(diǎn)未被訪問(wèn)的頂點(diǎn)中再選一個(gè)頂點(diǎn)v，轉(zhuǎn)，轉(zhuǎn)2，繼續(xù)，繼續(xù)遍歷；否則遍歷結(jié)束遍歷；否則遍歷結(jié)束。v1v7v4v3v5v6v2出發(fā)點(diǎn)dfs訪問(wèn)序列：v1v2v5v6v7v3v4v1出發(fā)點(diǎn)出發(fā)點(diǎn)dfsdfs訪問(wèn)序列：訪問(wèn)序列：v3v2v4v9v1v6v5v2v4v3v6v5v8v7v9v8v7v8v3v1v7v4v9v5v6v2出發(fā)點(diǎn)出發(fā)點(diǎn)dfs訪問(wèn)序列：訪問(wèn)序列：v1v9v7v2v5v6v4data87v76v65v54v43v92v21v108311546012firstarc054681v8v370v3v8v1v7v4v3v5v6v2v8d

10、ata8v87v76v65v54v43v32v21v101327654firstarc2457256g.verticesdfs訪問(wèn)序列：訪問(wèn)序列：v1v2v3v6v5v8v7v4出發(fā)點(diǎn)出發(fā)點(diǎn)bfs遍歷過(guò)程：遍歷過(guò)程：1.1. 從圖從圖g g的某個(gè)頂點(diǎn)的某個(gè)頂點(diǎn)v v出發(fā)，訪問(wèn)出發(fā)，訪問(wèn)v v；2.2.依次依次訪問(wèn)訪問(wèn)v v的未被訪問(wèn)的鄰接點(diǎn)；的未被訪問(wèn)的鄰接點(diǎn)；3.3. 再按照再按照“先被訪問(wèn)頂點(diǎn)的鄰接點(diǎn)先訪問(wèn)先被訪問(wèn)頂點(diǎn)的鄰接點(diǎn)先訪問(wèn)”的次序，依的次序，依次訪問(wèn)這些鄰接點(diǎn)的鄰接點(diǎn)，直至圖中所有已被次訪問(wèn)這些鄰接點(diǎn)的鄰接點(diǎn)，直至圖中所有已被訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)都被訪問(wèn)到；訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)都被訪

11、問(wèn)到；4.4. 若此時(shí)圖中還有頂點(diǎn)未曾被訪問(wèn)，則另選一個(gè)未若此時(shí)圖中還有頂點(diǎn)未曾被訪問(wèn)，則另選一個(gè)未被訪問(wèn)的頂點(diǎn)被訪問(wèn)的頂點(diǎn)v v作為出發(fā)點(diǎn)，重復(fù)上述過(guò)程，直至作為出發(fā)點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有的頂點(diǎn)都被訪問(wèn)完。圖中所有的頂點(diǎn)都被訪問(wèn)完。v1出發(fā)點(diǎn)出發(fā)點(diǎn)bfsbfs訪問(wèn)序列：訪問(wèn)序列：v3v2v1v6v4v5v9v2v4v3v6v5v8v7v9v8v7v1v7v4v3v5v6v2v8訪問(wèn)序列：訪問(wèn)序列：v1v2v4v5v6v7v8出發(fā)點(diǎn)v3data8v87v76v65v54v43v32v21v101327654firstarc2457256求無(wú)向圖的連通分量：求無(wú)向圖的連通分量： 對(duì)無(wú)向圖

12、對(duì)無(wú)向圖g調(diào)用一次調(diào)用一次dfs過(guò)程，能訪問(wèn)完過(guò)程，能訪問(wèn)完g的的一個(gè)連通分量。因此對(duì)一個(gè)連通分量。因此對(duì)dfs算法稍做修改就可解決算法稍做修改就可解決求無(wú)向圖連通分量的問(wèn)題求無(wú)向圖連通分量的問(wèn)題。最小生成樹(shù)最小生成樹(shù)8 最小最小(代價(jià)代價(jià))生成樹(shù)：生成樹(shù)：無(wú)向網(wǎng)的所有生成樹(shù)中，無(wú)向網(wǎng)的所有生成樹(shù)中，邊權(quán)之和最小的生成樹(shù)。邊權(quán)之和最小的生成樹(shù)。8 構(gòu)造最小生成樹(shù)的著名算法：構(gòu)造最小生成樹(shù)的著名算法： prim算法算法 kruskal算法算法8 在在n個(gè)城市之間建通訊網(wǎng)；個(gè)城市之間建通訊網(wǎng)；8 可能的線路最多有可能的線路最多有n(n-1)/2條；條；8 從中選擇從中選擇n1條，滿足：條，滿足：(

13、1)連通；連通；(2)邊上權(quán)值之和為最小。邊上權(quán)值之和為最小。8 這就是構(gòu)造這就是構(gòu)造最小代價(jià)生成樹(shù)最小代價(jià)生成樹(shù)。v1v2v4v5v6v35613266554最小生成樹(shù)的最小生成樹(shù)的mstmst性質(zhì)性質(zhì)： 設(shè)設(shè)g(v, e)是一個(gè)連通網(wǎng)，是一個(gè)連通網(wǎng)，u是頂點(diǎn)是頂點(diǎn)v的一個(gè)非空的一個(gè)非空子集。若子集。若(u, v)是一條具有是一條具有最小權(quán)值的邊最小權(quán)值的邊，且，且uu集，集，vvu集，則必存在一棵包含邊集，則必存在一棵包含邊(u, v)的最小生成樹(shù)。的最小生成樹(shù)。v1v2v4v5v6v35613266554u集(紅點(diǎn)集)vu集(藍(lán)點(diǎn)集)聯(lián)接紅點(diǎn)和藍(lán)點(diǎn)的邊(紫邊)最小紫邊一定會(huì)最小紫邊一定會(huì)

14、在在g g的某棵最小的某棵最小生成樹(shù)上出現(xiàn)生成樹(shù)上出現(xiàn)primprim算法思想：算法思想：8 由于紅點(diǎn)集與藍(lán)點(diǎn)集的劃分是任意的，經(jīng)過(guò)由于紅點(diǎn)集與藍(lán)點(diǎn)集的劃分是任意的，經(jīng)過(guò)n n1 1次不同的劃分，找到每次劃分的最小紫邊，以此次不同的劃分，找到每次劃分的最小紫邊，以此來(lái)構(gòu)成最小生成樹(shù)的來(lái)構(gòu)成最小生成樹(shù)的n-1n-1條邊。條邊。8 在每次劃分中，每個(gè)藍(lán)點(diǎn)可能有多條紫邊連接紅在每次劃分中，每個(gè)藍(lán)點(diǎn)可能有多條紫邊連接紅點(diǎn)。為了簡(jiǎn)化，我們將每個(gè)藍(lán)點(diǎn)用一條點(diǎn)。為了簡(jiǎn)化，我們將每個(gè)藍(lán)點(diǎn)用一條最小的紫最小的紫邊邊連接到紅點(diǎn)上，構(gòu)成生成樹(shù)的連接到紅點(diǎn)上，構(gòu)成生成樹(shù)的n n1 1條邊。條邊。8 初態(tài)：初態(tài)：任選一

15、個(gè)頂點(diǎn)作為紅點(diǎn)，不妨設(shè)是任選一個(gè)頂點(diǎn)作為紅點(diǎn)，不妨設(shè)是v1v1。鄰。鄰接矩陣的接矩陣的v1v1行就是行就是n n1 1條連接藍(lán)點(diǎn)的紫邊。條連接藍(lán)點(diǎn)的紫邊。8 從紫邊集中選一條最小的紫邊，將相應(yīng)的藍(lán)點(diǎn)從紫邊集中選一條最小的紫邊，將相應(yīng)的藍(lán)點(diǎn)vjvj變成紅點(diǎn)。變成紅點(diǎn)。8 檢測(cè)剩余藍(lán)點(diǎn)到新紅點(diǎn)檢測(cè)剩余藍(lán)點(diǎn)到新紅點(diǎn)vjvj的邊是否小于原來(lái)的紫的邊是否小于原來(lái)的紫邊。若小，則用藍(lán)點(diǎn)到新紅點(diǎn)邊。若小，則用藍(lán)點(diǎn)到新紅點(diǎn)vjvj的紫邊取代原來(lái)的紫邊取代原來(lái)的紫邊的紫邊g.arcs01234506151653215564355243665426g.vexs0v11v22v33v44v55v6prim算法的存儲(chǔ)

16、結(jié)構(gòu)(1)：無(wú)向網(wǎng)用鄰接矩陣表示無(wú)向網(wǎng)用鄰接矩陣表示afegdcb1210161497652348g.vexsg.arcs01234560a01216141b1121072c2103563d3344e454285f51676296g614891210161497652348g.vexsg.arcs01234560a01216141b1121072c2103563d3344e454285f51676296g61489afegdcbedgesadjvexlowcost01234561097652348g.vexsg.arcs01234560a01216141b1121072c2103563d334

17、4e454285f51676296g61489afegdcb121614edgesadjvexlowcost0012345612aaaaaa16 14設(shè)：初態(tài)時(shí)紅點(diǎn)集中只有設(shè)：初態(tài)時(shí)紅點(diǎn)集中只有一個(gè)頂點(diǎn)一個(gè)頂點(diǎn)a a；鄰接矩陣的第鄰接矩陣的第0 0行表示了所行表示了所有的紫邊有的紫邊1210161497652348g.vexsg.arcs01234560a01216141b1121072c2103563d3344e454285f51676296g61489afegdcbedgesadjvexlowcost0012345612aaaaaa16 140b10b7選中最小紫邊（選中最小紫邊（a,b)

18、a,b)；b b并入紅點(diǎn)集；并入紅點(diǎn)集；調(diào)整藍(lán)點(diǎn)調(diào)整藍(lán)點(diǎn)c c，f f所關(guān)聯(lián)的紫所關(guān)聯(lián)的紫邊邊12101497652348g.vexsg.arcs01234560a01216141b1121072c2103563d3344e454285f51676296g61489afegdcbclosedgeadjvexlowcost00123456abaaba10 140f67選中最小紫邊（選中最小紫邊（b,f)b,f)；f f并入紅點(diǎn)集；并入紅點(diǎn)集；調(diào)整藍(lán)點(diǎn)調(diào)整藍(lán)點(diǎn)c,e,gc,e,g所關(guān)聯(lián)的紫所關(guān)聯(lián)的紫邊邊0f29f1297652348g.vexsg.arcs01234560a01216141b112

19、1072c2103563d3344e454285f51676296g61489afegdcbclosedgeadjvexlowcost00123456afafbf62900選中最小紫邊（選中最小紫邊（f,e)f,e)；e e并入紅點(diǎn)集；并入紅點(diǎn)集；調(diào)整藍(lán)點(diǎn)調(diào)整藍(lán)點(diǎn)c,d,gc,d,g所關(guān)聯(lián)的紫所關(guān)聯(lián)的紫邊邊0e5e4e812752348g.vexsg.arcs01234560a01216141b1121072c2103563d3344e454285f51676296g61489afegdcbedgesadjvexlowcost00123456aeefbe541680b0選中最小紫邊（選中最小紫

20、邊（e,d)e,d)；d d并入紅點(diǎn)集；并入紅點(diǎn)集；調(diào)整藍(lán)點(diǎn)調(diào)整藍(lán)點(diǎn)c c所關(guān)聯(lián)的紫邊所關(guān)聯(lián)的紫邊0d301272348g.vexsg.arcs01234560a01216141b1121072c2103563d3344e454285f51676296g61489afegdcbedgesadjvexlowcost00123456aeefbe30800選中最小紫邊（選中最小紫邊（d,c)d,c)；c c并入紅點(diǎn)集；并入紅點(diǎn)集；沒(méi)有需要調(diào)整的紫邊沒(méi)有需要調(diào)整的紫邊001272348g.vexsg.arcs01234560a01216141b1121072c2103563d3344e454285f5

21、1676296g61489afegdcbedgesadjvexlowcost00123456aeefbe0800選中最小紫邊（選中最小紫邊（e,g)e,g)；g g并入紅點(diǎn)集；并入紅點(diǎn)集；最小生成樹(shù)構(gòu)造完畢最小生成樹(shù)構(gòu)造完畢000kruskal算法：ecdccbefbaaafdeeffggcbgf2345678910 12 14 16a b c d e fafegdcb127238ga b c d e, f ga b c, d e, f g4a b c, d, e, f ga b, c, d, e, f ga b, c, d, e, f, ga, b, c, d, e, f, g經(jīng)典例題解析經(jīng)

22、典例題解析v 【例【例1】若無(wú)向圖】若無(wú)向圖g=(v,e)中合有中合有7個(gè)頂點(diǎn)，要保證圖個(gè)頂點(diǎn)，要保證圖g在在任何情況下都是連通的，則需要的邊數(shù)最少是任何情況下都是連通的，則需要的邊數(shù)最少是v a6 b15 c16 d21v 【解析】無(wú)向圖中，如果每個(gè)頂點(diǎn)都有到其它所有頂點(diǎn)的路【解析】無(wú)向圖中，如果每個(gè)頂點(diǎn)都有到其它所有頂點(diǎn)的路徑，那么這個(gè)無(wú)向圖是連通圖。這個(gè)題是要保證圖徑，那么這個(gè)無(wú)向圖是連通圖。這個(gè)題是要保證圖g在任何在任何情況下都是連通的所需要的最少邊數(shù)，關(guān)鍵是要把握情況下都是連通的所需要的最少邊數(shù)，關(guān)鍵是要把握“在任在任何情況下都是連通的何情況下都是連通的”。在頂點(diǎn)固定的情況下，全連通圖用。在頂點(diǎn)固定的情況下，全連通圖用的邊最多。極端情況是所有的邊都被用于將部分頂點(diǎn)連接成的邊最多。極端情況是所有的邊都被用于將部分頂點(diǎn)連接成全連通圖，而另一個(gè)部分頂點(diǎn)被孤立。全連通圖，而另一個(gè)部分頂點(diǎn)被孤立。15條邊能夠保證條邊能夠保證6個(gè)個(gè)頂點(diǎn)的無(wú)向圖成為全連通圖，所以若只有頂點(diǎn)的無(wú)向圖成為全連通圖，所以若只有15條邊，則可能條邊，則可能出現(xiàn)出現(xiàn)6個(gè)頂點(diǎn)全連通而第個(gè)頂點(diǎn)全連通而第7個(gè)頂點(diǎn)被孤立的情況。再加上一個(gè)頂點(diǎn)被孤立的情況。再加