計算機統(tǒng)考重難點班講義(數(shù)據(jù)結構第三講

1、數(shù)據(jù)結構數(shù)據(jù)結構重難點串講重難點串講講師：翔高教育一級培訓師地點：上海第第5章章 圖圖重難點導航重難點導航v 圖的存儲結構，尤其是鄰接矩陣和鄰接表圖的存儲結構，尤其是鄰接矩陣和鄰接表v 圖的遍歷算法；廣度優(yōu)先搜索遍歷和深度優(yōu)先搜索圖的遍歷算法；廣度優(yōu)先搜索遍歷和深度優(yōu)先搜索遍歷。圖的遍歷是圖各種運算的基礎遍歷。圖的遍歷是圖各種運算的基礎v 最小生成樹的生成算法以及過程，熟練掌握最小生成樹的生成算法以及過程，熟練掌握prim和和kruskal算法，特別是利用兩算法手工模擬生成算法，特別是利用兩算法手工模擬生成樹的生成過程樹的生成過程v 圖的應用：最小生成樹，拓撲排序，關鍵路徑，最圖的應用：最小生

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

21、1676296g61489afegdcbedgesadjvexlowcost00123456aeefbe0800選中最小紫邊（選中最小紫邊（e,g)e,g)；g g并入紅點集；并入紅點集；最小生成樹構造完畢最小生成樹構造完畢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】若無向圖】若無向圖g=(v,e)中合有中合有7個頂點，要保證圖個頂點，要保證圖g在在任何情況下都是連通的，則需要的邊數(shù)最少是任何情況下都是連通的，則需要的邊數(shù)最少是v a6 b15 c16 d21v 【解析】無向圖中，如果每個頂點都有到其它所有頂點的路【解析】無向圖中，如果每個頂點都有到其它所有頂點的路徑，那么這個無向圖是連通圖。這個題是要保證圖徑，那么這個無向圖是連通圖。這個題是要保證圖g在任何在任何情況下都是連通的所需要的最少邊數(shù)，關鍵是要把握情況下都是連通的所需要的最少邊數(shù)，關鍵是要把握“在任在任何情況下都是連通的何情況下都是連通的”。在頂點固定的情況下，全連通圖用。在頂點固定的情況下，全連通圖用的邊最多。極端情況是所有的邊都被用于將部分頂點連接成的邊最多。極端情況是所有的邊都被用于將部分頂點連接成全連通圖，而另一個部分頂點被孤立。全連通圖，而另一個部分頂點被孤立。15條邊能夠保證條邊能夠保證6個個頂點的無向圖成為全連通圖，所以若只有頂點的無向圖成為全連通圖，所以若只有15條邊，則可能條邊，則可能出現(xiàn)出現(xiàn)6個頂點全連通而第個頂點全連通而第7個頂點被孤立的情況。再加上一個頂點被孤立的情況。再加