數(shù)據(jù)結(jié)構(gòu)案例教程（CC++版）第2版 課件 第7章 圖

第7章圖導(dǎo)學(xué)問(wèn)題11.構(gòu)造最小造價(jià)通信網(wǎng)【問(wèn)題1描述】假設(shè)要在n個(gè)城市之間建立一個(gè)通信網(wǎng)絡(luò)，且每?jī)蓚€(gè)城市之間架設(shè)一條通信線路的成本不盡相同。要連通n個(gè)城市只需要架設(shè)n-1條通信線路，請(qǐng)?jiān)O(shè)計(jì)一個(gè)施工方案使得總造價(jià)最小。導(dǎo)學(xué)問(wèn)題22.設(shè)計(jì)一個(gè)簡(jiǎn)單的旅游交通費(fèi)用查詢系統(tǒng)【問(wèn)題描述】某城市中n個(gè)旅游景點(diǎn)間有旅游交通線相連，所花費(fèi)的代價(jià)不盡相同。請(qǐng)?jiān)O(shè)計(jì)一個(gè)簡(jiǎn)單的旅游線路查詢系統(tǒng)，便于游客查詢從任一個(gè)景點(diǎn)到另一個(gè)景點(diǎn)之間的最少交通花費(fèi)。其他問(wèn)題中國(guó)主干公路網(wǎng)最短路徑查詢校園問(wèn)路系統(tǒng)排課、運(yùn)動(dòng)會(huì)秩序冊(cè)7.1知識(shí)學(xué)習(xí)——圖的基本概念圖的定義圖是由頂點(diǎn)的有窮非空集合和頂點(diǎn)之間邊的集合組成，通常表示為：G=(V，E)G表示一個(gè)圖V是圖G中頂點(diǎn)的集合E是圖G中頂點(diǎn)之間邊的集合。如果圖的任意兩個(gè)頂點(diǎn)之間的邊都是無(wú)向邊，則稱該圖為無(wú)向圖。若頂點(diǎn)vi和vj之間的邊沒有方向，則稱這條邊為無(wú)向邊，表示為(vi,vj)。若從頂點(diǎn)vi到vj的邊有方向，則稱這條邊為有向邊，表示為<vi,vj>。如果圖的任意兩個(gè)頂點(diǎn)之間的邊都是有向邊，則稱該圖為有向圖。V1V2V3V4V5V1V2V3V47.1知識(shí)學(xué)習(xí)——圖的基本概念在線性結(jié)構(gòu)中，數(shù)據(jù)元素之間僅具有線性關(guān)系；在樹結(jié)構(gòu)中，結(jié)點(diǎn)之間具有層次關(guān)系；在圖結(jié)構(gòu)中，任意兩個(gè)頂點(diǎn)之間都可能有關(guān)系。FECBAD線性結(jié)構(gòu)ABCDEF樹結(jié)構(gòu)V1V2V3V4V5圖結(jié)構(gòu)不同結(jié)構(gòu)中邏輯關(guān)系的對(duì)比在線性結(jié)構(gòu)中，元素之間的關(guān)系為前驅(qū)和后繼；在樹結(jié)構(gòu)中，結(jié)點(diǎn)之間的關(guān)系為雙親和孩子；在圖結(jié)構(gòu)中，頂點(diǎn)之間的關(guān)系為鄰接。FECBAD線性結(jié)構(gòu)ABCDEF樹結(jié)構(gòu)V1V2V3V4V5圖結(jié)構(gòu)不同結(jié)構(gòu)中邏輯關(guān)系的對(duì)比7.1知識(shí)學(xué)習(xí)——圖的基本術(shù)語(yǔ)圖的基本術(shù)語(yǔ)無(wú)向完全圖：在無(wú)向圖中，如果任意兩個(gè)頂點(diǎn)之間都存在邊，則稱該圖為無(wú)向完全圖。有向完全圖：在有向圖中，如果任意兩個(gè)頂點(diǎn)之間都存在方向相反的兩條弧，則稱該圖為有向完全圖。V1V2V3V1V2V3V4含有n個(gè)頂點(diǎn)的無(wú)向完全圖有多少條邊？含有n個(gè)頂點(diǎn)的有向完全圖有多少條弧？V1V2V3V1V2V3V47.1知識(shí)學(xué)習(xí)——圖的基本術(shù)語(yǔ)含有n個(gè)頂點(diǎn)的無(wú)向完全圖有n×(n-1)/2條邊含有n個(gè)頂點(diǎn)的有向完全圖有n×(n-1)條弧V1V2V3V1V2V3V47.1知識(shí)學(xué)習(xí)——圖的基本術(shù)語(yǔ)7.1知識(shí)學(xué)習(xí)——圖的基本術(shù)語(yǔ)圖的基本術(shù)語(yǔ)頂點(diǎn)的度：在無(wú)向圖中，頂點(diǎn)v的度是指依附于該頂點(diǎn)的邊數(shù)，通常記為TD(v)。頂點(diǎn)的入度：在有向圖中，頂點(diǎn)v的入度是指以該頂點(diǎn)為弧頭的弧的數(shù)目，記為ID(v)；頂點(diǎn)的出度：在有向圖中，頂點(diǎn)v的出度是指以該頂點(diǎn)為弧尾的弧的數(shù)目，記為OD(v)。V1V2V3V4V5在具有n個(gè)頂點(diǎn)、e條邊的無(wú)向圖G中，各頂點(diǎn)的度之和與邊數(shù)之和的關(guān)系？?==niievTD12)(7.1知識(shí)學(xué)習(xí)——圖的基本術(shù)語(yǔ)V1V2V3V4在具有n個(gè)頂點(diǎn)、e條邊的有向圖G中，各頂點(diǎn)的入度之和與各頂點(diǎn)的出度之和的關(guān)系？與邊數(shù)之和的關(guān)系？evODvIDiiii==??==11)()(nn7.1知識(shí)學(xué)習(xí)——圖的基本術(shù)語(yǔ)7.1知識(shí)學(xué)習(xí)——圖的基本術(shù)語(yǔ)圖的基本術(shù)語(yǔ)權(quán)：是指對(duì)邊賦予的有意義的數(shù)值量。網(wǎng)：邊上帶權(quán)的圖，也稱網(wǎng)圖。V1V2V3V427857.1知識(shí)學(xué)習(xí)——圖的基本術(shù)語(yǔ)圖的基本術(shù)語(yǔ)路徑：V1V2V3V4V5一般情況下，圖中的路徑不惟一。V1到V4的路徑：V1V4

V1V2V3V4V1V2V5V3V47.1知識(shí)學(xué)習(xí)——圖的基本術(shù)語(yǔ)圖的基本術(shù)語(yǔ)路徑長(zhǎng)度：非帶權(quán)圖——路徑上邊的個(gè)數(shù)帶權(quán)圖——路徑上各邊的權(quán)之和V1V2V3V4V5V1V4：長(zhǎng)度為V1V2V3V4：長(zhǎng)度為V1V2V5V3V4：長(zhǎng)度為1347.1知識(shí)學(xué)習(xí)——圖的基本術(shù)語(yǔ)圖的基本術(shù)語(yǔ)路徑長(zhǎng)度：非帶權(quán)圖——路徑上邊的個(gè)數(shù)帶權(quán)圖——路徑上各邊的權(quán)之和V1V4：長(zhǎng)度為V1V2V3V4：長(zhǎng)度為V1V2V5V3V4：長(zhǎng)度為V1V2V3V4V525632887157.1知識(shí)學(xué)習(xí)——圖的基本術(shù)語(yǔ)圖的基本術(shù)語(yǔ)回路（環(huán)）：第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑。簡(jiǎn)單路徑：序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑。簡(jiǎn)單回路（簡(jiǎn)單環(huán)）：除了第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)外，其余頂點(diǎn)不重復(fù)出現(xiàn)的回路。V1V2V3V4V5V1V2V3V47.1知識(shí)學(xué)習(xí)——圖的基本術(shù)語(yǔ)圖的基本術(shù)語(yǔ)子圖：若圖G=（V，E），G'=（V'，E'），如果V'

V

且E'

E，則稱圖G'是G的子圖。V1V2V3V4V5V1V2V3V4V5V1V3V47.1知識(shí)學(xué)習(xí)——圖的基本術(shù)語(yǔ)圖的基本術(shù)語(yǔ)連通圖：在無(wú)向圖中，如果從一個(gè)頂點(diǎn)vi到另一個(gè)頂點(diǎn)vj(i≠j)有路徑，則稱頂點(diǎn)vi和vj是連通的。如果圖中任意兩個(gè)頂點(diǎn)都是連通的，則稱該圖是連通圖。連通分量：非連通圖的極大連通子圖稱為連通分量。1.含有極大頂點(diǎn)數(shù)；2.依附于這些頂點(diǎn)的所有邊。如何求得一個(gè)非連通圖的連通分量?連通分量1

V1V2V3V4V5V6V7V1V2V4V5V3V6V7連通分量2連通分量是對(duì)無(wú)向圖的一種劃分。7.1知識(shí)學(xué)習(xí)——圖的基本術(shù)語(yǔ)7.1知識(shí)學(xué)習(xí)——圖的基本術(shù)語(yǔ)圖的基本術(shù)語(yǔ)強(qiáng)連通圖：在有向圖中，對(duì)圖中任意一對(duì)頂點(diǎn)vi和vj

(i≠j)，若從頂點(diǎn)vi到頂點(diǎn)vj和從頂點(diǎn)vj到頂點(diǎn)vi均有路徑，則稱該有向圖是強(qiáng)連通圖。強(qiáng)連通分量：非強(qiáng)連通圖的極大強(qiáng)連通子圖。如何求得一個(gè)非連通圖的連通分量?V1V2V3V4強(qiáng)連通分量1

強(qiáng)連通分量2V1V3V4V27.1知識(shí)學(xué)習(xí)——圖的基本術(shù)語(yǔ)7.1知識(shí)學(xué)習(xí)——圖的基本術(shù)語(yǔ)圖的基本術(shù)語(yǔ)生成樹：n個(gè)頂點(diǎn)的連通圖G的生成樹是包含G中全部頂點(diǎn)的一個(gè)極小連通子圖。生成森林：在非連通圖中，由每個(gè)連通分量都可以得到一棵生成樹，這些連通分量的生成樹就組成了一個(gè)非連通圖的生成森林。多——構(gòu)成回路少——不連通含有n-1條邊如何理解極小連通子圖?V1V2V3V4V5V6V7V1V2V3V4V5V6V7V1V2V3V4V5V1V2V3V4V5生成樹生成森林7.1知識(shí)學(xué)習(xí)——圖的存儲(chǔ)結(jié)構(gòu)是否可以采用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)圖?圖的特點(diǎn)：頂點(diǎn)之間的關(guān)系是m:n，即任何兩個(gè)頂點(diǎn)之間都可能存在關(guān)系（邊），無(wú)法通過(guò)存儲(chǔ)位置表示這種任意的邏輯關(guān)系，所以，圖無(wú)法采用順序存儲(chǔ)結(jié)構(gòu)。如何存儲(chǔ)圖?考慮圖的定義，圖是由頂點(diǎn)和邊組成的，分別考慮如何存儲(chǔ)頂點(diǎn)、如何存儲(chǔ)邊。7.1知識(shí)學(xué)習(xí)——圖的存儲(chǔ)結(jié)構(gòu)1.鄰接矩陣（數(shù)組表示法）基本思想：用一個(gè)一維數(shù)組存儲(chǔ)圖中頂點(diǎn)的信息，用一個(gè)二維數(shù)組（稱為鄰接矩陣）存儲(chǔ)圖中各頂點(diǎn)之間的鄰接關(guān)系假設(shè)圖G＝(V，E)有n個(gè)頂點(diǎn)，則鄰接矩陣是一個(gè)n×n的方陣，定義為：arcs[i][j]＝1若(vi,vj)∈E（或<vi,vj>∈E）0其它7.1知識(shí)學(xué)習(xí)——圖的存儲(chǔ)結(jié)構(gòu)1.鄰接矩陣（數(shù)組表示法）類型定義：enumGraphType{DG,UG,DN,UN};typedefcharVertexType;typedefstruct{ VertexTypevexs[MAX];//頂點(diǎn)表 intarcs[MAX][MAX];//鄰接矩陣 intvexnum,arcnum;

//頂點(diǎn)數(shù)和邊數(shù) GraphTypekind;//圖的類型}MGraph;無(wú)向圖的鄰接矩陣的特點(diǎn)？無(wú)向圖的鄰接矩陣V1V3V4V2V1V2V3V4vexs=0101101101001100arcs=V1V2V3V4V1V2V3V4主對(duì)角線為0且一定是對(duì)稱矩陣。7.1知識(shí)學(xué)習(xí)——圖的存儲(chǔ)結(jié)構(gòu)如何求頂點(diǎn)i的度？V1V3V4V2V1V2V3V4vexs=0101101101001100arcs=V1V2V3V4V1V2V3V4鄰接矩陣的第i行（或第i列）非零元素的個(gè)數(shù)。無(wú)向圖的鄰接矩陣7.1知識(shí)學(xué)習(xí)——圖的存儲(chǔ)結(jié)構(gòu)如何判斷頂點(diǎn)i和j之間是否存在邊？V1V3V4V2V1V2V3V4vexs=0101101101001100arcs=V1V2V3V4V1V2V3V4測(cè)試鄰接矩陣中相應(yīng)位置的元素arcs[i][j]是否為1。無(wú)向圖的鄰接矩陣7.1知識(shí)學(xué)習(xí)——圖的存儲(chǔ)結(jié)構(gòu)如何求頂點(diǎn)i的所有鄰接點(diǎn)？V1V3V4V2V1V2V3V4vexs=0101101101001100arcs=V1V2V3V4V1V2V3V4將數(shù)組中第i

行元素掃描一遍，若arcs[i][j]為1，則頂點(diǎn)j

為頂點(diǎn)i的鄰接點(diǎn)。無(wú)向圖的鄰接矩陣7.1知識(shí)學(xué)習(xí)——圖的存儲(chǔ)結(jié)構(gòu)V1V2V3V4V1V2V3V4vexs=0110000000011000arcs=V1V2V3V4V1V2V3V4有向圖的鄰接矩陣一定不對(duì)稱嗎？不一定，例如有向完全圖。有向圖的鄰接矩陣7.1知識(shí)學(xué)習(xí)——圖的存儲(chǔ)結(jié)構(gòu)V1V2V3V4V1V2V3V4vexs=0110000000011000arcs=V1V2V3V4V1V2V3V4如何求頂點(diǎn)i的出度？鄰接矩陣的第i行元素之和。有向圖的鄰接矩陣7.1知識(shí)學(xué)習(xí)——圖的存儲(chǔ)結(jié)構(gòu)V1V2V3V4V1V2V3V4vexs=0110000000011000arcs=V1V2V3V4V1V2V3V4如何求頂點(diǎn)i的入度？鄰接矩陣的第i列元素之和。有向圖的鄰接矩陣7.1知識(shí)學(xué)習(xí)——圖的存儲(chǔ)結(jié)構(gòu)V1V2V3V4V1V2V3V4vexs=0110000000011000arcs=V1V2V3V4V1V2V3V4如何判斷從頂點(diǎn)i到頂點(diǎn)j是否存在邊？測(cè)試鄰接矩陣中相應(yīng)位置的元素arcs[i][j]是否為1。有向圖的鄰接矩陣7.1知識(shí)學(xué)習(xí)——圖的存儲(chǔ)結(jié)構(gòu)網(wǎng)圖的鄰接矩陣可定義為：

arcs[i][j]＝

wij

若(vi,vj)∈E（或<vi,vj>∈E）0若i=j∞其他V1V2V3V42785025∞∞0∞

∞

∞

∞087∞∞0arcs=7.1知識(shí)學(xué)習(xí)——圖的存儲(chǔ)結(jié)構(gòu)7.1知識(shí)學(xué)習(xí)——圖的存儲(chǔ)結(jié)構(gòu)無(wú)向網(wǎng)的鄰接矩陣構(gòu)造voidCreateMGraph(MGraph&G){

inti,j,va,vb; G.kind=UG;

cout<<"請(qǐng)輸入圖的頂點(diǎn)數(shù)：";

cin>>G.vexnum;

cout<<"請(qǐng)輸入圖的邊數(shù)：";

cin>>G.arcnum;

cout<<"請(qǐng)輸入頂點(diǎn)的信息："; for(i=0;i<G.vexnum;i++)

cin>>G.vexs[i];

for(i=0;i<G.vexnum;i++) for(j=0;j<G.vexnum;j++) G.arcs[i][j]=0; cout<<"請(qǐng)輸入邊的信息：";

for(i=0;i<G.arcnum;i++)

{

cin>>va>>vb;G.arcs[va][vb]=1;G.arcs[vb][va]=1;}}7.1知識(shí)學(xué)習(xí)——圖的存儲(chǔ)結(jié)構(gòu)1.鄰接矩陣（數(shù)組表示法）圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)的空間復(fù)雜度？如果為稀疏圖則會(huì)出現(xiàn)什么現(xiàn)象？假設(shè)圖G有n個(gè)頂點(diǎn)e條邊，則存儲(chǔ)該圖需要O(n2)。7.1知識(shí)學(xué)習(xí)——圖的存儲(chǔ)結(jié)構(gòu)V1V3V4V2將所有鄰接于vi的頂點(diǎn)鏈成一個(gè)單鏈表，稱為頂點(diǎn)vi的邊表（對(duì)于有向圖則稱為出邊表），所有邊表的頭指針和存儲(chǔ)頂點(diǎn)信息的一維數(shù)組構(gòu)成了頂點(diǎn)表103∧23∧1∧01∧V1V2

V3V401232.鄰接表7.1知識(shí)學(xué)習(xí)——圖的存儲(chǔ)結(jié)構(gòu)datafirstedge頂點(diǎn)表結(jié)點(diǎn)data：數(shù)據(jù)域，存放頂點(diǎn)信息。

firstedge：指針域，指向邊表中第一個(gè)結(jié)點(diǎn)。

typedefstruct{

VertexTypedata;

EdgeListfirstedge;}VexNode;103∧23∧1∧01∧V1V2

V3V401237.1知識(shí)學(xué)習(xí)——圖的存儲(chǔ)結(jié)構(gòu)邊表結(jié)點(diǎn)adjvex：鄰接點(diǎn)域，邊的終點(diǎn)在頂點(diǎn)表中的下標(biāo)next：指針域，指向邊表中的下一個(gè)結(jié)點(diǎn)typedefstructEdgeNode{

intadjvex;

EdgeNode*next;}*EdgeList;adjvexnext103∧23∧1∧01∧V1V2

V3V40123V1V3V4V2無(wú)向圖的鄰接表邊表中的結(jié)點(diǎn)表示什么？每個(gè)結(jié)點(diǎn)對(duì)應(yīng)圖中的一條邊，鄰接表的空間復(fù)雜度為O(n+e)。103∧23∧1∧01∧V1V2

V3V40123V1V3V4V2如何求頂點(diǎn)i的度？頂點(diǎn)i的邊表中結(jié)點(diǎn)的個(gè)數(shù)。無(wú)向圖的鄰接表103∧23∧1∧01∧V1V2

V3V40123如何判斷頂點(diǎn)i和頂點(diǎn)j之間是否存在邊?測(cè)試頂點(diǎn)i的邊表中是否存在終點(diǎn)為j的結(jié)點(diǎn)。V1V3V4V2無(wú)向圖的鄰接表103∧23∧1∧01∧V1V2

V3V40123V1V2V3V412∧3∧0∧V1V2

V3V40123∧如何求頂點(diǎn)i的出度？頂點(diǎn)i的出邊表中結(jié)點(diǎn)的個(gè)數(shù)。有向圖的鄰接表V1V2V3V4如何求頂點(diǎn)i的入度？各頂點(diǎn)的出邊表中以頂點(diǎn)i為終點(diǎn)的結(jié)點(diǎn)個(gè)數(shù)。有向圖的鄰接表12∧3∧0∧V1V2

V3V40123∧V1V2V3V4如何求頂點(diǎn)i的所有鄰接點(diǎn)？遍歷頂點(diǎn)i的邊表，該邊表中的所有終點(diǎn)都是頂點(diǎn)i的鄰接點(diǎn)。有向圖的鄰接表12∧3∧0∧V1V2

V3V40123∧V1V2V3V4278521V1V2

V3V40123datafirstedge∧52∧83∧70∧網(wǎng)圖的鄰接表鄰接表逆鄰接表V1V2V3V412∧3∧0v1v2v3v4∧01231∧3∧0∧2∧v1v2v3v4012303∧7.1知識(shí)學(xué)習(xí)——圖的存儲(chǔ)結(jié)構(gòu)鄰接表的類型定義enumGraphType{DG,UG,DN,UN};//圖的類型定義：有向圖，無(wú)向圖，有向網(wǎng)，無(wú)向網(wǎng)typedefcharVertexType;typedefstructEdgeNode//邊表的結(jié)點(diǎn)類型{

intadjvex;//鄰接點(diǎn)存儲(chǔ)位置

EdgeNode*next;//指向下一個(gè)鄰接點(diǎn)}*EdgeList;typedefstruct//頂點(diǎn)表的元素類型{

VertexTypedata;//頂點(diǎn)信息

EdgeListfirstedge;//邊表的頭指針}VexNode;typedefstruct{

VexNodeadjlist[MAX];//頂點(diǎn)表

intvexnum,arcnum;//頂點(diǎn)數(shù)和邊數(shù)

GraphTypekind;//圖的類型}ALGraph;7.1知識(shí)學(xué)習(xí)——圖的存儲(chǔ)結(jié)構(gòu)鄰接表的構(gòu)建1.確定圖的頂點(diǎn)個(gè)數(shù)和邊的個(gè)數(shù)；2.

初始化頂點(diǎn)表；3.依次輸入每條邊創(chuàng)建鄰接表；

3.1輸入邊依附的兩個(gè)頂點(diǎn)的序號(hào)i,j；

3.2創(chuàng)建新結(jié)點(diǎn)，在表頭插入；(注意無(wú)向圖、無(wú)向網(wǎng)、有向圖、有向網(wǎng)的區(qū)別)O(n2)O(n+e)O(n2)O(n+e)空間性能時(shí)間性能適用范圍唯一性鄰接矩陣鄰接表稠密圖稀疏圖唯一不唯一圖的存儲(chǔ)結(jié)構(gòu)的比較——鄰接矩陣和鄰接表圖的遍歷是在從圖中某一頂點(diǎn)出發(fā)，對(duì)圖中所有頂點(diǎn)訪問(wèn)一次且僅訪問(wèn)一次。

抽象操作，可以是對(duì)結(jié)點(diǎn)進(jìn)行的各種處理，這里簡(jiǎn)化為輸出結(jié)點(diǎn)的數(shù)據(jù)。下面僅討論從某頂點(diǎn)出發(fā)遍歷圖的算法。7.1知識(shí)學(xué)習(xí)——

圖的遍歷7.1知識(shí)學(xué)習(xí)——圖的遍歷圖的遍歷操作要解決的關(guān)鍵問(wèn)題1因圖中可能存在回路，某些頂點(diǎn)可能會(huì)被重復(fù)訪問(wèn)，那么如何避免遍歷因回路而陷入死循環(huán)。解決方案：附設(shè)訪問(wèn)標(biāo)志數(shù)組visited[n]2在圖中，一個(gè)頂點(diǎn)可以和其它多個(gè)頂點(diǎn)相連，當(dāng)這樣的頂點(diǎn)訪問(wèn)過(guò)后，如何選取下一個(gè)要訪問(wèn)的頂點(diǎn)？解決方案：深度優(yōu)先遍歷和廣度優(yōu)先遍歷。7.1知識(shí)學(xué)習(xí)——圖的遍歷1.深度優(yōu)先遍歷DFS(MGraphG,intv)基本思想：⑴訪問(wèn)頂點(diǎn)v；⑵從v的未被訪問(wèn)的鄰接點(diǎn)中選取一個(gè)頂點(diǎn)i，

從i出發(fā)進(jìn)行深度優(yōu)先遍歷；⑶重復(fù)上述兩步，直至圖中所有和v有路徑相通的頂點(diǎn)都被訪問(wèn)到。cout<<G.vexs[v];//訪問(wèn)第v個(gè)頂點(diǎn)visited[v]=true;//設(shè)置訪問(wèn)標(biāo)志為1（已訪問(wèn)）for(inti=0;i<G.vexnum;i++)if(G.arcs[v][i]!=0&&!visited[i])

DFS(G,i);//連通圖的深度優(yōu)先遍歷遞歸算法boolvisited[MAX]={false};voidDFS(MGraphG,intv){ cout<<G.vexs[v]; visited[v]=true; for(inti=0;i<G.vexnum;i++) { if(G.arcs[v][i]!=0&&!visited[i]) DFS(G,i); }}深度優(yōu)先遍歷7.1知識(shí)學(xué)習(xí)——圖的遍歷2.廣度優(yōu)先遍歷基本思想：⑴訪問(wèn)頂點(diǎn)v；⑵依次訪問(wèn)v的各個(gè)未被訪問(wèn)的鄰接點(diǎn)w1,w2,…,wt；⑶分別從w1，w2，…，wt出發(fā)依次訪問(wèn)它們未被訪問(wèn)的鄰接點(diǎn)，并使“先被訪問(wèn)頂點(diǎn)的鄰接點(diǎn)”先于“后被訪問(wèn)頂點(diǎn)的鄰接點(diǎn)”被訪問(wèn)。直至圖中所有與頂點(diǎn)v有路徑相通的頂點(diǎn)都被訪問(wèn)到。voidBFSTraverse(MGraphG,intv){ bool*visited=newbool[G.vexnum]; SeqQueueq;

inti,j,u; InitQueue(q); for(i=0;i<G.vexnum;i++)

visited[i]=false;

for(i=0;i<G.vexnum;i++)

{

if(!visited[i])

{

cout<<G.vexs[i]<<""; visited[i]=true; EnQueue(q,i); while(!QueueEmpty(q))

{

u=DeQueue(q); for(j=0;j<G.vexnum;j++)

{

if(G.arcs[u][j]==1&&!visited[j])

{

cout<<G.vexs[j]<<"";

visited[j]=true;

EnQueue(q,j); } } } } } delete[]visited;}廣度優(yōu)先遍歷圖的遍歷算法的應(yīng)用無(wú)向圖的連通性的判斷要想判定一個(gè)無(wú)向圖是否為連通圖，或有幾個(gè)連通分量，通過(guò)對(duì)無(wú)向圖遍歷即可得到結(jié)果。連通圖：僅需從圖中任一頂點(diǎn)出發(fā)，進(jìn)行深度優(yōu)先搜索（或廣度優(yōu)先搜索），便可訪問(wèn)到圖中所有頂點(diǎn)。非連通圖：需從多個(gè)頂點(diǎn)出發(fā)進(jìn)行搜索，而每一次從一個(gè)新的起始點(diǎn)出發(fā)進(jìn)行搜索過(guò)程中得到的頂點(diǎn)訪問(wèn)序列恰為其各個(gè)連通分量中的頂點(diǎn)集。7.1知識(shí)學(xué)習(xí)——最小生成樹有向圖的連通性的判斷⑴從某頂點(diǎn)出發(fā)進(jìn)行深度優(yōu)先遍歷，并按其所有鄰接點(diǎn)都訪問(wèn)（即出棧）的順序?qū)㈨旤c(diǎn)排列起來(lái)。⑵從最后完成訪問(wèn)的頂點(diǎn)出發(fā)，沿著以該頂點(diǎn)為頭的弧作逆向的深度優(yōu)先遍歷。若不能訪問(wèn)到所有頂點(diǎn)，則從余下的頂點(diǎn)中最后訪問(wèn)的那個(gè)頂點(diǎn)出發(fā)，繼續(xù)作逆向的深度優(yōu)先遍歷，直至有向圖中所有頂點(diǎn)都被訪問(wèn)到為止。⑶每一次逆向深度優(yōu)先遍歷所訪問(wèn)到的頂點(diǎn)集便是該有向圖的一個(gè)強(qiáng)連通分量的頂點(diǎn)集。（a）深度優(yōu)先生成樹（b）廣度優(yōu)先生成樹V1V3V2V4V5V6V7V8V1V3V2V4V5V6V7V87.1知識(shí)學(xué)習(xí)——最小生成樹7.1知識(shí)學(xué)習(xí)——最小生成樹由深度優(yōu)先遍歷得到的為深度優(yōu)先生成樹，由廣度優(yōu)先遍歷得到的為廣度優(yōu)先生成樹。一個(gè)連通圖的生成樹可能不唯一，由不同的遍歷次序、從不同頂點(diǎn)出發(fā)進(jìn)行遍歷都會(huì)得到不同的生成樹。對(duì)于非連通圖，通過(guò)圖的遍歷，將得到的是生成森林。7.1知識(shí)學(xué)習(xí)——最小生成樹生成樹的代價(jià)：設(shè)G=(V，E)是一個(gè)無(wú)向連通網(wǎng)，生成樹上各邊的權(quán)值之和稱為該生成樹的代價(jià)。最小生成樹：在圖G所有生成樹中，代價(jià)最小的生成樹稱為最小生成樹。最小生成樹的概念可以應(yīng)用到許多實(shí)際問(wèn)題中。例：在n個(gè)城市之間建造通信網(wǎng)絡(luò)，至少要架設(shè)n-1條通信線路，而每?jī)蓚€(gè)城市之間架設(shè)通信線路的造價(jià)是不一樣的，那么如何設(shè)計(jì)才能使得總造價(jià)最?。?.1知識(shí)學(xué)習(xí)——最小生成樹

U={A}V-U={B,C,D,E,F}342465713ABEDCFPrim算法5adjvexlowcost0(A)001(B)022(C)053(D)044(E)0INFINIT5(F)0INFINITU={A,B}V-U={C,D,E,F}342465713ABEDCFPrim算法5adjvexlowcost0(A)001(B)022(C)053(D)044(E)0INFINIT5(F)0INFINIT04511U={A,B,C}V-U={D,E,F}342465713ABEDCFPrim算法5adjvexlowcost0(A)001(B)002(C)143(D)044(E)155(F)0INFINIT33022U={A,B,C,E}V-U={D,F}342465713ABEDCFPrim算法5adjvexlowcost0(A)001(B)002(C)103(D)044(E)235(F)2INFINIT104U={A,B,C,E,F}V-U={D}342465713ABEDCFPrim算法5adjvexlowcost0(A)001(B)002(C)103(D)044(E)205(F)410U={A,B,C,E,F,D}V-U={}342465713ABEDCFPrim算法5adjvexlowcost0(A)001(B)002(C)103(D)044(E)205(F)400Prim算法的關(guān)鍵：如何找到連接U和V-U的最短邊?？梢杂孟率龇椒?gòu)造候選最短邊集：對(duì)應(yīng)V-U中的每個(gè)頂點(diǎn)，保留從該頂點(diǎn)到U中的各頂點(diǎn)的最短邊。Prim算法Prim算法引入一個(gè)輔助數(shù)組miniedges[]，用于存放集合V

U中的各頂點(diǎn)到集合U中頂點(diǎn)的最小交叉邊及其權(quán)值，miniedges[]數(shù)組的元素類型定義如下：typedefstruct{VertexTypevex; floatlowcost; }Edge;

1.初始化輔助數(shù)組miniedges[]；2.輸出頂點(diǎn)v，將頂點(diǎn)v加入集合U中；3.重復(fù)執(zhí)行下列操作n-1次

3.1選取出權(quán)值最小的候選交叉邊，取對(duì)應(yīng)的頂點(diǎn)序號(hào)k；3.2將頂點(diǎn)k加入集合U中；

3.3調(diào)整數(shù)組miniedges[]；Prim算法Kruskal算法Kruskal算法基本思想：設(shè)無(wú)向連通網(wǎng)為G＝(V,E)，令G的最小生成樹為T＝(U,TE)，其初態(tài)為U＝V，TE＝{}，然后，按照邊的權(quán)值由小到大的順序，考察G的邊集E中的各條邊。若被考察的邊的兩個(gè)頂點(diǎn)屬于T的兩個(gè)不同的連通分量，則將此邊作為最小生成樹的邊加入到T中，同時(shí)把兩個(gè)連通分量連接為一個(gè)連通分量；若被考察邊的兩個(gè)頂點(diǎn)屬于同一個(gè)連通分量，則舍去此邊，以免造成回路。如此下去，當(dāng)T中的連通分量個(gè)數(shù)為1時(shí)，此連通分量便為G的一棵最小生成樹。連通分量＝{A},{B},{C},{D},{E},{F}Kruskal算法342465713ABEDCF5ABEDCF連通分量＝{A},{B},{C},{D},{E,F}Kruskal算法342465713ABEDCF5ABEDCF1連通分量＝{A,B},{C},{D},{E,F}Kruskal算法342465713ABEDCF5ABEDCF12連通分量＝{A,B},

{D},{C,E,F}Kruskal算法342465713ABEDCF5ABEDCF123連通分量＝{A,B,D},{C,E,F}Kruskal算法342465713ABEDCF5ABEDCF1234連通分量＝{A,B,C,D,E,F}Kruskal算法342465713ABEDCF5ABEDCF123441.初始化：U=V；TE={}；2.循環(huán)直到T中的連通分量個(gè)數(shù)為12.1在E中尋找最短邊(u，v);2.2如果頂點(diǎn)u、v位于T的兩個(gè)不同連通分量，則

2.2.1將邊(u，v)并入TE；

2.2.2將這兩個(gè)連通分量合為一個(gè)；

2.3在E中標(biāo)記邊(u，v)，使得(u，v)不參加后續(xù)最短邊的選??；Kruskal算法7.1知識(shí)學(xué)習(xí)——最短路徑在非網(wǎng)圖中，最短路徑是指兩頂點(diǎn)之間經(jīng)歷的邊數(shù)最少的路徑。在網(wǎng)圖中，最短路徑是指兩頂點(diǎn)之間經(jīng)歷的邊上權(quán)值之和最短的路徑。7.1知識(shí)學(xué)習(xí)——最短路徑單源點(diǎn)最短路徑問(wèn)題

問(wèn)題描述：給定帶權(quán)有向圖G＝(V,E)和源點(diǎn)v∈V，求從v到G中其余各頂點(diǎn)的最短路徑。迪杰斯特拉（Dijkstra）提出了一個(gè)按路徑長(zhǎng)度遞增的次序產(chǎn)生最短路徑的算法——Dijkstra算法。BAEDC105030101002060S={A}A→B:(A,B)10A→C:(A,C)∞A→D:(A,D)30A→E:(A,E)100Dijkstra算法AEDC105030101002060S={A,B}A→B:(A,B)10A→C:(A,B,C)60A→D:(A,D)30A→E:(A,E)100Dijkstra算法BAEC105030101002060S={A,B,D}A→B:(A,B)10A→C:(A,D,C)50A→D:(A,D)30A→E:(A,D,E)90Dijkstra算法BDAE105030101002060S={A,B,

D,C}A→B:(A,B)10A→C:(A,D,C)50A→D:(A,D)30A→E:(A,D,C,E)60Dijkstra算法BDCA105030101002060S={A,B,

D,

C,E}A→B:(A,B)10A→C:(A,B,C)60A→D:(A,D)30A→E:(A,D,C,E)60Dijkstra算法BDCE圖的存儲(chǔ)結(jié)構(gòu)：帶權(quán)的鄰接矩陣存儲(chǔ)結(jié)構(gòu)數(shù)組dist[n]：每個(gè)分量dist[i]表示當(dāng)前所找到的從始點(diǎn)v到終點(diǎn)vi的最短路徑的長(zhǎng)度。初態(tài)為：若從v到vi有弧，則dist[i]為弧上權(quán)值；否則置dist[i]為∞。數(shù)組path[n]：保存從源點(diǎn)到各頂點(diǎn)的。path[i]中保存了從源點(diǎn)到終點(diǎn)vi的最短路徑上該頂點(diǎn)的前驅(qū)頂點(diǎn)的序號(hào)。數(shù)組s[n]：記錄已求出最短路徑的頂點(diǎn)集合S，s[i]為true表示頂點(diǎn)vi已在集合S中。Dijkstra算法1.初始化數(shù)組dist、path和s；2.while(s中的元素個(gè)數(shù)<n)2.1在dist[n]中求最小值，其下標(biāo)為k；

2.2將頂點(diǎn)vk添加到數(shù)組s中；

2.3修改數(shù)組dist和path；

Dijkstra算法——偽代碼每一對(duì)頂點(diǎn)之間的最短路徑問(wèn)題描述：給定帶權(quán)有向圖G＝(V,E)，對(duì)任意頂點(diǎn)vi,vj∈V（i≠j），求頂點(diǎn)vi到頂點(diǎn)vj的最短路徑。方法1：每次以一個(gè)頂點(diǎn)為源點(diǎn)，調(diào)用Dijkstra算法n次。顯然，時(shí)間復(fù)雜度為O(n3)。方法2：弗洛伊德提出的求每一對(duì)頂點(diǎn)之間的最短路徑算法——Floyd算法，其時(shí)間復(fù)雜度也是O(n3)，但形式上要簡(jiǎn)單些。04116023∞0有向網(wǎng)圖鄰接矩陣acb346112Floyd算法acb346112dist-1

=04116023∞0path-1

=

abacbabcca初始化Floyd算法acb346112dist-1

=04116023∞0path-1

=

abacbabcca第1次迭代dist0

=0411602370path0

=

abacbabccacab

Floyd算法acb346112第2次迭代dist0

=0411602370path0

=

abacbabccacabdist1

=046602370path1

=

ababc

babccacabFloyd算法acb346112第3次迭代dist2

=046502370path2

=

ababcbcabccacabdist1

=046602370path1

=

ababcbabccacabFloyd算法圖的存儲(chǔ)結(jié)構(gòu)：帶權(quán)的鄰接矩陣存儲(chǔ)結(jié)構(gòu)數(shù)組D[n][n]：存放在迭代過(guò)程中求得的最短路徑長(zhǎng)度。數(shù)組path[n][n]：path[i][j]中存放的是從頂點(diǎn)vi到頂點(diǎn)vj中間頂點(diǎn)序號(hào)不大于k的最短路徑上的頂點(diǎn)vi的后繼頂點(diǎn)的序號(hào)。

設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)導(dǎo)學(xué)問(wèn)題1的實(shí)現(xiàn)：

導(dǎo)學(xué)問(wèn)題1就是構(gòu)造連通網(wǎng)的最小生成樹的問(wèn)題。導(dǎo)學(xué)問(wèn)題2的實(shí)現(xiàn)：

導(dǎo)學(xué)問(wèn)題2就是求兩個(gè)頂點(diǎn)間最短路徑的問(wèn)題。7.2知識(shí)應(yīng)用

7.3知識(shí)拓展——AOV網(wǎng)與拓?fù)渑判蚴裁碅OV網(wǎng)？AOV網(wǎng)：在一個(gè)表示工程的有向圖中，用頂點(diǎn)表示活動(dòng)，用弧表示活動(dòng)之間的優(yōu)先關(guān)系，稱這樣的有向圖為頂點(diǎn)表示活動(dòng)的網(wǎng)，簡(jiǎn)稱AOV網(wǎng)。AOV網(wǎng)中出現(xiàn)回路意味著什么？7.3知識(shí)拓展——AOV網(wǎng)與拓?fù)渑判駻OV網(wǎng)特點(diǎn)：1.AOV網(wǎng)中的弧表示活動(dòng)之間存在的某種制約關(guān)系。2.AOV網(wǎng)中不能出現(xiàn)回路。編號(hào)課程名稱先修課C1高等數(shù)學(xué)無(wú)C2計(jì)算機(jī)導(dǎo)論無(wú)C3離散數(shù)學(xué)C1C4程序設(shè)計(jì)C1,C2C5數(shù)據(jù)結(jié)構(gòu)C3，C4C6計(jì)算機(jī)原理C2，C4C7數(shù)據(jù)庫(kù)原理C4，C5，C6C1C2C3C4C6C5C7AOV網(wǎng)拓?fù)渑判蛲負(fù)湫蛄校涸O(shè)G=(V，E)是一個(gè)具有n個(gè)頂點(diǎn)的有向圖，V中的頂點(diǎn)序列v1,v2,…,vn稱為一個(gè)拓?fù)湫蛄校?dāng)且僅當(dāng)滿足下列條件：若從頂點(diǎn)vi到vj有一條路徑，則在頂點(diǎn)序列中頂點(diǎn)vi必在頂點(diǎn)vj之前。拓?fù)渑判颍簩?duì)一個(gè)有向圖構(gòu)造拓?fù)湫蛄械倪^(guò)程稱為拓?fù)渑判颉Ｍ負(fù)渑判蚧舅枷耄孩艔腁OV網(wǎng)中選擇一個(gè)沒有前驅(qū)的頂點(diǎn)并且輸出；⑵從AOV網(wǎng)中刪去該頂點(diǎn)，并且刪去所有以該頂點(diǎn)為尾的弧；⑶重復(fù)上述兩步，直到全部頂點(diǎn)都被輸出，或AOV網(wǎng)中不存在沒有前驅(qū)的頂點(diǎn)。C1C2C3C4C6C5C7拓?fù)湫蛄校篊1,拓?fù)渑判駽2C3C4C6C5C7拓?fù)湫蛄校篊1,C2,拓?fù)渑判駽3C4C6C5C7拓?fù)湫蛄校篊1,C2,C3,拓?fù)渑判駽4C6C5C7拓?fù)湫蛄校篊1,C2,C3,C4,拓?fù)渑判駽6C5C7拓?fù)湫蛄校篊1,C2,C3,C4,C5,拓?fù)渑判駽6C7拓?fù)湫蛄校篊1,C2,C3,C4,C5,C6,拓?fù)渑判駽7拓?fù)湫蛄校篊1,C2,C3,C4,C5,C6,C7,拓?fù)渑判蛟O(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)1.圖的存儲(chǔ)結(jié)構(gòu)：宜采用鄰接表存儲(chǔ)。2.為便于算法執(zhí)行過(guò)程中考察每個(gè)頂點(diǎn)的入度，即查找沒有前驅(qū)的頂點(diǎn)，可引入一個(gè)存放各頂點(diǎn)入度的數(shù)組indegree[]。3.為了避免每一步選入度為0的頂點(diǎn)時(shí)重復(fù)掃描數(shù)組indegree，可設(shè)置一個(gè)隊(duì)列（或棧）來(lái)存儲(chǔ)所有入度為0的頂點(diǎn)。在進(jìn)行拓?fù)渑判蛑埃灰獙?duì)頂點(diǎn)表掃描一遍，將所有入度為0的頂點(diǎn)都排入隊(duì)列中，一旦排序過(guò)程中出現(xiàn)新的入度為0的頂點(diǎn)，也同樣將其排入隊(duì)列中。

(a)一個(gè)AOV網(wǎng)(b)AOV網(wǎng)的鄰接表存儲(chǔ)0123456

indgreevertexfirstedgeA

B

C

D

E

F

G∧

2

4

5

4∧

6∧ABGDEF拓?fù)渑判駽

3

4

6∧

5∧

4∧

6∧

3(a)一個(gè)AOV網(wǎng)(b)AOV網(wǎng)的鄰接表存儲(chǔ)0123456

indgreevertexfirstedge0A0B1C2D4E2F

3

G∧

2

4

5

4∧

6∧ABGDEF拓?fù)渑判駽

3

4

6∧

5∧

4∧

6∧

3AB(a)一個(gè)AOV網(wǎng)(b)AOV網(wǎng)的鄰接表存儲(chǔ)0123456

indgreevertexfirstedge0A0B1C2D4E2F

3

G∧

2

4

5

4∧

6∧ABGDEF拓?fù)渑判駽

3

4

6∧

5∧

4∧

6∧

3132AB(a)一個(gè)AOV網(wǎng)(b)AOV網(wǎng)的鄰接表存儲(chǔ)0123456

indgreevertexfirstedge0A0B1C1D3E2F

2

G∧

2

4

5

4∧

6∧BGDEF拓?fù)渑判駽

3

4

6∧

5∧

4∧

6∧

3021BAC(a)一個(gè)AOV網(wǎng)(b)AOV網(wǎng)的鄰接表存儲(chǔ)0123456

indgreevertexfirstedge0A0B0C1D2E1F

2

G∧

2

4

5

4∧

6∧GDEF拓?fù)渑判駽

3

4

6∧

5∧

4∧

6∧

301CADB(a)一個(gè)AOV網(wǎng)(b)AOV網(wǎng)的鄰接表存儲(chǔ)0123456

indgreevertexfirstedge0A0B0C0D1E1F

2

G∧

2

4

5

4∧

6∧GDEF拓?fù)渑判?/p>

3

4

6∧

5∧

4∧

6∧

30DAEBC(a)一個(gè)AOV網(wǎng)(b)AOV網(wǎng)的鄰接表存儲(chǔ)0123456

indgreevertexfirstedge0A0B0C0D0E1F

2

G∧

2

4

5

4∧

6∧GEF拓?fù)渑判?/p>

3

4

6∧

5∧

4∧

6∧

31EAFBCD0(a)一個(gè)AOV網(wǎng)(b)AOV網(wǎng)的鄰接表存儲(chǔ)0123456

indgreevertexfirstedge0A0B0C0D0E0F

1

G∧

2

4

5

4∧

6∧GF拓?fù)渑判?/p>

3

4

6∧

5∧

4∧

6∧

3FAGBCD0E(a)一個(gè)AOV網(wǎng)(b)AOV網(wǎng)的鄰接表存儲(chǔ)0123456

indgreevertexfirstedge0A0B0C0D0E0F

0

G∧

2

4

5

4∧

6∧G拓?fù)渑判?/p>

3

4

6∧

5∧

4∧

6∧

3GABCDEF1.隊(duì)列s初始化；累加器c初始化；2.掃描頂點(diǎn)表，將沒有前驅(qū)的頂點(diǎn)入隊(duì)；3.當(dāng)隊(duì)列s非空時(shí):

3.1頂點(diǎn)i出隊(duì)，并輸出；累加器加1；

3.2將頂點(diǎn)i的各個(gè)鄰接點(diǎn)的入度減1；

3.3將新的入度為0的頂點(diǎn)入隊(duì)；4.if(c<圖的頂點(diǎn)個(gè)數(shù))輸出“有回路”信息；拓?fù)渑判蛩惴ā獋未a事件事件含義

v1開工

v2

活動(dòng)a1完成，活動(dòng)a4可以開始

v3活動(dòng)a2完成，活動(dòng)a5可以開始

…………v9活動(dòng)a10

和a11完成，整個(gè)工程完成v2v1v3v4v5v8v6v7v9a1=6a4=1a7=9a10=2a11=4a8=7a9=4a5=1a6=2a3=5a2=47.3知識(shí)拓展——AOE網(wǎng)與關(guān)鍵路徑v2v1v3v4v5v8v6v7v9a1=6a4=1a7=9a10=2a11=4a8=7a9=4a5=1a6=2a3=5a2=47.3知識(shí)拓展——AOE網(wǎng)與關(guān)鍵路徑AOE網(wǎng)可以回答下列問(wèn)題：1.完成整個(gè)工程至少需要多少時(shí)間?2.為縮短完成工程所需的時(shí)間,應(yīng)當(dāng)加快哪些活動(dòng)?v2v1v3v4v5v8v6v7v9a1=6a4=1a7=9a10=2a11=4a8=7a9=4a5=1a6=2a3=5a2=47.3知識(shí)拓展——AOE網(wǎng)與關(guān)鍵路徑從始點(diǎn)到終點(diǎn)的路徑可能不止一條，只有各條路徑上所有活動(dòng)都完成了，整個(gè)工程才算完成。因此，完成整個(gè)工程所需的最短時(shí)間取決于從始點(diǎn)到終點(diǎn)的最長(zhǎng)路徑長(zhǎng)度，即這條路徑上所有活動(dòng)的持續(xù)時(shí)間之和。這條路徑長(zhǎng)度最長(zhǎng)的路徑就叫做關(guān)鍵路徑。關(guān)鍵路徑：在AOE網(wǎng)中，從始點(diǎn)到終點(diǎn)