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

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

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

V

且E'

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

V1V2V3V4V5V6V7V1V2V4V5V3V6V7連通分量2連通分量是對無向圖的一種劃分。7.1知識學習——圖的基本術語7.1知識學習——圖的基本術語圖的基本術語強連通圖：在有向圖中，對圖中任意一對頂點vi和vj

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

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

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

行元素掃描一遍，若arcs[i][j]為1，則頂點j

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

arcs[i][j]＝

wij

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

∞

∞

∞087∞∞0arcs=7.1知識學習——圖的存儲結構7.1知識學習——圖的存儲結構無向網(wǎng)的鄰接矩陣構造voidCreateMGraph(MGraph&G){

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

cout<<"請輸入圖的頂點數(shù)：";

cin>>G.vexnum;

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

cin>>G.arcnum;

cout<<"請輸入頂點的信息："; 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<<"請輸入邊的信息：";

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

{

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

V3V401232.鄰接表7.1知識學習——圖的存儲結構datafirstedge頂點表結點data：數(shù)據(jù)域，存放頂點信息。

firstedge：指針域，指向邊表中第一個結點。

typedefstruct{

VertexTypedata;

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

V3V401237.1知識學習——圖的存儲結構邊表結點adjvex：鄰接點域，邊的終點在頂點表中的下標next：指針域，指向邊表中的下一個結點typedefstructEdgeNode{

intadjvex;

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

V3V40123V1V3V4V2無向圖的鄰接表邊表中的結點表示什么？每個結點對應圖中的一條邊，鄰接表的空間復雜度為O(n+e)。103∧23∧1∧01∧V1V2

V3V40123V1V3V4V2如何求頂點i的度？頂點i的邊表中結點的個數(shù)。無向圖的鄰接表103∧23∧1∧01∧V1V2

V3V40123如何判斷頂點i和頂點j之間是否存在邊?測試頂點i的邊表中是否存在終點為j的結點。V1V3V4V2無向圖的鄰接表103∧23∧1∧01∧V1V2

V3V40123V1V2V3V412∧3∧0∧V1V2

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

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

V3V40123∧V1V2V3V4278521V1V2

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

intadjvex;//鄰接點存儲位置

EdgeNode*next;//指向下一個鄰接點}*EdgeList;typedefstruct//頂點表的元素類型{

VertexTypedata;//頂點信息

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

VexNodeadjlist[MAX];//頂點表

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

GraphTypekind;//圖的類型}ALGraph;7.1知識學習——圖的存儲結構鄰接表的構建1.確定圖的頂點個數(shù)和邊的個數(shù)；2.

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

3.1輸入邊依附的兩個頂點的序號i,j；

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

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

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

從i出發(fā)進行深度優(yōu)先遍歷；⑶重復上述兩步，直至圖中所有和v有路徑相通的頂點都被訪問到。cout<<G.vexs[v];//訪問第v個頂點visited[v]=true;//設置訪問標志為1（已訪問）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知識學習——圖的遍歷2.廣度優(yōu)先遍歷基本思想：⑴訪問頂點v；⑵依次訪問v的各個未被訪問的鄰接點w1,w2,…,wt；⑶分別從w1，w2，…，wt出發(fā)依次訪問它們未被訪問的鄰接點，并使“先被訪問頂點的鄰接點”先于“后被訪問頂點的鄰接點”被訪問。直至圖中所有與頂點v有路徑相通的頂點都被訪問到。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)先遍歷圖的遍歷算法的應用無向圖的連通性的判斷要想判定一個無向圖是否為連通圖，或有幾個連通分量，通過對無向圖遍歷即可得到結果。連通圖：僅需從圖中任一頂點出發(fā)，進行深度優(yōu)先搜索（或廣度優(yōu)先搜索），便可訪問到圖中所有頂點。非連通圖：需從多個頂點出發(fā)進行搜索，而每一次從一個新的起始點出發(fā)進行搜索過程中得到的頂點訪問序列恰為其各個連通分量中的頂點集。7.1知識學習——最小生成樹有向圖的連通性的判斷⑴從某頂點出發(fā)進行深度優(yōu)先遍歷，并按其所有鄰接點都訪問（即出棧）的順序將頂點排列起來。⑵從最后完成訪問的頂點出發(fā)，沿著以該頂點為頭的弧作逆向的深度優(yōu)先遍歷。若不能訪問到所有頂點，則從余下的頂點中最后訪問的那個頂點出發(fā)，繼續(xù)作逆向的深度優(yōu)先遍歷，直至有向圖中所有頂點都被訪問到為止。⑶每一次逆向深度優(yōu)先遍歷所訪問到的頂點集便是該有向圖的一個強連通分量的頂點集。（a）深度優(yōu)先生成樹（b）廣度優(yōu)先生成樹V1V3V2V4V5V6V7V8V1V3V2V4V5V6V7V87.1知識學習——最小生成樹7.1知識學習——最小生成樹由深度優(yōu)先遍歷得到的為深度優(yōu)先生成樹，由廣度優(yōu)先遍歷得到的為廣度優(yōu)先生成樹。一個連通圖的生成樹可能不唯一，由不同的遍歷次序、從不同頂點出發(fā)進行遍歷都會得到不同的生成樹。對于非連通圖，通過圖的遍歷，將得到的是生成森林。7.1知識學習——最小生成樹生成樹的代價：設G=(V，E)是一個無向連通網(wǎng)，生成樹上各邊的權值之和稱為該生成樹的代價。最小生成樹：在圖G所有生成樹中，代價最小的生成樹稱為最小生成樹。最小生成樹的概念可以應用到許多實際問題中。例：在n個城市之間建造通信網(wǎng)絡，至少要架設n-1條通信線路，而每兩個城市之間架設通信線路的造價是不一樣的，那么如何設計才能使得總造價最?。?.1知識學習——最小生成樹

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算法的關鍵：如何找到連接U和V-U的最短邊?？梢杂孟率龇椒嬙旌蜻x最短邊集：對應V-U中的每個頂點，保留從該頂點到U中的各頂點的最短邊。Prim算法Prim算法引入一個輔助數(shù)組miniedges[]，用于存放集合V

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

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

3.1選取出權值最小的候選交叉邊，取對應的頂點序號k；3.2將頂點k加入集合U中；

3.3調整數(shù)組miniedges[]；Prim算法Kruskal算法Kruskal算法基本思想：設無向連通網(wǎng)為G＝(V,E)，令G的最小生成樹為T＝(U,TE)，其初態(tài)為U＝V，TE＝{}，然后，按照邊的權值由小到大的順序，考察G的邊集E中的各條邊。若被考察的邊的兩個頂點屬于T的兩個不同的連通分量，則將此邊作為最小生成樹的邊加入到T中，同時把兩個連通分量連接為一個連通分量；若被考察邊的兩個頂點屬于同一個連通分量，則舍去此邊，以免造成回路。如此下去，當T中的連通分量個數(shù)為1時，此連通分量便為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中的連通分量個數(shù)為12.1在E中尋找最短邊(u，v);2.2如果頂點u、v位于T的兩個不同連通分量，則

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

2.2.2將這兩個連通分量合為一個；

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

問題描述：給定帶權有向圖G＝(V,E)和源點v∈V，求從v到G中其余各頂點的最短路徑。迪杰斯特拉（Dijkstra）提出了一個按路徑長度遞增的次序產(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圖的存儲結構：帶權的鄰接矩陣存儲結構數(shù)組dist[n]：每個分量dist[i]表示當前所找到的從始點v到終點vi的最短路徑的長度。初態(tài)為：若從v到vi有弧，則dist[i]為弧上權值；否則置dist[i]為∞。數(shù)組path[n]：保存從源點到各頂點的。path[i]中保存了從源點到終點vi的最短路徑上該頂點的前驅頂點的序號。數(shù)組s[n]：記錄已求出最短路徑的頂點集合S，s[i]為true表示頂點vi已在集合S中。Dijkstra算法1.初始化數(shù)組dist、path和s；2.while(s中的元素個數(shù)<n)2.1在dist[n]中求最小值，其下標為k；

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

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

Dijkstra算法——偽代碼每一對頂點之間的最短路徑問題描述：給定帶權有向圖G＝(V,E)，對任意頂點vi,vj∈V（i≠j），求頂點vi到頂點vj的最短路徑。方法1：每次以一個頂點為源點，調用Dijkstra算法n次。顯然，時間復雜度為O(n3)。方法2：弗洛伊德提出的求每一對頂點之間的最短路徑算法——Floyd算法，其時間復雜度也是O(n3)，但形式上要簡單些。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算法圖的存儲結構：帶權的鄰接矩陣存儲結構數(shù)組D[n][n]：存放在迭代過程中求得的最短路徑長度。數(shù)組path[n][n]：path[i][j]中存放的是從頂點vi到頂點vj中間頂點序號不大于k的最短路徑上的頂點vi的后繼頂點的序號。

設計數(shù)據(jù)結構導學問題1的實現(xiàn)：

導學問題1就是構造連通網(wǎng)的最小生成樹的問題。導學問題2的實現(xiàn)：

導學問題2就是求兩個頂點間最短路徑的問題。7.2知識應用

7.3知識拓展——AOV網(wǎng)與拓撲排序什么AOV網(wǎng)？AOV網(wǎng)：在一個表示工程的有向圖中，用頂點表示活動，用弧表示活動之間的優(yōu)先關系，稱這樣的有向圖為頂點表示活動的網(wǎng)，簡稱AOV網(wǎng)。AOV網(wǎng)中出現(xiàn)回路意味著什么？7.3知識拓展——AOV網(wǎng)與拓撲排序AOV網(wǎng)特點：1.AOV網(wǎng)中的弧表示活動之間存在的某種制約關系。2.AOV網(wǎng)中不能出現(xiàn)回路。編號課程名稱先修課C1高等數(shù)學無C2計算機導論無C3離散數(shù)學C1C4程序設計C1,C2C5數(shù)據(jù)結構C3，C4C6計算機原理C2，C4C7數(shù)據(jù)庫原理C4，C5，C6C1C2C3C4C6C5C7AOV網(wǎng)拓撲排序拓撲序列：設G=(V，E)是一個具有n個頂點的有向圖，V中的頂點序列v1,v2,…,vn稱為一個拓撲序列，當且僅當滿足下列條件：若從頂點vi到vj有一條路徑，則在頂點序列中頂點vi必在頂點vj之前。拓撲排序：對一個有向圖構造拓撲序列的過程稱為拓撲排序。拓撲排序基本思想：⑴從AOV網(wǎng)中選擇一個沒有前驅的頂點并且輸出；⑵從AOV網(wǎng)中刪去該頂點，并且刪去所有以該頂點為尾的?。虎侵貜蜕鲜鰞刹?，直到全部頂點都被輸出，或AOV網(wǎng)中不存在沒有前驅的頂點。C1C2C3C4C6C5C7拓撲序列：C1,拓撲排序C2C3C4C6C5C7拓撲序列：C1,C2,拓撲排序C3C4C6C5C7拓撲序列：C1,C2,C3,拓撲排序C4C6C5C7拓撲序列：C1,C2,C3,C4,拓撲排序C6C5C7拓撲序列：C1,C2,C3,C4,C5,拓撲排序C6C7拓撲序列：C1,C2,C3,C4,C5,C6,拓撲排序C7拓撲序列：C1,C2,C3,C4,C5,C6,C7,拓撲排序設計數(shù)據(jù)結構1.圖的存儲結構：宜采用鄰接表存儲。2.為便于算法執(zhí)行過程中考察每個頂點的入度，即查找沒有前驅的頂點，可引入一個存放各頂點入度的數(shù)組indegree[]。3.為了避免每一步選入度為0的頂點時重復掃描數(shù)組indegree，可設置一個隊列（或棧）來存儲所有入度為0的頂點。在進行拓撲排序之前，只要對頂點表掃描一遍，將所有入度為0的頂點都排入隊列中，一旦排序過程中出現(xiàn)新的入度為0的頂點，也同樣將其排入隊列中。

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

indgreevertexfirstedgeA

B

C

D

E

F

G∧

2

4

5

4∧

6∧ABGDEF拓撲排序C

3

4

6∧

5∧

4∧

6∧

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

indgreevertexfirstedge0A0B1C2D4E2F

3

G∧

2

4

5

4∧

6∧ABGDEF拓撲排序C

3

4

6∧

5∧

4∧

6∧

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

indgreevertexfirstedge0A0B1C2D4E2F

3

G∧

2

4

5

4∧

6∧ABGDEF拓撲排序C

3

4

6∧

5∧

4∧

6∧

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

indgreevertexfirstedge0A0B1C1D3E2F

2

G∧

2

4

5

4∧

6∧BGDEF拓撲排序C

3

4

6∧

5∧

4∧

6∧

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

indgreevertexfirstedge0A0B0C1D2E1F

2

G∧

2

4

5

4∧

6∧GDEF拓撲排序C

3

4

6∧

5∧

4∧

6∧

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

indgreevertexfirstedge0A0B0C0D1E1F

2

G∧

2

4

5

4∧

6∧GDEF拓撲排序

3

4

6∧

5∧

4∧

6∧

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

indgreevertexfirstedge0A0B0C0D0E1F

2

G∧

2

4

5

4∧

6∧GEF拓撲排序

3

4

6∧

5∧

4∧

6∧

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

indgreevertexfirstedge0A0B0C0D0E0F

1

G∧

2

4

5

4∧

6∧GF拓撲排序

3

4

6∧

5∧

4∧

6∧

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

indgreevertexfirstedge0A0B0C0D0E0F

0

G∧

2

4

5

4∧

6∧G拓撲排序

3

4

6∧

5∧

4∧

6∧

3GABCDEF1.隊列s初始化；累加器c初始化；2.掃描頂點表，將沒有前驅的頂點入隊；3.當隊列s非空時:

3.1頂點i出隊，并輸出；累加器加1；

3.2將頂點i的各個鄰接點的入度減1；

3.3將新的入度為0的頂點入隊；4.if(c<圖的頂點個數(shù))輸出“有回路”信息；拓撲排序算法——偽代碼事件事件含義

v1開工

v2

活動a1完成，活動a4可以開始

v3活動a2完成，活動a5可以開始

…………v9活動a10

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