數據結構與算法：第七章 圖

17.1基本術語7.2存儲結構7.3圖的遍歷7.4圖的其他運算7.5圖的應用第7章圖2數據結構課程的內容多對多（m:n)重點1.圖的兩種物理存儲表示；2.圖的兩種遍歷的思想及算法；3.圖的各種應用。31.最小生成樹算法；2.最短路徑算法；3.拓撲排序算法；4.關鍵路徑4難點57.1圖的基本術語

其中：V

是G的頂點集合，是有窮非空集；

E是G的邊集合，是有窮集。問：當E(G)為空時，圖G存在否？答：還存在！但此時圖G只有頂點而沒有邊。V=vertexE=edge圖：記為G＝(V,E)v1v2v3v5v4v4v1v2v3v467.1圖的基本術語有向圖：無向圖：完全圖：圖G中的每條邊都是有方向的；圖G中的每條邊都是無方向的；圖G任意兩個頂點都有一條邊相連接；若n個頂點的無向圖有n(n-1)/2條邊,稱為無向完全圖若n個頂點的有向圖有n(n-1)條邊,稱為有向完全圖7例：判斷下列4種圖形各屬什么類型？無向圖無向圖(樹)有向圖有向完全圖n(n-1)/2條邊n(n-1)條邊G1的頂點集合為V(G1)={0,1,2,3}邊集合為E(G1)={(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)}8證明證明：若是完全有向圖，則n個頂點中的每個頂點都有一條弧指向其它n-1個頂點,因此總邊數=n(n-1)①完全有向圖有n(n-1)條邊。12349證明證明：從①可以直接推論出無向完全圖的邊數——因為無方向，兩弧合并為一邊，所以邊數減半，總邊數為n(n-1)/2。②完全無向圖有n(n-1)/2條邊。123410

稀疏圖：邊較少的圖。通常邊數遠少于nlog2n。稠密圖：邊很多的圖。無向圖中，邊數接近n(n-1)/2

有向圖中，邊數接近n(n-1)圖的基本術語

11設無向圖的頂點個數為n,則該圖最多有()條邊。n-1An(n-1)Bn(n-1)/2CnD提交單選題1分12

設有兩個圖G＝(V,E)和G’＝(V’,E’)。若V’V且E’E,則稱圖G’是圖G的子圖。子圖：圖的基本術語

13帶權圖：即邊上帶權的圖。其中權是指每條邊可以標上具有某種含義的數值（即與邊相關的數）。→帶權圖網絡：圖的基本術語

14連通圖：在無向圖中,若從頂點v1到頂點v2有路徑,則稱頂點v1與v2是連通的。如果圖中任意一對頂點都是連通的,則稱此圖是連通圖。非連通圖的極大連通子圖叫做連通分量。圖的基本術語DEABCFJLMGHIK15圖的基本術語(續(xù))在有向圖中,若對于每一對頂點vi和vj,都存在一條從vi到vj和從vj到vi的路徑,則稱此圖是強連通圖。強連通圖（針對有向圖）：非強連通圖的極大強連通子圖叫做強連通分量。v1v2v3v416要連通具有n個頂點的有向圖,至少需要()條邊。n-1AnBn+1C2nD提交單選題1分17有兩類圖形不在本章討論之列18生成樹：是一個極小連通子圖，它含有圖中全部n個頂點，但只有n-1條邊。針對的是無向帶權圖。圖的基本術語(續(xù))v1v2v3v4如果在生成樹上添加1條邊，必定構成一個環(huán)。若圖中有n個頂點，卻少于n-1條邊，必為非連通圖。19若干棵生成樹的集合，含全部頂點，但構成這些樹的邊或弧是最少的。圖的基本術語(續(xù))生成森林：一個有向圖及其生成森林20鄰接點：有向邊(u,v)稱為弧，邊的始點u叫弧尾，終點v叫弧頭。若(u,v)是E(G)中的一條邊，則稱u與v互為鄰接頂點。弧頭和弧尾：uvU的入度=?U的出度=?圖的基本術語(續(xù))21頂點v的入度是以v為終點的有向邊的條數,記作ID(v);頂點v的出度是以v為始點的有向邊的條數,記作OD(v)。入度:出度：uv度：頂點v的度是與它相關聯的邊的條數。記作TD(v)。在有向圖中,頂點的度等于該頂點的入度與出度之和。U的入度=?U的出度=?圖的基本術語(續(xù))22有向樹是一種特殊的圖答：是樹！而且是一棵有向樹！問：當有向圖中僅1個頂點的入度為0,其余頂點的入度均為1，此時是何形狀？23路徑：在圖G＝(V,E)中,若從頂點vi出發(fā),沿一些邊經過一些頂點vp1,vp2,…,vpm，到達頂點vj。則稱頂點序列(vi

vp1vp2...vpm

vj)為從頂點vi到頂點vj的路徑。它經過的邊(vi,vp1)、(vp1,vp2)、...、(vpm,vj)應當是屬于E的邊。路徑長度非帶權圖的路徑長度是指此路徑上邊的條數；帶權圖的路徑長度是指路徑上各邊的權之和。圖的術語（續(xù)）24簡單路徑：路徑上各頂點v1,v2,...,vm

均不互相重復?；芈罚喝袈窂缴系谝粋€頂點v1

與最后一個頂點vm

重合，則稱這樣的路徑為回路或環(huán)。圖的術語（續(xù)）25ADTGraph{數據對象V：數據關系R：基本操作P：}ADTGraph圖的抽象數據類型V是具有相同特性的數據元素的集合，稱為頂點集。R={VR}；VR={<v,w>|v,w∈V且P(v,w),<v,w>表示從v到w的弧，謂詞P(v,w)定義了弧<v,w>的意義或信息}CreatGraph(&G,V,VR);InsertVex(&G,v);

…………（參見教材P156-157）267.2圖的存儲結構圖的特點：順序存儲結構：難！（多個頂點，無序可言，無法僅以頂點坐標表達相互關系）但可用數組描述元素間關系（邊）。非線性結構（m:n）鄰接矩陣277.2圖的存儲結構一、順序存儲法1、鄰接矩陣(數組)表示法各種表示法成立的原則：存入電腦后能惟一復原二、鏈式存儲結構鄰接表(鏈式)表示法十字鏈表表示法鄰接多重表表示法28①建立一個頂點表和一個鄰接矩陣。1.鄰接矩陣（數組）表示法記錄各個頂點信息表示各個頂點之間關系②設圖A=(V,E)有n個頂點，則圖的鄰接矩陣是一個二維數組A.Edge[n][n]，定義為：29例1：鄰接矩陣：A.Edge=（v1v2

v3v4v5）v1v2v3v4v5分析1：無向圖的鄰接矩陣是對稱的；分析2：頂點i

的度＝第i

行(列)中1的個數；特別：完全圖的鄰接矩陣中，對角元素為0，其余全1。頂點表：無向圖的鄰接矩陣如何表示？v1v2v3v5v4v4A00

0

0000

0000

0000000000000001

0

1010

1010

101110101011101.鄰接矩陣（數組）表示法30例2：有向圖的鄰接矩陣如何表示？v1v2v3v4A鄰接矩陣：A.Edge=(v1v2

v3v4)v1v2v3v400

0

000

000

0000000注：在有向圖的鄰接矩陣中，第i行含義：以結點vi為尾的弧(即出度邊）；第i列含義：以結點vi為頭的弧(即入度邊）。頂點表：01

1

000

000

0

01

1

00001

1

000

000

001100031例2：有向圖的鄰接矩陣如何表示？分析1：有向圖的鄰接矩陣可能是不對稱的。分析2：頂點vi的出度=第i行非零元素之和，OD(vi)=A.Edge[i][j]

頂點vi的入度=第i列非零元素之和。ID(vi)=A.Edge[j][i]

頂點的度=第i行非零元素之和+第i列非零元素之和,

即：TD(vi)=OD(vi)+ID(vi)v1v2v3v4A鄰接矩陣：A.Edge=(v1v2

v3v4)v1v2v3v400

0

000

000

0000000頂點表：01

1

000

000

0

01

1

00001

1

000

000

001100032例3：有權圖（即網絡）的鄰接矩陣如何表示？定義：A.Edge[i][j]=Wij<vi,vj>或（vi,vj）∈VR∞無邊（弧）v1v2v3v4Nv5v65489755613以有向網為例：鄰接矩陣：∞

∞

∞∞

∞

∞∞

∞

∞∞

∞

∞∞

∞

∞∞

∞

∞∞

∞

∞∞

∞

∞∞

∞

∞∞

∞

∞∞

∞

∞∞

∞

∞N.Edge=(v1v2

v3v4v5v6)頂點表：

5

7

4

8

9

5

6

5

3

1

∞

5

∞

7

∞

∞∞

∞

4

∞

∞

∞

8

∞

∞

∞∞

9∞

∞

5∞

∞

6∞

∞

∞

5

∞

∞

3

∞

∞∞

1

∞v1v2v3v4v5v633鄰接矩陣法優(yōu)點：鄰接矩陣法缺點：對稀疏圖而言尤其浪費空間。容易實現圖的操作，如：求某頂點的度、判斷頂點之間是否有邊（?。?、找頂點的鄰接點等等。n個頂點需要n*n個單元存儲邊(弧);空間效率為O(n2)。鄰接矩陣法優(yōu)缺點34設圖的鄰接矩陣A如下所示。各頂點的度依次是()1,2,1,2A2,2,1,1B3,4,2,3C4,4,2,2D提交單選題1分35圖的鄰接矩陣在機內如何表示？（重點）36StatusCreateUDN(Mgraph&G){//無向網的構造，用鄰接矩陣表示scanf(&G.vexnum,&G.arcnum,&IncInfo);//輸入總頂點數n、總弧數e和信息for(i=0;i<G.vexnum,;++i)scanf(&G.vexs[i]);//輸入n個頂點值，存入一維向量例：用鄰接矩陣生成無向網的算法（參見教材P162）for(i=0;i<G.vexnum;++i)//對鄰接矩陣n*n個單元初始化，adj=∞,info=NULLfor(j=0;j<G.vexnum;++j)G.arcs[i][j]={INFINITY,NULL};37對于n個頂點e條弧的網，建網時間效率=O(n+n2+e*n)for(k=0;k<G.arcnum;++k){//給鄰接矩陣有關單元賦初值(循環(huán)次數＝弧數escanf(&v1,&v2,&w);//輸入弧的兩頂點以及對應權值

i=LocateVex(G,v1);j=LocateVex(G,v2);//找到兩頂點在矩陣中的位置(n次)G.arcs[i][j].adj=w;//輸入對應權值

If(IncInfo)Input(*G.arcs[i][j].info);//如果弧有信息則填入

G.arcs[i][j]=G.arcs[j][i]；//無向網是對稱矩陣

}returnOK;}

//CreateUDN例：用鄰接矩陣生成無向網的算法（參見教材P162）382.鄰接表（鏈式）表示法①對每個頂點vi建立一個單鏈表，把與vi有關聯的邊的信息（即度或出度邊）鏈接起來，表中每個結點都設為3個域:②每個單鏈表還應當附設一個頭結點（設為2個域），存vi信息；adjvexinfonextarcdatafirstarc表結點頭結點鄰接點域，表示vi

鄰接點的位置鏈域，指向下一個邊或弧的結點數據域，與邊有關信息（如權值）數據域，存儲頂點vi

信息鏈域，指向單鏈表的第一個結點③每個單鏈表的頭結點另外用順序存儲結構存儲。39例1：無向圖的鄰接表如何表示？v1v2v3v5v4v4鄰接表01234^1334^142^0請注意：鄰接表不唯一！因各個邊結點的鏈入順序是任意的。v1v2v3v4v523^142^0v1鄰接點v4的位置此無權圖未開第3分量40例2：有向圖的鄰接表如何表示？v1v2v3v4V4V3^V2V12^3^0^1鄰接表(出邊)V4V3V2V1^3^0^2^0逆鄰接表(入邊)41例3：已知某網的鄰接（出邊）表，請畫出該網絡。8064125當鄰接表的存儲結構形成后，圖便唯一確定！42分析1:對于n個頂點e條邊的無向圖，鄰接表中除了n個頭結點外，只有2e個表結點,空間效率為O(n+2e)。若是稀疏圖(e<<n2)，則比鄰接矩陣表示法O(n2)省空間。鄰接表存儲法的特點—它其實是對鄰接矩陣法在存儲空間的一種改進怎樣計算無向圖頂點的度？TD(Vi)=單鏈表中鏈接的結點個數43分析2：在有向圖中，鄰接表中除了n個頭結點外，只有e個表結點，空間效率為O(n+e)。若是稀疏圖，則比鄰接矩陣表示法合適。鄰接表存儲法的特點：44怎樣計算有向圖頂點的出度？

OD(Vi)＝單鏈出邊表中鏈接的結點數怎樣計算有向圖頂點的入度？

ID(Vi)＝鄰接點為Vi的弧個數怎樣計算有向圖頂點Vi的度：

TD(Vi)=OD(Vi)+ID(Vi)鄰接表存儲法的特點：45鄰接表的缺點：鄰接表的優(yōu)點：空間效率高；容易尋找頂點的鄰接點；判斷兩頂點間是否有邊或弧，需搜索兩結點對應的單鏈表，沒有鄰接矩陣方便。鄰接表存儲法的特點46討論：鄰接表與鄰接矩陣有什么異同之處？1.聯系：鄰接表中每個鏈表對應于鄰接矩陣中的一行，鏈表中結點個數等于鄰接矩陣一行中非零元素的個數。47討論：鄰接表與鄰接矩陣有什么異同之處？2.區(qū)別①對于任一確定的無向圖，鄰接矩陣是唯一的（行列號與頂點編號一致），但鄰接表不唯一（鏈接次序與頂點編號無關）。②鄰接矩陣的空間復雜度為O(n2)，而鄰接表的空間復雜度為O(n+e)。48討論：鄰接表與鄰接矩陣有什么異同之處？3.用途鄰接矩陣多用于稠密圖的存儲（e接近n(n-1)/2)；鄰接表多用于稀疏圖的存儲（e<<n2)49圖的鄰接表在機內如何表示？（參見教材P163）50它是有向圖的另一種鏈式結構。思路：將鄰接矩陣用鏈表存儲，是鄰接表、逆鄰接表的結合。1、開設弧結點，設5個域（每段弧是一個數據元素）2、開設頂點結點，設3個域（每個頂點也是一個數據元素）3.十字鏈表表示法（用在有向圖）51tailvexheadvexhlinktlinkinfodata:頂點信息Firstin:以頂點為弧頭的第一條弧結點Firstout:以頂點為弧尾的第一條弧結點dataFirstinFirstout頂點結點弧結點3.十字鏈表表示法（用在有向圖）tailvex:弧尾頂點位置headvex:弧頭頂點位置hlink:弧頭相同的下一弧位置tlink:弧尾相同的下一弧位置info:弧信息n個頂點的集合怎樣儲存？仍用順序存儲結構52v1v2v3v4202^^33^03^^1例：畫出有向圖的十字鏈表。十字鏈表優(yōu)點：容易操作，如求頂點的入度、出度等。FirstoutFirstindata頂點結點infotlinkhlinkheadvextailvex弧結點0v11v22v33v40123010^^2此無權圖未開第4分量空間復雜度和建表的時間復雜度都與鄰接表相同。53#defineMAX_VERTEX_NUM20十字鏈表存儲結構描述：typedefstructArcBox{//弧結點結構，5分量

inttailvex,headvex;structArcBox*hlink,*tlink;InfoType*info;}ArcBox;typedefstructVexNode{//頂點結構,3分量

VertexTypedata;ArcBox*firstin,*firstout;}VexNode;typedefstruct{//圖結構,整體概念

VexNodexlist[MAX_VERTEX_NUM];//表頭向量

intvexnum,arcnum;}OLGraph;54這是無向圖的另一種存儲結構，當對邊操作時建議采用此種結構存儲。

1、設立邊結點，6個域（每條邊是一個數據元素）2、設立頂點結點，2個域（每個頂點也是一個數據元素）4.鄰接多重表表示法（用在無向圖）55markivexilinkjvexjlinkinfo邊結點data:存儲頂點信息Firstedge:依附頂點的第一條邊結點dataFirstedge頂點結點4.鄰接多重表表示法（用在無向圖）mark：標志域，是否搜索過ivex，jvex:邊依附的兩個頂點位置ilink:指向下一條依附頂點i的邊位置jlink:指向下一條依附頂點j的邊位置info:邊信息n個頂點的集合怎樣儲存？仍用順序存儲結構56121^4232^43^4^v1v2v3v5v4v4例：畫出無向圖的鄰接多重表鄰接多重表優(yōu)點：減少了邊結點的數量0v11v22v33v44v501234Firstedgedata頂點結點markinfojlinkjvexilinkivex邊結點空間復雜度和建表的時間復雜度都與鄰接表相同。01^…03此無權圖未開第6分量577.3圖的遍歷遍歷定義：從已給的連通圖中某一頂點出發(fā)，沿著一些邊，訪遍圖中所有的頂點，且使每個頂點僅被訪問一次，就叫做圖的遍歷，它是圖的基本運算。遍歷實質：找每個頂點的鄰接點的過程。具有遞歸性，在遍歷過程中需要用到堆棧。587.3圖的遍歷圖的特點：圖中可能存在回路，且圖的任一頂點都可能與其它頂點相通，在訪問完某個頂點之后可能會沿著某些邊又回到了曾經訪問過的頂點。59怎樣避免重復訪問？解決思路：可設置一個輔助數組visited[n]，用來標記每個被訪問過的頂點。它的初始狀態(tài)為0，在圖的遍歷過程中，一旦某一個頂點i

被訪問，就立即改visited[i]為1，防止它被多次訪問。7.3圖的遍歷60圖常用的遍歷一、深度優(yōu)先搜索二、廣度優(yōu)先搜索61一、深度優(yōu)先搜索(DFS)基本思想：——仿樹的先序遍歷過程。Depth_FirstSearchv1v1v2v3v8v7v6v4v5DFS結果例1：→→→→→→→v2v4v8v5v3v6v7例2：v2→v1→v3→v5→DFS結果v4→v6起點起點遍歷步驟應退回到V8，因為V2已有標記62深度優(yōu)先搜索（遍歷）步驟：簡單歸納：

訪問起始點v;

若v的第1個鄰接點沒訪問過，深度遍歷此鄰接點；若當前鄰接點已訪問過，再找v的第2個鄰接點重新遍歷。63討論1：計算機如何實現DFS？123456100000020000003000000400000050000006000000000000123456010000110000111000111010111110111111DFS結果鄰接矩陣A輔助數組visited[n]起點——開輔助數組visited[n]！例：123456101110021000103100010410000150110006000100v2→→→→→v1v3v5v4v6請注意逐級回退是遞歸概念64for(j=1;j<=n;j++)if(A[v,j]&&!visited[j])DFS(A,n,j);return;}//DFS討論2：DFS算法如何編程？DFS(A,n,v){visit（v）;visited[v]=1;——可以用遞歸算法！//A[n][n]為鄰接矩陣，v為起始頂點(編號）//訪問（例如打?。╉旤cvA[v,j]＝1有鄰接點visited[j]=0未訪問過//訪問后立即修改輔助數組標志//從v所在行從頭搜索鄰接點（教材上DFS遞歸算法見P169）65討論3：在圖的鄰接表中如何進行DFS？DFS結果00000123輔助數組visited[n]1000110011101111例：—照樣借用visited[n]！起點0123注意：在鄰接表中，并非每個鏈表元素（表結點）都被掃描到,因此遍歷速度很快。v0→→→v1v2v366討論4：

鄰接表的DFS算法如何編程？//訪問后立即修改輔助數組標志——仍用遞歸算法intvisited[];//初始化輔助數組,元素均為0

VoidDFS(List,v,p)//設p為v的頭指針{visit(v);//訪問起點

visited[v]=1;//起點已訪問,0變1

while(p->link)//當存在起點的第一個鄰接點時

{p=p->link;

v=p->data;

if(!visited[v])DFS(List,v,p);//進行遞歸

}

return;

}鄰接表非遞歸深度遍歷算法6768DFS算法效率分析（設圖中有n個頂點，e條邊）如果用鄰接矩陣來表示圖，遍歷圖中每一個頂點都要從頭掃描該頂點所在行，因此遍歷全部頂點所需的時間為O(n2)。如果用鄰接表來表示圖，雖然有2e個表結點，但只需掃描e個結點即可完成遍歷，加上訪問n個頭結點的時間，因此遍歷圖的時間復雜度為O(n+e)。DFS算法效率分析結論：稠密圖適于在鄰接矩陣上進行深度遍歷；稀疏圖適于在鄰接表上進行深度遍歷。6970二、廣度優(yōu)先搜索(BFS)基本思想：——仿樹的層次遍歷過程。Breadth_FirstSearchv1v1v2v3v8v7v6v4v5BFS結果例1：→→→→v2v3→v4v5→v6v7→v8例2：v3→BFS結果v4→v5→起點遍歷步驟起點v2→v1→v6→v9→v8→v771廣度優(yōu)先搜索（遍歷）步驟：簡單歸納：在訪問了起始點v之后，依次訪問v的鄰接點；然后再依次（順序）訪問這些點（下一層）中未被訪問過的鄰接點；直到所有頂點都被訪問過為止。72廣度優(yōu)先搜索（遍歷）步驟：廣度優(yōu)先搜索是一種分層的搜索過程，每向前走一步可能訪問一批頂點，不像深度優(yōu)先搜索那樣有回退的情況。因此，廣度優(yōu)先搜索不是一個遞歸的過程，其算法也不是遞歸的。在遍歷過程中需要用到隊列。73討論1：計算機如何實現BFS？鄰接表廣度優(yōu)先搜索要借助隊列！例：起點輔助隊列visited[n]仍需要v2已訪問過了V2入隊BFS遍歷結果74討論2：

BFS算法如何編程？——層次遍歷應當用隊列！（教材上BFS算法見P170）75若對如下無向圖進行遍歷,則下列選項中,不是廣度優(yōu)先遍歷序列的是()h,c,a,b,d,e,g,fAe,a,f,g,b,h,c,dBd,b,c,a,h,e,f,gCa,b,c,d,h,e,f,gD提交單選題1分此題未設置答案，請點擊右側設置按鈕76BFS算法效率分析如果使用鄰接表來表示圖，則BFS循環(huán)的總時間代價為d0+d1+…+dn-1=O(e)，其中的di是頂點i的度。如果使用鄰接矩陣，則BFS對于每一個被訪問到的頂點，都要循環(huán)檢測矩陣中的整整一行（n個元素），總的時間代價為O(n2)。（設圖中有n個頂點，e條邊）77BFS算法效率分析DFS與BFS之比較：空間復雜度相同，都是O(n)(借用堆棧或隊列裝n個頂點）；時間復雜度只與存儲結構（鄰接矩陣或鄰接表）有關，而與搜索路徑無關。787.4圖的連通性問題1.求圖的生成樹2.求最小生成樹

791.求圖的生成樹（或生成森林）生成樹：是一個極小連通子圖，它含有圖中全部頂點，但只有n-1條邊。生成森林：由若干棵生成樹組成，含全部頂點，但構成這些樹的邊是最少的。1.求圖的生成樹（或生成森林）思考1：若對連通圖進行遍歷，得到的是什么？

—得到的將是一個極小連通子圖，即圖的生成樹！

由深度優(yōu)先搜索得到的生成樹，稱為深度優(yōu)先搜索生成樹。由廣度優(yōu)先搜索得到的生成樹，稱為廣度優(yōu)先搜索生成樹。801.求圖的生成樹（或生成森林）思考2：若對非連通圖進行遍歷，得到的是什么？得到的將是各連通分量的生成樹，即圖的生成森林！81821.求圖的生成樹生成樹的特征——n個頂點的連通網絡的生成樹有n個頂點、n-1條邊。這是生成樹的必要條件。求生成樹的方法——DFS（深度優(yōu)先搜索）和BFS（廣度優(yōu)先搜索）83例1：畫出下圖的生成樹DFS生成樹v0v1v2v4v4v3鄰接表01234^1334^142^0v4v3v2v1v023^142^0v0v2v1v4v3BFS生成樹v0v1v3v2v4無向連通圖84其實由鄰接矩陣或鄰接表也能直接畫出生成森林DEABCFJLMGHIK例2：畫出下圖的生成森林（或極小連通子圖）求解步驟：Step1:先求出鄰接矩陣或鄰接表；Step2:寫出DFS或BFS結果序列；Step3:畫出對應子圖或生成森林。這是一個無向非連通圖（參見教材P170-171例）下面選用鄰接表方式來求深度優(yōu)先搜索生成森林生成森林的定義（對有向或無向圖均適用）：是若干棵生成樹的集合，含全部頂點，但構成這些樹的邊或弧是最少的。85解題步驟1、先寫出鄰接表（或鄰接矩陣）2、再寫出DFS結果ABMJLCF

DEGHKI3、畫出對應子圖或生成森林。861155M12L11K10J9I8H7G6F5E4D3C2B1A012^^0^120^0^4^378^106^6^1011^126^709^1219^111^1229^47^10811DEGHIK子圖1：ABCFJLM子圖2：子圖3：最小連通！例2：畫出下圖的生成森林（或極小連通子圖）87DEGHIK子圖(或連通分量)ABCFJLMABCFJLMDEGHIK生成森林例2：畫出下圖的生成森林（或極小連通子圖）88討論：如何求得最小生成樹？最小生成樹（MST）的性質如下：若U集是V的一個非空子集，若(u0,v0)是一條最小權值的邊，其中u0U，v0V-U；則：(u0,v0)必在最小生成樹上。設想一下：先把權值最小的邊歸入生成樹內，逐個遞增，舍去回路邊，則得到的很可能就是最小生成樹！2.求最小生成樹892.求最小生成樹即有權圖目標：在網絡的多個生成樹中，尋找一個各邊權值之和最小的生成樹。902.求最小生成樹首先明確：使用不同的遍歷圖的方法，可以得到不同的生成樹；從不同的頂點出發(fā)，也可能得到不同的生成樹。即生成樹的形狀不唯一。按照生成樹的定義，n個頂點的連通網絡的生成樹肯定有n個頂點和僅僅n-1條邊。2.求最小生成樹構造最小生成樹的準則必須只使用該網絡中的邊來構造最小生成樹；必須使用且僅使用n-1條邊來聯結網絡中的n個頂點；不能使用產生回路的邊。9192欲在n個城市間建立通信網，則n個城市應鋪n-1條線路；但因為每條線路都會有對應的經濟成本，而n個城市可能有n(n-1)/2條線路，那么，如何選擇n–1條線路使總費用最少？典型用途：93典型用途：先建立數學模型：頂點———表示城市，有n個；邊————表示線路，有n–1條；邊的權值—表示線路的經濟代價；連通網——表示n個城市間的通信網。顯然此連通網是一棵生成樹！94典型用途：問題抽象：n個頂點的生成樹很多，需要從中選一棵代價最小的生成樹，即該樹各邊的代價之和最小。此樹便稱為最小生成樹MST。MinimumcostSpanningTree952.求最小生成樹目標：在網的多個生成樹中，尋找一個各邊權值之和最小的生成樹。應用：n個城市建網，如何選擇n–1條線路，使總費用最少？962.求最小生成樹Kruskal（克魯斯卡爾）算法Prim（普里姆）算法算法：歸并邊歸并頂點97Kruskal（克魯斯卡爾）算法例：14652315655463621543213524698計算機內怎樣實現Kruskal算法？

特點：將邊歸并——適于求稀疏網的最小生成樹。故采用鄰接表作為圖的存儲表示。99（1）初始狀態(tài)：U={u0},（u0∈V），TE={},（2）從E中選擇頂點分別屬于U、V-U兩個集合、且權值最小的邊（u0,v0)，將頂點v0歸并到集合U中，邊（u0,v0)歸并到TE中；（3）直到U=V為止。此時TE中必有n-1條邊，

T＝（V，{TE}）就是最小生成樹。設：N=（V,E）是個連通網，另設U為最小生成樹的頂點集，TE為最小生成樹的邊集。構造步驟:普利姆（Prim）算法(重點）100例：用PRIM算法實現最小生成樹364251[注]：在最小生成樹的生成過程中，所選的邊都是一端在V-U中，另一端在U中。1465231565546362計算機內怎樣實現Prim（普里姆）算法？Prime算法特點:將頂點歸并，與邊數無關，適于稠密網。故采用鄰接矩陣作為圖的存儲表示。問題：如何求連續(xù)輸入的n個數的最小值？102設計思路：①增設一輔助數組Closedge[n]，每個數組分量都有兩個域：要求：使Colsedge[i].lowcost=min((u,vi))uU計算機內怎樣實現Prim（普里姆）算法？adjvexlowcostvi

在U中的鄰點u，已歸并點Colsedge[i]V-U中頂點vi，未歸并點u與vi之間對應的權值最小的邊更新技巧：通常用未歸并頂點vi和新歸并頂點u直連距離與上次求得的最短距離進行比較103adjvexlowcostadjvexlowcostadjvexlowcostadjvexlowcostadjvexlowcostadjvexlowcostV-UU65432vclosedge1423561655536426具體示例（算法求解過程）{1}{2,3,4,5,6}1611151∞1∞{1,3}{2,4,5,6}035153634{1,3,6}{2,4,5}35062360{1,3,6,4}{2,5}3503600{1,3,6,4,2}{5}00002300000{1,3,6,4,2,5}{}1起點4253123456顯然，Prim算法的時間效率＝O（n2）104i<=G.vexnumk=locateVex(G,u);for(j=0;j<G.vexnum;++j)if(j!=k)closedge[j]={u,G.arcs[k,j].adj;Closedge[k].lowcost=0;k=minmum(closedge);closedge[k].lowcost=0;EndNprintf(closedge[k].adjvex,G.vexs(k));j<G.vexnumG.arcs[k,j].adj<closedge[j].lowcostclosedge[j]={G.vexs[k],G.arcs[k,j].adj};++j;++i;NNYYY初始化過程求出權值最小的邊重新求V-U中每個頂點的closedge[]；closedge[j]是上一次求得的j頂點到U集合的最短距離，當k點加入U后，只須在k與j之間的直連距離和上次求得的最短距離之間選較小者作為closedge[j]算法流程Prime算法實現105106在圖采用鄰接表存儲時,求最小生成樹的Prim算法的時間復雜度為()。O(n)AO(n+e)BO(n2)CO(n3)D提交單選題1分1077.5有向無環(huán)圖及其應用（1）

AOV網(ActivityOnVertices)—用頂點表示活動的網絡AOV網定義：若用有向圖表示一個工程，在圖中用頂點表示活動，用弧表示活動間的優(yōu)先關系。Vi必須先于活動Vj進行。則這樣的有向圖叫做用頂點表示活動的網絡，簡稱AOV。有兩種常用的活動網絡（ActivityNetwork）1087.5有向無環(huán)圖及其應用（2）AOE網(ActivityOnEdges)—用邊表示活動的網絡AOE網定義：如果在無環(huán)的帶權有向圖中，用有向邊表示一個工程中的活動，用邊上權值表示活動持續(xù)時間，用頂點表示事件，則這樣的有向圖叫做用邊表示活動的網絡，簡稱AOE。有兩種常用的活動網絡（ActivityNetwork）1097.5.1AOV網絡的用途

我們經常用有向圖來描述一個工程或系統的進行過程。一般來說，一個工程可以分為若干個子工程，只要完成了這些子工程，就可以導致整個工程的完成。AOV網絡若用于教學計劃的制定，可以解決：哪些課程是必須先修的，哪些課程是可以并行學習的。1107.5.1AOV網絡的用途預備知識：拓撲排序什么叫拓撲排序？——對一個有向無環(huán)圖中的頂點排成一個具有前后次序的線性序列。功能：借助于拓撲排序，能夠判斷有向圖中是否有回環(huán)；確定活動的先后順序；111進行拓撲排序的方法輸入AOV網絡。令n為頂點個數；

在AOV網絡中選一個沒有直接前驅的頂點,并輸出之;

從圖中刪去該頂點,同時刪去所有它發(fā)出的有向邊;

重復以上2、3步,直到：全部頂點均已輸出，拓撲有序序列形成，拓撲排序完成；或：圖中還有未輸出的頂點，但已跳出處理循環(huán)。這說明圖中還剩下一些頂點，它們都有直接前驅，再也找不到沒有前驅的頂點了。這時AOV網絡中必定存在有向環(huán)。112進行拓撲排序的方法拓撲排序算法關鍵：重復選擇沒有直接前驅的頂點。算法見教材P182113拓撲排序的過程114

最后得到的拓撲有序序列為C4,C0,C3,C2,C1,C5

。它滿足圖中給出的所有前驅和后繼關系，對于本來沒有這種關系的頂點，如C4和C2，也排出了先后次序關系。115AOV網絡及其鄰接表表示116下面哪一方法可以判斷出一個有向圖是否有環(huán)(回路):()深度優(yōu)先遍歷A拓撲排序B求最短路徑C求關鍵路徑D提交單選題1分拓撲排序算法的實現代碼117118對下圖進行拓補排序,可以得到不同的拓補序列的個數是()4A3B2C1D提交單選題1分1197.5.2AOE網絡的用途常用于大型工程的計劃管理。利用AOE網絡可以解決以下兩個問題：

(1)完成整個工程至少需要多少時間(假設網絡中沒有環(huán))？(2)為縮短完成工程所需的時間,應當加快哪些活動？或者說，哪些活動是影響工程進度的關鍵？預備知識：關鍵路徑120什么叫關鍵路徑？在AOE網絡中,有些活動順序進行，有些活動并行進行；從源點到各個頂點，以至從源點到匯點的有向路徑可能不止一條。這些路徑的長度也可能不同。完成不同路徑的活動所需的時間雖然不同，但只有各條路徑上所有活動都完成了，整個工程才算完成；121什么叫關鍵路徑？3.因此，完成整個工程所需的時間取決于從源點到匯點的最長路徑長度，即在這條路徑上所有活動的持續(xù)時間之和。這條路徑長度最長的路徑就叫做關鍵路徑(CriticalPath)。122關鍵路徑是事件結點網絡中()。從源點到匯點的最長路徑A從源點到匯點的最短路徑B最長回路C最短回路D提交單選題1分123下列關于AOE網的敘述中,不正確的是()。關鍵活動不按期完成就會影響整個工程的完成時間A任何一個關鍵活動提前完成,那么整個工程將會提前完成B所有的關鍵活動提前完成,那么整個工程將會提前完成C某些關鍵活動提前完成,那么整個工程將會提前完成D提交單選題1分124什么叫關鍵路徑？構造關鍵路徑的方法：見教材P184

要用到拓撲排序和逆拓撲排序125關鍵路徑問題:

假設以有向網表示一個施工流圖，弧上的權值表示完成該項子工程所需時間。問：哪些子工程項是“關鍵工程”?即：哪些子工程項將影響整個工程的完成期限的。126整個工程完成的時間為：從有向圖的源點到匯點的最長路徑。abcdefghk64521187244例如:“關鍵活動”指的是：該弧上的權值增加將使有向圖上的最長路徑的長度增加。源點匯點6174127

如何求關鍵活動？

什么是“關鍵活動”？該活動的最早開始時間

=該活動的最遲開始時間ijdut128事件(頂點)的最早發(fā)生時間ve(j)ve(j)=從源點到頂點j的最長路徑長度;事件(頂點)的最遲發(fā)生時間vl(k)vl(k)=匯點長度-從頂點k到匯點的最長路徑長度;關鍵路徑專業(yè)術語129活動最早發(fā)生時間：假設開始點是V1，活動的起始點為Vi，則從V1到Vi的最長的路徑的長度叫做活動ee(i)的最早發(fā)生時間?；顒幼钸t開始時間：不推遲整個工程完成的前提下，活動el(i)最遲必須開始進行的時間。關鍵路徑專業(yè)術語vivjee(i)130

假設第i條弧為<j,k>，則對第i項活動言“活動(弧)”的最早開始時間用ee(i)表示，則

ee(i)=ve(j)(事件j最早開始時間）“活動(弧)”的最遲開始時間用el(i)表示，則

el(i)=vl(k)–dut(<j,k>);關鍵路徑專業(yè)術語jkdutel(i)1311、事件（頂點）最早開始時間

ve(源點)=0;ve(k)=Max{ve(j)+dut(<j,k>)}2、事件（頂點）最晚開始時間

vl(匯點)=ve(匯點);vl(j)=Min{vl(k)–dut(<j,k>)}=vl(k)–Max{(dut<j,k>)}事件發(fā)生時間的計算公式:jkdutel(i)132如何求關鍵路徑？關鍵：求出各個事件最早發(fā)生時間ve(j)和最遲發(fā)生時間vl(j)。再判斷各活動ee(i)是否等于el(i)！133abcdefghk6452118724400000000064571157151418181818181818181818161486610807拓撲有序序列:a-d-f-c-b-e-h-g-k如何求關鍵路徑？1340645771514181814161078660000645777151414160236688710如何求關鍵路徑？135

算法的實現要點:顯然，求ve的順序應該是按拓撲有序的次序;而求vl的順序應該是按拓撲逆序的次序;

因為拓撲逆序序列即為拓撲有序序列的逆序列，因此應該在拓撲排序的過程中，另設一個“隊列”記下拓撲有序序列。136下面關于求關鍵路徑的說法不正確的是()。求關鍵路徑是以拓撲排序為基礎的A一個事件的最早開始時間同以該事件為尾的弧的活動最早開始時間相同B一個事件的最遲開始時間為以該事件為尾的弧的活動最遲開始時間與該活動的持續(xù)時間的差C關鍵活動一定位于關鍵路徑上D提交單選題1分137下列關于AOE網的敘述中,不正確的是()。關鍵活動不按期完成就會影響整個工程的完成時間A任何一個關鍵活動提前完成,那么整個工程將會提前完成B所有的關鍵活動提前完成,那么整個工程將會提前完成C某些關鍵活動提前完成,那么整個工程將會提前完成D提交單選題1分138（1）列出所有的關鍵路徑；（2）完成整個工程至少需要多少時間？（3）事件V5的最早完成時間是多少？（4）活動a6的最早開工時間是多少？a2=101.對于下面的AOE網絡，試回答下列問題：作業(yè)題139273648915a1=5a4=9a2=10a9=15a10=14a13=12a12=6a6=12a5=7a7=8a8=12a11=8a3=8vevlv1v2v3v4v5v6v7v8v9ela1a2a3a4a5a6a7a8a9a10a11a12a130515927233541530523271615354153050092315155272735410577162315151227273541求關鍵路徑算法實現1401417.6最短路徑典型用途：交通問題。如：城市A到城市B有多條線路，但每條線路的交通費（或所需時間）不同，那么，如何選擇一條線路，使總費用（或總時間）最少？1427.6最短路徑問題抽象：在帶權有向圖中A點（源點）到達B點（終點）的多條路徑中，尋找一條各邊權值之和最小的路徑，即最短路徑。（注：最短路徑與最小生成樹不同，路徑上不一定包含n個頂點）143兩種常見的最短路徑問題一、單源最短路徑—用Dijkstra（迪杰斯特拉）算法二、所有頂點間的最短路徑—用Floyd（弗洛伊德）算法一頂點到其余各頂點任意兩頂點之間144一、單源最短路徑(Dijkstra算法)目的：設一有向圖G=（V,E），已知各邊的權值，以某指定點v0為源點，求從v0到圖的其余各點的最短路徑。限定各邊上的權值大于或等于0。145一、單源最短路徑(Dijkstra算法)例1：源點從F→A的路徑有4條：①F→A：24②F→B→A：5＋18=23③F→B→C→A：5+7+9=21④F→D→C→A：25+12+9=36又：從F→B的最短路徑是哪條？從F→C的最短路徑是哪條？146v0(v0,v1)10源點終點

最

短路

徑路徑長度(v0,v1,v2)(v0,v3,v2)(v0,v3)30

v1

v2

v3

v4100(v0,v4)(v0,v3,v4)(v0,v3,v2,v4)例2：6001234509070(v0,v1,v2,v4)60一、單源最短路徑(Dijkstra算法)147Dijkstra（迪杰斯特拉）算法算法思想：（1）先找出從源點v0到各終點vk的直達路徑（v0,vk），即通過一條弧到達的路徑；（2）從這些路徑中找出一條長度最短的路徑（v0,u）,然后對其余各條路徑進行適當調整：若在圖中存在弧（u,vk），且（v0,u）+（u,vk）<（v0,vk）,則以路徑（v0,u,vk）代替（v0,vk）。其中，（v0,u）為上次求得的v0到u最短路徑；（3）在調整后的各條路徑中，再找長度最短的路徑，依此類推。總之，按路徑“長度”遞增的次序來逐步產生最短路徑148算法具體描述（1）設A[n][n]為有向網的帶權鄰接矩陣，A[i][j]表示?。╲i，vj)的權值，S為已找到從源點v0出發(fā)的最短路徑的終點集合，它的初始狀態(tài)為{v0}，輔助數組dist[n]為源點v0各終點當前找到的最短路徑的長度，它的初始值為：dist[i]＝A[v0,i]//即鄰接矩陣中第v0行的權值；149算法具體描述（2）選擇u，使得

dist[u]＝min{dist[w]|w∈V-S}/*w是S集之外的頂點，u是當前離源點距離最短的頂點，dist[u]是從源點v0到S集合之外所有頂點的路徑中距離最短的一條*/

S=S∪{u}//u將u加入S集150算法具體描述（4）重復操作(2)、(3)共n-1次，由此求得從v0到各終點的最短路徑。（3）對于所有不在S中的終點w，若

dist[u]+A[u,w]<dist[w]//即(v0,u)＋(u,w)<(v0,w)則修改dist[w]為：dist[w]＝dist[u]+A[u,w]

dist[u]為上次求得從源點到u點的最短路徑，u為上次求得最短路徑的點。151終點

從v0到各終點的dist值和最短路徑v1v2v3v4v5vjS之外的當前最短路徑之頂點60{v0,v2,v3}50{v0,v4,v3}30{v0,v4}90{v0,v4,v5}60{v0,v4,v3,v5}5540312100603010102050s{v0,v2}{v0,v2,v4}{v0,v2,v4,v3}{v0,v2,v4,v3,v5}10{v0,v2}∞

30{v0,v4}100{v0,v5}∞∞∞∞例3：v2v4v3v5100{v0,v5}012345dist[w]012345與最小生成樹的不同點：路徑可能是累加的！10{v0,v2}50{v0,v4,v3}30{v0,v4}v0,v2)+(v2,v3)<(v0,v3)152如下有向帶權圖,若采用迪杰斯特拉算法求源點a到其他各頂點的最短路徑,得到的第一條最短路徑的目標頂點是b,第二條最短路徑的目標頂點是c,后續(xù)得到的其余各最短路徑的目標頂點依次是()d,e,fAe,d,fBf,d,eCf,e,dD提交單選題1分153算法的C語言程序見教材P189154求V1結點到各點的最短距離作答正常使用主觀題需2.0以上版本雨課堂主觀題10分155二、所有頂點之間的最短路徑問題的提出：已知一個各邊權值均大于0的帶權有向圖，對每一對頂點vi

vj，希望求出vi

與vj之間的最短路徑和最短路徑長度。解決思路：可以通過調用n次Dijkstra算法來完成，但時間復雜度為O(n3)。改進：Floyd算法

Floyd弗洛伊德給出了另一個算法，時間復雜度也是O（n3），但是形式上簡單些。Floyd算法：求任意二點之間最短路徑從演示中看算法思想一個簡單的圖及其鄰接矩陣如下：abc116423abca(aa,0)(ab,4)(ac,11)b(ba,6)(bb,0)(bc,2)c(ca,3)(cb,∞)(cc,0)D(-1)Floyd算法：求任意二點之間最短路徑從上面的D（-1）開始，對于每兩個頂點u、v，在D（-1）中存儲著一條路徑u…v。現在我們考察，試著把a加到u、v的路徑上能否，得到一條更短的路徑，即如果u…a+a…v<u…v的話，能夠找到一條更短的路徑。Floyd算法：求任意二點之間最短路徑abc116423abca(aa,0)(ab,4)(ac,11)b(ba,6)(bb,0)(bc,2)c(ca,3)(cb,∞)(cc,0)D(-1)abca(aa,0)(ab,4)(ac,11)b(ba,6)(bb,0)c(ca,3)(cc,0)D(0)本來路徑上源點或終點就有a的不必考慮。對角線上的也不必考慮Floyd算法：求任意二點之間最短路徑abc116423abca(aa,0)(ab,4)(ac,11)b(ba,6)(bb,0)(bc,2)c(ca,3)(cb,∞)(cc,0)D(-1)abca(aa,0)(ab,4)(ac,11)b(ba,6)(bb,0)c(ca,3)(cc,0)D(0)D[b][a]+D[a][c]=6+11>D[b][c]=2，所以如果從a繞，反而遠，那么這一項不變。Floyd算法：求任意二點之間最短路徑abc116423abca(aa,0)(ab,4)(ac,11)b(ba,6)(bb,0)(bc,2)c(ca,3)(cb,∞)(cc,0)D(-1)abca(aa,0)(ab,4)(ac,11)b(ba,6)(bb,0)(bc,2)c(ca,3)(cc,0)D(0)Floyd算法：求任意二點之間最短路徑abc116423abca(aa,0)(ab,4)(ac,11)b(ba,6)(bb,0)(bc,2)c(ca,3)(cb,∞)(cc,0)D(-1)abca(aa,0)(ab,4)(ac,11)b(ba,6)(bb,0)(bc,2)c(ca,3)(cc,0)D(0)D[c][a]+D[a][b]=3+4<D[c][b]=∞，所以如果從a繞，更近，那么應該更新。Floyd算法：求任意二點之間最短路徑abc116423abca(aa,0)(ab,4)(ac,11)b(ba,6)(bb,0)(bc,2)c(ca,3)(cb,∞)(cc,0)D(-1)abca(aa,0)(ab,4)(ac,11)b(ba,6)(bb,0)(bc,2)c(ca,3)(cab,7)(cc,0)D(0)Floyd算法：求任意二點之間最短路徑從上面的D（0）開始，對于每兩個頂點u、v，在D（0）中存儲著一條路徑u…v。現在我們考察，試著把b加到u、v的路徑上能否，得到一條更短的路徑，即如果u…b+b…v<u…