7第七章-圖120張課件

?7.1圖的定義和基本術(shù)語7.2圖的存儲結(jié)構(gòu)7.3圖的遍歷7.4圖的生成樹7.5拓?fù)渑判?.6關(guān)鍵路徑7.7最短路徑第七章圖?7.1圖的定義和基本術(shù)語第七章圖1圖(Graph)——圖G是由兩個(gè)集合V(G)和E(G)組成的,記為G=(V,E)其中：V(G)是頂點(diǎn)的非空有限集E(G)是邊的有限集合，邊是頂點(diǎn)的無序?qū)蛴行驅(qū)D的定義和術(shù)語【例】157324G16V(G1)={1,2,3,4,5,6,7}E(G1)={(1,2),(1,3),(2,3),(2,4),(2,5),(5,6),(5,7)}圖(Graph)——圖G是由兩個(gè)集合V(G)和E(G)組成的2無向圖

——無向圖G是由兩個(gè)集合V(G)和E(G)組成的其中：V(G)是頂點(diǎn)的非空有限集

E(G)是邊的有限集合，邊是頂點(diǎn)的無序?qū)?，記?/p>

（v,w）或（w,v)，并且（v,w)=(w,v)簡單的圖：圖中不包含頂點(diǎn)到其自身的弧或邊，同一條弧或邊不在圖中重復(fù)出現(xiàn)有向圖&無向圖

有向圖——有向圖G是由兩個(gè)集合V(G)和E(G)組成的其中：V(G)是頂點(diǎn)的非空有限集

E(G)是有向邊（也稱弧）的有限集合，弧是頂點(diǎn)的有序?qū)?，記?lt;v,w>，v,w是頂點(diǎn)，v為弧尾，w為弧頭無向圖——無向圖G是由兩個(gè)集合V(G)和E(G)組成的簡3【有向圖G2】245136G2V(G2)={1,2,3,4,5,6}E(G2)={<1,2>,<2,1>,<2,3>,<2,4>,<3,5>,<5,6>,<6,3>}【有向圖G2】245136G2V(G2)={1,2,3,4權(quán)

——與圖的邊或弧相關(guān)的數(shù)網(wǎng)——帶權(quán)的圖叫~1452375318642G3子圖

——如果圖G(V,E)和圖G’(V’,E’),滿足：V’VE’E則稱G’為G的子圖356245136圖與子圖無向圖&有向圖&無向網(wǎng)&有向網(wǎng)UDGDGUDNDN權(quán)——與圖的邊或弧相關(guān)的數(shù)網(wǎng)——帶權(quán)的圖叫~145235有向完全圖

——n個(gè)頂點(diǎn)的有向圖最大邊數(shù)是n(n-1)入度：以該頂點(diǎn)為頭的弧的數(shù)目頂點(diǎn)的度無向圖中，頂點(diǎn)的度為與每個(gè)頂點(diǎn)相關(guān)聯(lián)的邊數(shù)有向圖中，頂點(diǎn)的度分成入度與出度出度：以該頂點(diǎn)為尾的弧的數(shù)目bac有向完全圖bac無向完全圖無向完全圖

——n個(gè)頂點(diǎn)的無向圖最大邊數(shù)是n(n-1)/2鄰接點(diǎn)——無向圖G(V,E)中，如果邊(u，v)∈E，則稱頂點(diǎn)u，v互為鄰接點(diǎn)，或者稱頂點(diǎn)u，v相關(guān)聯(lián)有向完全圖——n個(gè)頂點(diǎn)的有向圖最大邊數(shù)是n(n-1)入度6【例】245136G2頂點(diǎn)2入度：1出度：3頂點(diǎn)4入度：1出度：0【例】157324G16頂點(diǎn)5的度：3頂點(diǎn)2的度：4G2中{1，2，3，5，6}是一條路徑G1中{1，2，5，7}是一條路徑例如路徑

——路徑是頂點(diǎn)的序列V={Vi0,Vi1,……Vin}，滿足

(Vij-1,Vij)E（1<jn)【例】245136G2頂點(diǎn)2入度：1出度：3【例】17路徑長度——路徑上邊或弧的數(shù)目或沿路徑各邊權(quán)值之和回路——第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑簡單路徑——序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑簡單回路——除了第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)外，其余頂點(diǎn)不重復(fù)出現(xiàn)的回路叫簡單回路aegcbfG1d{a，b，e，d}路徑長度是3bdeacfG2{a，b，c，e}是一條路徑路徑長度——路徑上邊或弧的數(shù)目或沿路徑各邊權(quán)值之和回路——第8連通——無向圖從頂點(diǎn)v到頂點(diǎn)w有一條路徑，則說v和w是連通的連通圖——無向圖中任意兩個(gè)頂點(diǎn)都是連通的叫連通圖連通分量——無向圖的極大連通子圖叫連通分量【連通圖】bdeacfbdeacf【有2個(gè)連通分量的無向圖】連通——無向圖從頂點(diǎn)v到頂點(diǎn)w有一條路徑，則說v和w是連通的9強(qiáng)連通分量——有向圖的極大強(qiáng)連通子圖叫強(qiáng)連通分量強(qiáng)連通圖——有向圖中，如果對每一對頂點(diǎn)間都存在路徑，則稱G強(qiáng)連通圖

【強(qiáng)連通圖】ABC

【有2個(gè)強(qiáng)連通分量的有向圖】ABCDE強(qiáng)連通分量——有向圖的極大強(qiáng)連通子圖叫強(qiáng)連通分量強(qiáng)連通圖——10【例】157324G26【例】245136G1路徑：1，2，3，5，6，3路徑：1，2，5，7，6，5，2，3簡單回路：3，5，6，3路徑長度：5簡單路徑：1，2，3，5回路：1，2，3，5，6，3，1簡單回路：1，2，3，1路徑長度：7簡單路徑：1，2，5，7，6回路：1，2，5，7，6，5，2，1【例】157324G26【例】245136G1路徑：1，2，117.1圖的定義和基本術(shù)語

?7.2圖的存儲結(jié)構(gòu)7.3圖的遍歷7.4圖的生成樹7.5拓?fù)渑判?.6關(guān)鍵路徑7.7最短路徑第七章圖7.1圖的定義和基本術(shù)語第七章圖127.2.1鄰接矩陣7.2.2鄰接表7.2.3十字鏈表7.24鄰接多重表7.2圖的存儲結(jié)構(gòu)7.2.1鄰接矩陣7.2圖的存儲結(jié)構(gòu)13鄰接矩陣——表示頂點(diǎn)間相聯(lián)關(guān)系的矩陣?yán)鼼22413例15324G1

定義：設(shè)G=(V,E)是有n1個(gè)頂點(diǎn)的圖，G的鄰接矩陣A是具有以下性質(zhì)的n階方陣úúúúú?ùêêêêê?é0001100000000110úúúúúúú?ùêêêêêêê?é00110001011101010101010101A[i,j]=0若(vi,vj)或<vi,vj>E其它鄰接矩陣——表示頂點(diǎn)間相聯(lián)關(guān)系的矩陣?yán)鼼22413例1532141452375318642úúúúúúú?ùêêêêêêê?é∞61836∞24∞12∞∞784∞∞53∞75∞創(chuàng)建一個(gè)以鄰接矩陣存儲的圖

網(wǎng)的鄰接矩陣可定義為：???íì>?<=∞，其它E(G)v,v或)v,(v若,],[jijiijjiAw1452375318642úúúúúúú15typedefstructArcCell{VRTypeadj;InfoType*info;}ArcCell,AdjMatrix[MAX][MAX];typedefstructMGraph{VertexTypevexs[MAX_VERTEX_NUM];AdjMatrixarcs;intvexnum,arcnum;GraphKindkind;}MGraph;MgraphG;typedefstructArcCellMgraphG16例aecbdG1úúúúúúú?ùêêêêêêê?é0011000101110101010101010Gvexsarcsvexnumarcnumkind65UDGabcde例aecbdG1úúúúúúú?ùêêêêêêê?é001117特點(diǎn)：

有向圖鄰接矩陣不一定對稱；有n個(gè)頂點(diǎn)的有向圖需存儲空間為n2

無向圖中頂點(diǎn)Vi的度是鄰接矩陣A中第i行元素之和

有向圖中，

頂點(diǎn)Vi的出度是A中第i行元素之和

頂點(diǎn)Vi的入度是A中第i列元素之和

無向圖的鄰接矩陣對稱，可壓縮存儲；有n個(gè)頂點(diǎn)的無向圖需存儲空間為n(n+1)/2特點(diǎn)：有向圖鄰接矩陣不一定對稱；有n個(gè)頂點(diǎn)的有向圖需存儲空18鄰接表

實(shí)現(xiàn)：為圖中每個(gè)頂點(diǎn)建立一個(gè)單鏈表，第i個(gè)單鏈表中的結(jié)點(diǎn)表示依附于頂點(diǎn)Vi的邊（有向圖中指以Vi為尾的弧）例G1bdac1234acdbvexdatafirstarc

3

2

4

1^^^^adjvexnextarc鄰接表實(shí)現(xiàn)：為圖中每個(gè)頂點(diǎn)建立一個(gè)單鏈表，第i個(gè)單鏈表中的19aecbdG21234acdbdatafirtarc

4

2

1

2^^^adjvexnextarc5e

4

3

5^

1

5

3

2

3^創(chuàng)建一個(gè)以鄰接表存儲的圖aecbdG21234acdbdatafirtarc4220特點(diǎn)G1bdac1234acdbdatafirstarc

4

1^

1^^

3^adjvexnextarc

有向圖中頂點(diǎn)Vi的出度為第i個(gè)單鏈表中的結(jié)點(diǎn)個(gè)數(shù)頂點(diǎn)Vi的入度為整個(gè)單鏈表中鄰接點(diǎn)域值是i的結(jié)點(diǎn)個(gè)數(shù)

無向圖中頂點(diǎn)Vi的度為第i個(gè)單鏈表中的結(jié)點(diǎn)數(shù)

逆鄰接表：有向圖中對每個(gè)結(jié)點(diǎn)建立以Vi為頭的弧的單鏈表特點(diǎn)G1bdac1234acdbdatafirstarc421有向圖的十字鏈表表示法bdac^^^^^^^^創(chuàng)建一個(gè)以十字鏈表存儲的圖

02

01

23

20

32

31

30tailvexheadvexhlinktlinkabcd0123datafirstinfirstout有向圖的十字鏈表表示法bdac^^^^^^^^創(chuàng)建一個(gè)以十22無向圖的鄰接多重表表示法aecbd^^^^^創(chuàng)建一個(gè)以鄰接多重表存儲的圖0123acdb4e

01

03

23

21

24

41ivexjvexilinkjlinkdatafirstedge無向圖的鄰接多重表表示法aecbd^^^^^創(chuàng)建一個(gè)以鄰接多237.1圖的定義和基本術(shù)語7.2圖的存儲結(jié)構(gòu)

?7.3圖的遍歷7.4圖的生成樹7.5拓?fù)渑判?.6關(guān)鍵路徑7.7最短路徑第七章圖7.1圖的定義和基本術(shù)語第七章圖247.3.1深度優(yōu)先遍歷DFS7.3.2廣度優(yōu)先遍歷BFS

7.3圖的遍歷7.3.1深度優(yōu)先遍歷DFS7.3圖的遍歷25

遍歷圖：從圖中某個(gè)頂點(diǎn)出發(fā)游歷圖，訪遍圖中其余頂點(diǎn)，并且使圖中的每個(gè)頂點(diǎn)僅被訪問一次的過程。

深度優(yōu)先遍歷DFS

廣度優(yōu)先遍歷BFS兩種遍歷方法：遍歷圖：從圖中某個(gè)頂點(diǎn)出發(fā)游歷圖，訪遍圖中其余頂點(diǎn)，并且26深度優(yōu)先遍歷(DFS)V1V2V4V5V3V7V6V8深度遍歷：V1V2V4V8V5V3V6V7方法：從圖的某一頂點(diǎn)V0出發(fā)，訪問此頂點(diǎn)；然后依次從V0的未被訪問的鄰接點(diǎn)出發(fā)，深度優(yōu)先遍歷圖，直至圖中所有和V0相通的頂點(diǎn)都被訪問到；若此時(shí)圖中尚有頂點(diǎn)未被訪問，則另選圖中一個(gè)未被訪問的頂點(diǎn)作起點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問為止深度優(yōu)先遍歷(DFS)V1V2V4V5V3V7V6V8深度遍27V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8深度遍歷：V1V2V4V8V5V6V3V7深度遍歷：V1V2V4V8V5V6V3V7V1V2V4V5V3V7V6V8V1V2V4V5V3V7V628V1V2V4V5V3V7V6V8深度遍歷：V1V2V4V8V3V6V7V5V1V2V4V5V3V7V6V8深度遍歷：V1V2V29816273551428764342587361V1V2V4V5V3V7V6V8例深度遍歷：816273551428764342587361V1V2V430V1V2V4V5V3V7V6V8深度遍歷：V112341342vexdatafirstarc

2

7

8

3^^^adjvexnext55

6

4

1^

5

1

2

8

2^678678

7

3

6

3

5

4^^^V3V7V6V2V5V8V4V1V2V4V5V3V7V6V8深度遍歷：V112341331V1V2V4V5V3V7V6V812341342vexdatafirstarc

2

7

8

3^^^adjvexnext55

6^

4

8

2^678678

7^^^深度遍歷：V1V3V7V6V2V4V8V5V1V2V4V5V3V7V6V812341342vexdat32深度優(yōu)先遍歷算法

遞歸算法方法：1）選定任意一點(diǎn)作起始點(diǎn)2）訪問起始點(diǎn)，并標(biāo)注“已訪問”3）對起始點(diǎn)的每一個(gè)鄰接點(diǎn)進(jìn)行如下操作：若該鄰接點(diǎn)未訪問過，以它作為新的起始點(diǎn)進(jìn)行2）3）的操作。（算法特點(diǎn)：遞歸）深度優(yōu)先遍歷算法遞歸算法方法：33DFSTraverse(){for()DFS(G,v)//對非連通圖需要多次出發(fā)DFS}DFS

()//以v為起點(diǎn)深度遍歷{visit(v);//訪問頂點(diǎn)vfor(w=v的第一個(gè)鄰接點(diǎn);w;w=v的下一個(gè)鄰接點(diǎn))DFS(G,w);}DFSTraverse()34廣度優(yōu)先遍歷(BFS)V1V2V4V5V3V7V6V8廣度遍歷：V1V2V3V4V5V6V7V8方法：從圖的某一頂點(diǎn)V0出發(fā)，訪問此頂點(diǎn)后，依次訪問V0的各個(gè)未曾訪問過的鄰接點(diǎn)；然后分別從這些鄰接點(diǎn)出發(fā)，廣度優(yōu)先遍歷圖，直至圖中所有已被訪問的頂點(diǎn)的鄰接點(diǎn)都被訪問到；若此時(shí)圖中尚有頂點(diǎn)未被訪問，則另選圖中一個(gè)未被訪問的頂點(diǎn)作起點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問為止。廣度優(yōu)先遍歷(BFS)V1V2V4V5V3V7V6V8廣度遍35V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8廣度遍歷：V1V2V3V4V5V6V7V8廣度遍歷：V1V2V3V4V5V6V7V8V1V2V4V5V3V7V6V8V1V2V4V5V3V7V636V1V2V4V5V3V7V6V8廣度遍歷：V1V2V3V4V6V7V8V5V1V2V4V5V3V7V6V8廣度遍歷：V1V2V37816273551428764332548671V1V2V4V5V3V7V6V8例廣度遍歷：816273551428764332548671V1V2V438V1V2V4V5V3V7V6V8廣度遍歷：V112341342vexdatafirstarc

2

7

8

3^^^adjvexnext55

6

4

1^

5

1

2

8

2^678678

7

3

6

3

5

4^^^V3V2V5V3V7V5V8V1V2V4V5V3V7V6V8廣度遍歷：V1123413391423512341342vexdatafirstarc

5

5

4

3^^^adjvexnext55

1^

5

1

1

4

3^

2

20123451fr遍歷序列：10123454fr遍歷序列：1401234543fr遍歷序列：1431423512341342vexdatafirstarc54012341342vexdatafirstarc

5

5

4

3^^^adjvexnext55

1^

5

1

1

4

3^

2

2012345432fr遍歷序列：1432012345

32fr遍歷序列：1432012345

325fr遍歷序列：143251423512341342vexdatafirstarc55441012345

25fr遍歷序列/p>

5fr遍歷序列/p>

fr遍歷序列：1432512341342vexdatafirstarc

5

5

4

3^^^adjvexnext55

1^

5

1

1

4

3^

2

21423501234542BFSTraverse(){for()

//對于非連通圖需要有多個(gè)起始點(diǎn)

{EnQueue(v)//v是起點(diǎn)Visit(v)

while()//隊(duì)列不空

{DeQueue()while()//所有鄰接點(diǎn)入隊(duì)一個(gè)訪問一個(gè)

{EnQueue（w）Visit(w)}}

}}廣度優(yōu)先遍歷算法BFSTraverse()廣度優(yōu)先遍歷算法437.1圖的定義和基本術(shù)語7.2圖的存儲結(jié)構(gòu)7.3圖的遍歷

?7.4圖的生成樹7.5拓?fù)渑判?.6關(guān)鍵路徑7.7最短路徑第七章圖7.1圖的定義和基本術(shù)語第七章圖44什么是生成樹？一個(gè)圖可以有許多棵不同的生成樹一個(gè)有n個(gè)頂點(diǎn)的連通圖的生成樹有n-1條邊定義：所有頂點(diǎn)均由邊連接在一起，但不存在回路的子圖叫~V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8有兩種特殊的生成樹：深度優(yōu)先生成樹&廣度優(yōu)先生成樹一個(gè)連通圖的生成樹其實(shí)就是該連通圖的極小連通分量什么是生成樹？一個(gè)圖可以有許多棵不同的生成樹一個(gè)有n45V1V2V4V5V3V7V6V8例深度遍歷：V1V2V4V8V5V3V6V7V1V2V4V5V3V7V6V8深度優(yōu)先生成樹V1V2V4V5V3V7V6V8廣度優(yōu)先生成樹V1V2V4V5V3V7V6V8V7V1V2V4V5V3V6V8廣度遍歷：V1V2V3V4V5V6V7V8V1V2V4V5V3V7V6V8例深度遍歷：V1V2V446非連通圖ABLMCFDEGHKIJABLMCFJDEGHKI深度優(yōu)先生成森林生成森林：非連通圖每個(gè)連通分量的生成樹一起組成非連通圖的~需要從多個(gè)頂點(diǎn)出發(fā)，經(jīng)過多次搜索非連通圖ABLMCFDEGHKIJABLMCFJDEGHKI47對于連通網(wǎng)絡(luò)，其生成樹的各邊也是帶權(quán)值的，其各邊的權(quán)值之和稱作生成樹的權(quán)，權(quán)值最小的生成樹稱為最小生成樹14523753186421452375318642對于連通網(wǎng)絡(luò)，其生成樹的各邊也是帶權(quán)值的，其各邊的權(quán)值之和稱48問題分析1654327131791812752410

假設(shè)要在n個(gè)城市之間建立通訊聯(lián)絡(luò)網(wǎng)，則連通n個(gè)城市只需要修建n-1條線路該問題等價(jià)于：在e條帶權(quán)的邊中選取n-1條（不構(gòu)成回路），使“權(quán)值之和”為最小。即：構(gòu)造網(wǎng)的一棵最小生成樹如何在最節(jié)省經(jīng)費(fèi)的前提下建立這個(gè)通訊網(wǎng)？問題提出問題分析165432713179181275241049構(gòu)造最小生成樹方法方法一：普里姆(Prim)算法

MST性質(zhì)假設(shè)N=(V,{E})是一個(gè)連通網(wǎng)，U是頂點(diǎn)集V中的非空子集，若(u,v)是所有一端在U中而另一端在V-U中的所有邊中具有最小權(quán)值的邊，則必存在一棵最小生成樹包含邊(u,v)。構(gòu)造最小生成樹方法方法一：普里姆(Prim)算法MST50若圖中所有頂點(diǎn)均加入中，則在3操作中記錄的邊和相關(guān)的頂點(diǎn)構(gòu)成該網(wǎng)絡(luò)的最小生成樹以下的表述中，u表示U中的頂點(diǎn),v表示V-U中的頂點(diǎn)

1選任一個(gè)頂點(diǎn)加入U(xiǎn)2標(biāo)出一端在U中，而另一端在V-U中的邊和其權(quán)值，如果有多條邊同時(shí)從U中的不同的頂點(diǎn)出發(fā)到達(dá)v，則只選其中權(quán)值小的那條3在2中標(biāo)出的所有(u,v)中，選出權(quán)值最小的一條邊，記錄這條邊，并將頂點(diǎn)v加入U(xiǎn)中4若U<>V,根據(jù)新加入U(xiǎn)中的頂點(diǎn)，調(diào)整連接U和V中的邊（u，v），返回3若圖中所有頂點(diǎn)均加入中，則在3操作中記錄的邊和相關(guān)的頂點(diǎn)構(gòu)成51例1654326513566425131163141643142116432142516543214253***Prim算法***例1654326513566425131163141643152方法二：克魯斯卡爾(Kruskal)算法例165432651356642516543212345算法思想：設(shè)連通網(wǎng)N=(V,{E})，令最小生成樹初始狀態(tài)為只有n個(gè)頂點(diǎn)而無邊的非連通圖T=(V,{})，每個(gè)頂點(diǎn)自成一個(gè)連通分量。在E中選取代價(jià)最小的邊，若該邊依附的頂點(diǎn)落在T中不同的連通分量上，則將此邊加入到T中；否則，舍去此邊，選取下一條代價(jià)最小的邊。依此類推，直至T中所有頂點(diǎn)都在同一連通分量上為止方法二：克魯斯卡爾(Kruskal)算法例165432651531用頂點(diǎn)數(shù)組和邊數(shù)組存放頂點(diǎn)和邊信息2初始時(shí)，令每個(gè)頂點(diǎn)的集合互不相同；每個(gè)邊的flag為03選出權(quán)值最小且flag為0的邊4若該邊依附的兩個(gè)頂點(diǎn)的集合值不同，即非連通，則令該邊的flag=1,選中該邊；再令該邊依附的兩頂點(diǎn)的集合以及兩集合中所有頂點(diǎn)的集合相同。若該邊依附的兩個(gè)頂點(diǎn)的集合值相同，即連通，則令該邊的flag=2,即舍去該邊。5重復(fù)上述步驟，直到選出n-1條邊為止算法實(shí)現(xiàn)：1用頂點(diǎn)數(shù)組和邊數(shù)組存放頂點(diǎn)和邊信息算法實(shí)現(xiàn)：54例1654326513566425datajihe124536124536124536vexhweight112213233544vextflag6153550000000134256789334556666426000011111421112222216543212345例1654326513566425datajihe1245355普里姆算法適于稠密圖；克魯斯卡爾算法需對e條邊按權(quán)值進(jìn)行排序，則適于稀疏圖例.請分別用Prim算法和Kruskal算法構(gòu)造該網(wǎng)絡(luò)的最小生成樹。

普里姆算法適于稠密圖；例.請分別用Prim算法和Kruska567.1圖的定義和基本術(shù)語7.2圖的存儲結(jié)構(gòu)7.3圖的遍歷7.4圖的生成樹

?7.5拓?fù)渑判?.6關(guān)鍵路徑7.7最短路徑第七章圖7.1圖的定義和基本術(shù)語第七章圖57一個(gè)無環(huán)的有向圖稱作有向無環(huán)圖(DirectidAcyclineGragp)有向無環(huán)圖有向無環(huán)圖是描述一項(xiàng)工程或系統(tǒng)的進(jìn)行過程的有效工具一個(gè)無環(huán)的有向圖稱作有向無環(huán)圖(DirectidAcycl58課程代號課程名稱先修棵C1C2C3C4C5C6C7C8C9C10C11C12無C1C1,C2C1C3,C4C11C3.C5C3,C6無C9C9C1,C9,C10程序設(shè)計(jì)基礎(chǔ)離散數(shù)學(xué)數(shù)據(jù)結(jié)構(gòu)匯編語言語言的設(shè)計(jì)和分析計(jì)算機(jī)原理編譯原理操作系統(tǒng)高等數(shù)學(xué)線性代數(shù)普通物理數(shù)值分析C1C2C3C4C5C6C7C8C9C10C11C12學(xué)生應(yīng)按怎樣的順序?qū)W習(xí)這些課程，才能無矛盾、順利地完成學(xué)業(yè)？？？頂點(diǎn)——表示課程有向弧——若課程i是課程j的先決條件，則圖中有弧<i,j>學(xué)生選修課程問題課程代號課程名稱59AOV網(wǎng)

——

用頂點(diǎn)表示活動，用弧表示活動間優(yōu)先關(guān)系的有向圖稱為頂點(diǎn)表示活動的網(wǎng)(ActivityOnVertexnetwork)，簡稱AOV網(wǎng)。拓?fù)渑判?/p>

——

把AOV網(wǎng)絡(luò)中各頂點(diǎn)按照它們相互之間的優(yōu)先關(guān)系排列成一個(gè)線性序列的過程叫~檢測AOV網(wǎng)中是否存在環(huán)方法：對有向圖構(gòu)造其頂點(diǎn)的拓?fù)溆行蛐蛄校艟W(wǎng)中所有頂點(diǎn)都在它的拓?fù)溆行蛐蛄兄?，則該AOV網(wǎng)必定不存在環(huán)AOV網(wǎng)——用頂點(diǎn)表示活動，用弧表示活動間優(yōu)先關(guān)系的有向60在有向圖中選一個(gè)沒有前驅(qū)的頂點(diǎn)且輸出之從圖中刪除該頂點(diǎn)和所有以它為尾的弧拓?fù)渑判虻姆椒ㄖ貜?fù)上述兩步，直至全部頂點(diǎn)均已輸出；或者當(dāng)圖中不存在無前驅(qū)的頂點(diǎn)為止在有向圖中選一個(gè)沒有前驅(qū)的頂點(diǎn)且輸出之拓?fù)渑判虻姆椒ㄖ貜?fù)上述61C1C2C3C4C5C6C7C8C9C10C11C12拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12--C8或：C9--C10--C11--C6--C1--C12--C4--C2--C3--C5--C7--C8一個(gè)AOV網(wǎng)的拓?fù)湫蛄胁皇俏ㄒ坏腃1C2C3C4C5C6C7C8C9C10C11C12拓?fù)湫?2C1C2C3C4C5C6C7C8C9C10C11C12拓?fù)湫蛄校篊1（1）C1C2C3C4C5C6C7C8C9C10C11C12拓?fù)湫?3C2C3C4C5C6C7C8C9C10C11C12拓?fù)湫蛄校篊1--C2（2）C9C3C4C5C6C7C8C10C11C12拓?fù)湫蛄校篊1--C2--C3（3）C2C3C4C5C6C7C8C9C10C11C12拓?fù)湫蛄校?4C4C5C6C7C8C9C10C11C12拓?fù)湫蛄校篊1--C2--C3--C4（4）C5C6C7C8C9C10C11C12拓?fù)湫蛄校篊1--C2--C3--C4--C5（5）C4C5C6C7C8C9C10C11C12拓?fù)湫蛄校篊1--65C6C8C10C11C12拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7--C9--C10C6C7C8C9C10C11C12拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7（6）C11拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7--C9C6C8C9C10C12C6C8C11C12拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7--C9--C10--C11C6C8C10C11C12拓?fù)湫蛄校篊1--C2--C3--66C6C8C12拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7--C9--C10--C11--C6C8C12拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12C8拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12--C8C6C8C12拓?fù)湫蛄校篊1--C2--C3--C4--C567算法實(shí)現(xiàn)重復(fù)上述操作直至?？諡橹埂Ｈ魲？諘r(shí)輸出的頂點(diǎn)個(gè)數(shù)不是n，則有向圖有環(huán)；否則，拓?fù)渑判蛲戤呉脏徑颖碜鞔鎯Y(jié)構(gòu)把鄰接表中所有入度為0的頂點(diǎn)進(jìn)棧棧非空時(shí)，輸出棧頂元素Vj并退棧；在鄰接表中查找Vj的直接后繼Vk，把Vk的入度減1；若Vk的入度為0則進(jìn)棧算法實(shí)現(xiàn)重復(fù)上述操作直至?？諡橹埂Ｈ魲？諘r(shí)輸出的頂點(diǎn)個(gè)數(shù)不是6832104例1234560122infr

5

5

4

3^^^vexnext3^

2

5^

2

40123456^top16toptop32104例1234560122infr5543^^693210416top輸出序列：6top例1234560122infr

5

5

4

3^^^vexnext3^

2

5^

2

40123456^3210416top輸出序列：6top例1234560122700122infr

5

5

4

3^^^vexnext3^

2

5^

2

40123456^輸出序列：6321041topp0122infr5543^^^vexnext3^2710122infr

5

5

4

3^^^vexnext2^

2

5^

2

40123456^輸出序列：6321041topp0122infr5543^^^vexnext2^2720122infr

5

5

4

3^^^vexnext2^

2

5^

2

40123456^輸出序列：6321041topp0122infr5543^^^vexnext2^2730112infr

5

5

4

3^^^vexnext2^

2

5^

2

40123456^輸出序列：6321041topp0112infr5543^^^vexnext2^2740112infr

5

5

4

3^^^vexnext2^

2

5^

2

40123456^輸出序列：6321041topp=NULL0112infr5543^^^vexnext2^2750112infr

5

5

4

3^^^vexnext2^

2

5^

2

40123456^輸出序列：61321041toptop0112infr5543^^^vexnext2^2760112infr

5

5

4

3^^^vexnext2^

2

5^

2

40123456^輸出序列：6132104topp0112infr5543^^^vexnext2^2770102infr

5

5

4

3^^^vexnext2^

2

5^

2

40123456^輸出序列：6132104topp40102infr5543^^^vexnext2^2780102infr

5

5

4

3^^^vexnext2^

2

5^

2

40123456^輸出序列：6132104p4top0102infr5543^^^vexnext2^2790102infr

5

5

4

3^^^vexnext2^

2

5^

2

40123456^輸出序列：6132104p4top0102infr5543^^^vexnext2^2800002infr

5

5

4

3^^^vexnext2^

2

5^

2

40123456^輸出序列：6132104p4top30002infr5543^^^vexnext2^2810002infr

5

5

4

3^^^vexnext2^

2

5^

2

40123456^輸出序列：6132104p4top30002infr5543^^^vexnext2^2820002infr

5

5

4

3^^^vexnext2^

2

5^

2

40123456^輸出序列：6132104p4top30002infr5543^^^vexnext2^2830001infr

5

5

4

3^^^vexnext2^

2

5^

2

40123456^輸出序列：6132104p4top30001infr5543^^^vexnext2^2840001infr

5

5

4

3^^^vexnext2^

2

5^

2

40123456^輸出序列：6132104p=NULL4top30001infr5543^^^vexnext2^2850001infr

5

5

4

3^^^vexnext2^

2

5^

2

40123456^輸出序列：613321044top30001infr5543^^^vexnext2^2860001infr

5

5

4

3^^^vexnext2^

2

5^

2

40123456^輸出序列：613321044topp0001infr5543^^^vexnext2^2870001infr

5

5

4

3^^^vexnext1^

2

5^

2

40123456^輸出序列：613321044topp0001infr5543^^^vexnext1^2880001infr

5

5

4

3^^^vexnext1^

2

5^

2

40123456^輸出序列：613321044topp0001infr5543^^^vexnext1^2890000infr

5

5

4

3^^^vexnext1^

2

5^

2

40123456^輸出序列：613321044topp20000infr5543^^^vexnext1^2900000infr

5

5

4

3^^^vexnext1^

2

5^

2

40123456^輸出序列：613321044topp20000infr5543^^^vexnext1^2910000infr

5

5

4

3^^^vexnext1^

2

5^

2

40123456^輸出序列：613321044top2p=NULL0000infr5543^^^vexnext1^2920000infr

5

5

4

3^^^vexnext1^

2

5^

2

40123456^輸出序列：6132321044top2p=NULL0000infr5543^^^vexnext1^2930000infr

5

5

4

3^^^vexnext1^

2

5^

2

40123456^輸出序列：6132321044topp=NULL0000infr5543^^^vexnext1^2940000infr

5

5

4

3^^^vexnext1^

2

5^

2

40123456^輸出序列：61324321044top0000infr5543^^^vexnext1^2950000infr

5

5

4

3^^^vexnext1^

2

5^

2

40123456^輸出序列：6132432104topp0000infr5543^^^vexnext1^2960000infr

5

5

4

3^^^vexnext0^

2

5^

2

40123456^輸出序列：6132432104topp50000infr5543^^^vexnext0^2970000infr

5

5

4

3^^^vexnext0^

2

5^

2

40123456^輸出序列：6132432104topp=NULL50000infr5543^^^vexnext0^2980000infr

5

5

4

3^^^vexnext0^

2

5^

2

40123456^輸出序列：61324532104top50000infr5543^^^vexnext0^2990000infr

5

5

4

3^^^vexnext0^

2

5^

2

40123456^輸出序列：61324532104topp=NULL拓?fù)渑判蛩惴?000infr5543^^^vexnext0^2100例.寫出下圖所有可能的拓?fù)湫蛄衎cdegfa例.寫出下圖所有可能的拓?fù)湫蛄衎cdegfa1017.1圖的定義和基本術(shù)語7.2圖的存儲結(jié)構(gòu)7.3圖的遍歷7.4圖的生成樹7.5拓?fù)渑判?/p>

?7.6關(guān)鍵路徑7.7最短路徑第七章圖7.1圖的定義和基本術(shù)語第七章圖102例

設(shè)一個(gè)工程有11項(xiàng)活動，9個(gè)事件

事件V1——表示整個(gè)工程開始

事件V9——表示整個(gè)工程結(jié)束987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4AOE網(wǎng)（ActivityOnEdge）邊表示活動用頂點(diǎn)表示事件，弧表示活動，權(quán)表示活動持續(xù)的時(shí)間；網(wǎng)中只有：唯一一個(gè)入度為0的點(diǎn)源點(diǎn)唯一一個(gè)出度為0的點(diǎn)匯點(diǎn)完成整項(xiàng)工程至少需要多少時(shí)間？哪些活動是影響工程進(jìn)度的關(guān)鍵？例設(shè)一個(gè)工程有11項(xiàng)活動，9個(gè)事件987645321a1103Ve(j)——表示事件Vj的最早發(fā)生時(shí)間Vl(j)——表示事件Vj的最遲發(fā)生時(shí)間ee(i)——表示活動ai的最早開始時(shí)間el(i)——表示活動ai的最遲開始時(shí)間el(i)-ee(i)——表示完成活動ai的時(shí)間余量關(guān)鍵活動就是時(shí)間余量el(i)-ee(i)＝0的活動關(guān)鍵路徑

——

路徑長度最長的路徑叫~關(guān)鍵活動

——

關(guān)鍵路徑上的活動叫~987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4Ve(j)——表示事件Vj的最早發(fā)生時(shí)間關(guān)鍵路徑——路徑104如何找ee(i)=el(i)的關(guān)鍵活動？設(shè)活動ai用弧<j,k>表示，其持續(xù)時(shí)間記為：dut(<j,k>)則有：（1）ee(i)=Ve(j)（2）el(i)=Vl(k)-dut(<j,k>)jkai如何求Ve(j)和Vl(j)？(1)從Ve(1)=0開始向前遞推(2)從Vl(n)=Ve(n)開始向后遞推如何找ee(i)=el(i)的關(guān)鍵活動？設(shè)活動ai用弧<j,105987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4V1V2V3V4V5V6V7V8V9頂點(diǎn)VeVl0645771614180668710161418a1a2a3a4a5a6a7a8a9a10a11活動eeelel-ee00002266046258377077071031616014140033求關(guān)鍵路徑步驟求Ve(i)->求Vl(j)->求ee(i),el(i),計(jì)算el(i)-ee(i)987645321a2=4a3=5a5=1a6=2a9=4a106算法描述輸入頂點(diǎn)和弧信息，建立其鄰接表計(jì)算每個(gè)頂點(diǎn)的入度對其進(jìn)行拓?fù)渑判蚺判蜻^程中求頂點(diǎn)的Ve[i]將得到的拓?fù)湫蛄羞M(jìn)棧按逆拓?fù)湫蛄星箜旤c(diǎn)的Vl[i]計(jì)算每條弧的ee[i]和el[i],找出ee[i]=el[i]的關(guān)鍵活動987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4按拓?fù)渑判虻捻樞蛴?jì)算Ve按逆拓?fù)渑判虻捻樞蛴?jì)算Vl因此：對以拓?fù)渑判蛩惴榛A(chǔ)修改關(guān)鍵路徑算法算法描述987645321a2=4a3=5a5=1a6=2a107987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4inlink

vexnextvexdata

info123456789123456789011121122

26

34

45^

79^

51^

62^

51^

87^

84^

910^

94^987645321a2=4a3=5a5=1a6=2a9=4a1087.1圖的定義和基本術(shù)語7.2圖的存儲結(jié)構(gòu)7.3圖的遍歷7.4圖的生成樹7.5拓?fù)渑判?.6關(guān)鍵路徑

?7.7最短路徑第七章圖7.1圖的定義和基本術(shù)語第七章圖109問題提出用帶權(quán)的有向圖表示一個(gè)交通運(yùn)輸網(wǎng)，圖中：頂點(diǎn)——表示城市邊——表示城市間的交通聯(lián)系權(quán)——表示此線路的長度或沿此線路運(yùn)輸所花的時(shí)間或費(fèi)用等問題：從某頂點(diǎn)出發(fā)，沿圖的邊到達(dá)另一頂點(diǎn)所經(jīng)過的路徑中，各邊上權(quán)值之和最小的一條路徑——最短路徑從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑51643208562301371732913長度最短路徑<V0,V1><V0,V2><V0,V2,V3><V0,V2,V3,V4><V0,V2,V3,V4,V5><V0,V1,V6>813192120問題提出用帶權(quán)的有向圖表示一個(gè)交通運(yùn)輸網(wǎng)，圖中：從某個(gè)源點(diǎn)到110迪杰斯特拉(Dijkstra)算法思想按路徑長度遞增次序產(chǎn)生最短路徑算法：把V分成兩組：（1）S：已求出最短路徑的頂點(diǎn)的集合（2）V-S=T：尚未確定最短路徑的頂點(diǎn)集合將T中頂點(diǎn)按最短路徑遞增的次序加入到S中，保證：（1）從源點(diǎn)V0到S中各頂點(diǎn)的最短路徑長度都不大于從V0到T中任何頂點(diǎn)的最短路徑長度（2）每個(gè)頂點(diǎn)對應(yīng)一個(gè)距離值

S中頂點(diǎn)：從V0到此頂點(diǎn)的最短路徑長度

T中頂點(diǎn)：從V0到此頂點(diǎn)的只包括S中頂點(diǎn)作中間頂點(diǎn)的最短路徑長度依據(jù)：可以證明V0到T中頂點(diǎn)Vk的最短路徑，或是從V0到Vk的直接路徑的權(quán)值,或是從V0經(jīng)S中頂點(diǎn)到Vk的路徑權(quán)值之和（反證法可證）迪杰斯特拉(Dijks