《數(shù)據(jù)結(jié)構(gòu)JAVA語言版》課件 第7章 圖

第七章圖

在線性表中，結(jié)點(diǎn)之間的關(guān)系是線性關(guān)系，除第一個(gè)結(jié)點(diǎn)和最后一個(gè)結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)只有一個(gè)前趨和一個(gè)后繼。

在樹中，結(jié)點(diǎn)之間的關(guān)系實(shí)質(zhì)上是層次關(guān)系，除根結(jié)點(diǎn)之外，其余結(jié)點(diǎn)都只有一個(gè)前驅(qū)，但可以有0個(gè)或多個(gè)后繼。

在圖結(jié)構(gòu)中，對(duì)結(jié)點(diǎn)的前趨和后繼個(gè)數(shù)都是不加限制的，即結(jié)點(diǎn)可以有0個(gè)或多個(gè)前驅(qū)，也可以有0個(gè)或多個(gè)后繼。（結(jié)點(diǎn)之間的關(guān)系是任意的）7.1圖的定義和術(shù)語1、有向圖（直觀的說：帶箭頭的就是有向圖）v1v2v4v3頂點(diǎn)（vertex）即圖中的圓圈。該有向圖共有四個(gè)頂點(diǎn)：v1,v2,v3,v4.弧(arc)即圖中的箭頭，也稱有向邊。該有向圖共有4條弧。記為<v1,v3>,<v1,v2>,<v3,v4>,<v4,v1>弧尾,弧頭：弧<v1,v3>的弧尾是v1，弧頭是v3。有向圖的二元組描述：頂點(diǎn)的集合和弧的集合來描述有向圖。G1＝（V，A）其中V={v1,v2,v3,v4},A={<v1,v3>,<v1,v2>,<v3,v4>,<v4,v1>}v1v2v4v3請(qǐng)用二元組描述下圖。ABCDV={A,B,C,D}

A={<A,B>,<A,C>,<C,D>,<D,C>,<D,A>,<B,D>}有向完全圖：有n個(gè)頂點(diǎn)的有向圖有n(n-1)條弧，則此圖為完全有向圖。判斷下列有向圖是不是完全有向圖？v1v2v4v3v1v4v3子圖：設(shè)有兩個(gè)有向圖G＝(V,A)和G’＝(V’,A’)。若V’

V且A’

A,則稱圖G’

是圖G的子圖。v1v2v4v3v1v4v3v1v2v4v3v1v2v4v3有向圖G1

判斷下面三圖是不是有向圖G1的子圖？如果在有向圖中存在弧<VP,Vq>，稱VP鄰接到Vq；Vq鄰接自VP。BACD權(quán)：有向圖的弧具有與它相關(guān)的數(shù)，這種與圖的弧相關(guān)的數(shù)叫權(quán)。帶權(quán)的圖也稱網(wǎng)?；?lt;v6,v1>的權(quán)是？頂點(diǎn)的入度InDegree：以頂點(diǎn)v為頭的弧的數(shù)目。記為ID(v)。v1頂點(diǎn)的入度是？頂點(diǎn)的出度OutDegree：以頂點(diǎn)v為尾的弧的數(shù)目。記為OD(v)。v1頂點(diǎn)的出度是？頂點(diǎn)的度TotalDegree：等于頂點(diǎn)的入度加頂點(diǎn)的出度。TD(v)=ID(v)+OD(v)v1頂點(diǎn)的度是？

路徑：在一圖中若從某個(gè)頂點(diǎn)VP出發(fā)，沿著一些弧經(jīng)過頂點(diǎn)V1，V2，...Vm到達(dá)Vq則稱頂點(diǎn)序列（Vp,V1,V2...Vm,Vq)為從Vp到Vq的路徑。頂點(diǎn)v6到v3的路徑有（V6，V1,V2，V3）頂點(diǎn)v6到v3的路徑有（V6，V5,V4，V3）頂點(diǎn)v6到v3的路徑有（V6，V1,V4，V3）路徑長(zhǎng)度：定義為該路徑上弧的數(shù)目。簡(jiǎn)單路徑：頂點(diǎn)V1,V2...Vm,均不相同，則稱此路徑為一條簡(jiǎn)單路徑。簡(jiǎn)單回路或簡(jiǎn)單環(huán)(Cycle)：起點(diǎn)和終點(diǎn)相同(vp＝vq)的簡(jiǎn)單路徑稱為簡(jiǎn)單回路或簡(jiǎn)單環(huán)(Cycle)。

對(duì)于有向圖，若從頂點(diǎn)Vp到頂點(diǎn)Vq以及從頂點(diǎn)Vq到頂點(diǎn)Vp之間都有路徑，則稱這兩點(diǎn)是強(qiáng)連通的。強(qiáng)連通圖：對(duì)于有向圖中任意兩個(gè)頂點(diǎn)Vp,Vq,從Vp到Vq，從Vq到Vp，都存在路徑，叫強(qiáng)連通圖。v1v2v4v3有向圖G1頂點(diǎn)V3和V4是不是強(qiáng)連通的？頂點(diǎn)V2和V4是不是強(qiáng)連通的？圖G1是不是強(qiáng)連通圖？判斷下列兩圖是不是強(qiáng)連通圖？v1v4v3v2第一個(gè)圖：因?yàn)槿我鈨蓚€(gè)頂點(diǎn)之間都有路徑，所以是連通圖。第二個(gè)圖：只有一個(gè)頂點(diǎn)的圖我們也認(rèn)為它是連通圖。

強(qiáng)連通分量：有向圖中的極大連通子圖稱為強(qiáng)連通分量。（復(fù)雜一點(diǎn)的有向圖的強(qiáng)連通分量找起來很麻煩，必須編程序讓計(jì)算機(jī)找。）注意三點(diǎn)問題：首先，它必須是有向圖的子圖。其次，它必須是連通的。再次，它必須是極大的（看有沒有包含它的更大的子圖也是連通的？如果有，它就不是極大的；沒有，它就是極大的）v1v2v4v3有向圖G1例：求圖G1強(qiáng)連通分量。（依次對(duì)每個(gè)子圖用定義去判別）課堂分析：右邊的三個(gè)子圖是不是G1的強(qiáng)連通分量呢？v2v1v1v4v3是有向圖G1的子圖，是連通的。但它是不是極大的呢?能不能找到包含它的更大的子圖也是連通的？找不到包含它的更大的子圖也是連通的，所以它就是極大的。所以它是強(qiáng)連通分量。v1v2v4v3有向圖G1v2是有向圖G1的子圖，是連通的。但它是不是極大的呢?能不能找到包含它的更大的子圖也是連通的？能找到包含它的更大的子圖也是連通的，所以它不是極大的。所以它不是強(qiáng)連通分量。v1v2v4v3有向圖G1v1v1v4v3是有向圖G1的子圖，是連通的。但它是不是極大的呢?能不能找到包含它的更大的子圖也是連通的？找不到包含它的更大的子圖也是連通的，所以它就是極大的。所以它是強(qiáng)連通分量。v1v2v4v3有向圖G1v1v4v3

有向樹：在有向圖中，一個(gè)頂點(diǎn)入度為0，其余頂點(diǎn)的入度都是1，則是一棵有向樹。判斷下面兩個(gè)圖是不是有向樹？v1v4v3v1v4v32、無向圖（直觀的說：不帶箭頭的就是無向圖）v4v5v3v2v1無向圖G2頂點(diǎn)：即圖中的圓圈。無向圖G2共有四個(gè)頂點(diǎn)：v1,v2,v3,v4,v5邊：即圖中的線段。無向圖G2共有6條邊：記為（v1,v2）,（v1,v4）,（v2,v3）,（v2,v5）,（v3,v4）,（v3,v5）.無向圖的二元組表示：

G2＝（V，E）V={v1,v2,v3,v4,v5}E={（v1,v2）,（v1,v4）,（v2,v3）,（v2,v5）,（v3,v4）,（v3,v5）}v4v5v3v2v1無向圖G2例請(qǐng)用二元組描述無向圖DABCV={A,B,C,D}A={（A,B）,（A,C）,（A,D）,(C,D),(B,D)}無向完全圖：有n個(gè)頂點(diǎn)的有向圖有n(n-1)/2條邊則此圖為無向完全圖。

v1v2v4v3v1v4v3

下面兩圖是不是無向完全圖？子圖：設(shè)有兩個(gè)無向圖G＝(V,E)和G’＝(V’,E’)。若V’

V且E’

E,則稱圖G’

是圖G的子圖。

v4v5v3v2v1無向圖G2v4v5v3v2v1v4v5v3v2v1v4v5v3v2v1

下面三個(gè)圖是不是無向圖G2的子圖？如果在有向圖中存在弧<VP,Vq>，稱VP鄰接到Vq；Vq鄰接自VP。如果在無向圖中存在邊(VP,Vq),稱VP和Vq鄰接。BACDv4v5v3v2v1權(quán)：無向圖的邊具有與它相關(guān)的數(shù)，這種與圖的邊相關(guān)的數(shù)叫權(quán)。

頂點(diǎn)的度：與頂點(diǎn)相關(guān)聯(lián)的邊的數(shù)目。

路徑：在一圖中若從某個(gè)頂點(diǎn)VP出發(fā)，沿著一些邊經(jīng)過頂點(diǎn)V1，V2，...Vm到達(dá)Vq則稱頂點(diǎn)序列（VP,V1,V2...Vm,Vq)為從Vp到Vq的路徑。路徑長(zhǎng)度：定義為該路徑上邊的數(shù)目。v4v5v3v2v1無向圖G2

簡(jiǎn)單路徑：對(duì)于路徑(VP,V1,V2...Vm,Vq)

頂點(diǎn)V1,V2...Vm,均不相同，則稱此路徑為一條簡(jiǎn)單路徑。簡(jiǎn)單回路或簡(jiǎn)單環(huán)(Cycle)：起點(diǎn)和終點(diǎn)相同(vp＝vq)的簡(jiǎn)單路徑稱為簡(jiǎn)單回路或簡(jiǎn)單環(huán)。

連通圖：對(duì)于無向圖，若從頂點(diǎn)Vp到頂點(diǎn)Vq有路徑，則稱這兩點(diǎn)是連通的。

對(duì)于無向圖中任意兩個(gè)頂點(diǎn)Vp,Vq都存在路徑，叫連通圖。v4v5v3v2v1無向圖G2連通分量：無向圖中的極大連通子圖稱為連通分量。ABCDEFGIJLHMK無向圖G3ABCDEFGIJLHMK無向圖G3連通圖的生成樹：連通圖的極小連通子圖判斷一個(gè)圖是不是連通圖G的生成樹；看三個(gè)方面：第一個(gè)方面：它是不是連通圖G的子圖？第二個(gè)方面：該子圖是不是連通的？第三個(gè)方面：該連通子圖是不是極小的？極小含義直觀解釋：該連通子圖含有圖的全部N個(gè)頂點(diǎn)和圖的N-1條邊ABCDEHMABCDEHM無向圖G4

無向圖G4的生成樹3、圖的抽象數(shù)據(jù)類型定義ADTGRAPH{數(shù)據(jù)對(duì)象：

D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}(頂點(diǎn)集)//n個(gè)數(shù)據(jù)元素的集合。數(shù)據(jù)元素可以是整型、字符型、結(jié)構(gòu)類型。數(shù)據(jù)關(guān)系：R={頂點(diǎn)集元素之間多對(duì)多的關(guān)系}基本操作：P關(guān)于基本操作的幾點(diǎn)說明：

1、基本操作是定義于邏輯結(jié)構(gòu)上的基本操作，向外界提供一個(gè)與其通訊的接口。還沒有用具體的某種程序語言寫出具體的算法，而算法的實(shí)現(xiàn)只有在存儲(chǔ)結(jié)構(gòu)確立之后。對(duì)應(yīng)于不同的存儲(chǔ)結(jié)構(gòu)，圖的基本操作的實(shí)現(xiàn)也不相同。

2、基本操作的種類可隨實(shí)際需要的不同而不同，定義多少種基本操作由自己確定。

3、針對(duì)不同的需要，基本操作的參數(shù)和返回值可以有所變化。1)、GetNumOfVertex()初始條件：圖存在；

操作結(jié)果：返回圖中的頂點(diǎn)數(shù)。

2)、GetNumOfEdge()初始條件：圖存在；

操作結(jié)果：返回圖中的邊或弧的數(shù)目。

3)、SetEdge(Node<T>v1,Node<T>v2,intv)初始條件：圖存在，頂點(diǎn)v1和v2是圖的兩個(gè)頂點(diǎn)；

操作結(jié)果：在頂點(diǎn)v1和v2之間添加一條邊或弧并設(shè)邊或弧的值為v。4)、DelEdge(Node<T>v1,Node<T>v2)

初始條件：圖存在，頂點(diǎn)v1和v2是圖的兩個(gè)頂點(diǎn)并且v1和v2之間有一條邊或??；

操作結(jié)果：刪除頂點(diǎn)v1和v2之間的邊或弧。

5)、IsEdge(Node<T>v1,Node<T>v2)

初始條件：圖存在，頂點(diǎn)v1和v2是圖的兩個(gè)頂點(diǎn)；

操作結(jié)果：如果v1和v2之間有一條邊或弧，返回true,否則返回false。}7.2圖的存儲(chǔ)結(jié)構(gòu)

1、鄰接矩陣（adjacencymatrix）無權(quán)值的有向圖的鄰接矩陣設(shè)有向圖具有n個(gè)結(jié)點(diǎn)，則用n行n列的布爾矩陣A表示該有向圖；A[i,j]=1,如果i至j有一條有向邊；A[iI,j]=0如果i至j沒有一條有向邊注意：A[i,i]=0。ABCD表示成右圖矩陣0110000000011000

ABCDABCD

無權(quán)值的無向圖的鄰接矩陣設(shè)無向圖具有n個(gè)結(jié)點(diǎn)，則用n行n列的布爾矩陣A表示該無向圖；

A[i,j]=1,如果i至j有一條無向邊；

A[i,j]=0,如果i至j沒有一條無向邊;注意：A[i,i]=0。表示成右圖矩陣0110010011100010100101110ABCDE

ABCDEABCDE有權(quán)值的有向圖的鄰接矩陣設(shè)有向圖具有n個(gè)結(jié)點(diǎn)，則用n行n列的矩陣表示該有向圖；

A[i,j]=a,如果i至j有一條有向邊且它的權(quán)值為a。

A[i,j]=∞,如果i至j沒有一條有向邊。

A[i,i]=0.表示成右圖矩陣有權(quán)值的無向圖的鄰接矩陣設(shè)無向圖具有n個(gè)結(jié)點(diǎn)，則用n行n列的矩陣表示該無向圖；A[i,j]=a,如果i至j有一條無向邊且它的權(quán)值為a。A[i,j]=∞,如果i至j沒有一條無向邊。A[i,i]=0.5v5v4v2v3v1v0651536642表示成右圖矩陣v0

v1v2v3v4v5v00615∞∞v1605∞3∞v2150564v35∞50∞2v4∞36∞06v5∞∞4260有權(quán)值的無向圖的鄰接矩陣設(shè)無向圖具有n個(gè)結(jié)點(diǎn)，則用n行n列的矩陣表示該無向圖；A[i,j]=a,如果i至j有一條無向邊且它的權(quán)值為a。A[i,j]=∞,如果i至j沒有一條無向邊。A[i,i]=0.5v5v4v2v3v1v0651536642表示成右圖矩陣v0v1v2v3v4v5v00615∞∞v1605∞3∞v2150564v35∞50∞2v4∞36∞06v5∞∞4260

2、鄰接表（adjacencylist）無權(quán)值的有向圖的鄰接表BACD表示成右圖鄰接表ABCD12030123nullnullnullnulldatafirstarcheadvexnextarc

數(shù)組的data部分存放頂點(diǎn)的元素，指針部分指向第一條以該頂點(diǎn)為弧尾的弧（到底誰是第一條，是人為規(guī)定的）；弧鏈表中第一個(gè)結(jié)點(diǎn)的數(shù)據(jù)部分存儲(chǔ)該弧的弧頭元素（即它在數(shù)組中的下標(biāo)），指針部分指向第二條以該頂點(diǎn)為弧尾的??；依此類推。（用一條鏈把所有以該頂點(diǎn)為弧尾的弧串起來）。特點(diǎn)：求頂點(diǎn)的出度容易，求頂點(diǎn)的入度困難。

解決方案：逆鄰接表。數(shù)組的data部分存放頂點(diǎn)的元素，指針部分指向第一條以該頂點(diǎn)為弧頭的弧（到底誰是第一條，是人為規(guī)定的）；弧鏈表中第一個(gè)結(jié)點(diǎn)的數(shù)據(jù)部分存儲(chǔ)該弧的弧尾元素（即它在數(shù)組中的下標(biāo)），指針部分指向第二條以該頂點(diǎn)為弧頭的??；依此類推。（用一條鏈把所有以該頂點(diǎn)為弧頭的弧串起來）ABCDAB30123002CDnullnullnull特點(diǎn)：求頂點(diǎn)的入度容易，求頂點(diǎn)的出度困難。練習(xí)：畫出下面無權(quán)值有向圖的鄰接表和逆鄰接表。

有權(quán)值有向圖的鄰接表數(shù)組的data部分存放頂點(diǎn)的元素，指針部分指向第一條以該頂點(diǎn)為弧尾的弧（到底誰是第一條，是人為規(guī)定的）弧鏈表中第一個(gè)結(jié)點(diǎn)的第一部分存儲(chǔ)該弧的弧頭元素（即它在數(shù)組中的下標(biāo)），第二部分存儲(chǔ)該弧的權(quán)值，第三部分即指針部分指向第二條以該頂點(diǎn)為弧尾的?。?/p>

無權(quán)值的無向圖的鄰接表

ABCDEAB1201234nulldatafirstedge03041412CDE43nullnullnullnulladjvexnextedge

數(shù)組的data部分存放頂點(diǎn)的元素，指針部分指向該頂點(diǎn)依附的第一條邊（到底哪是第一條邊，是人為規(guī)定的）；邊鏈表中第一個(gè)結(jié)點(diǎn)的數(shù)據(jù)部分存儲(chǔ)該條邊的另一個(gè)頂點(diǎn)（即該頂點(diǎn)在數(shù)組中的下標(biāo)），指針部分指向該頂點(diǎn)依附的第二條邊；依此類推（用一條鏈把該頂點(diǎn)依附的所有邊串起來）。例：畫出下圖的鄰接表。ABCD0123nullnullnulldatafirstedge

adjvexnextedge231505340314null有權(quán)值的無向圖的鄰接表

結(jié)點(diǎn)的第一部分存儲(chǔ)該條邊的另一個(gè)頂點(diǎn)在數(shù)組中的下標(biāo)；第二部分存儲(chǔ)邊的權(quán)值。數(shù)組的data部分存放頂點(diǎn)的元素；指針部分指向第一條依附的邊；第三部分即指針部分指向該頂點(diǎn)依附的第二條邊（用一條鏈把該頂點(diǎn)依附的所有邊串起來）三條邊卻用了6個(gè)結(jié)點(diǎn)，解決的辦法：鄰接多重表。

3、鄰接多重表（針對(duì)無向圖而言）datafirstedgemarkivexilink邊表中的結(jié)點(diǎn)的表示：頂點(diǎn)表中的結(jié)點(diǎn)的表示：data:結(jié)點(diǎn)的數(shù)據(jù)域，保存結(jié)點(diǎn)的數(shù)據(jù)值。firstedge:結(jié)點(diǎn)的指針域，給出依附于該頂點(diǎn)的第一條邊的邊結(jié)點(diǎn)的地址。info:邊結(jié)點(diǎn)的數(shù)據(jù)域，保存邊的權(quán)值等。mark:邊結(jié)點(diǎn)的標(biāo)志域，用于標(biāo)識(shí)該條邊是否被訪問過。jvexinfoivex:本條邊依附的一個(gè)頂點(diǎn)的在數(shù)組中下標(biāo)。ilink:依附于頂點(diǎn)ivex的下一條邊的地址。jlinkjvex:本條邊依附的另一個(gè)頂點(diǎn)在數(shù)組中的下標(biāo)。jlink:依附于頂點(diǎn)jvex下一條邊的地址。ABCDEAB01234datafirstedgeCDE012441310234∧∧∧∧markivexilinkjvexjlink∧無向圖G2作業(yè)：畫出右圖的鄰接多重表。v4v5v3v2v1v1v2v3v401234103212421430v5

4、十字鏈表(針對(duì)于有向圖而言)datafirstinfirstoutinfotailvexheadvex弧結(jié)點(diǎn)表中的結(jié)點(diǎn)的表示：頂點(diǎn)結(jié)點(diǎn)表中的結(jié)點(diǎn)的表示：data:結(jié)點(diǎn)的數(shù)據(jù)域，保存頂點(diǎn)的數(shù)據(jù)值。firstin:結(jié)點(diǎn)的指針域，給出以該結(jié)點(diǎn)為弧頭的第一條弧的地址。firstout:結(jié)點(diǎn)的指針域，給出以該結(jié)點(diǎn)為弧尾的的第一條弧的地址。info:弧結(jié)點(diǎn)的數(shù)據(jù)域，保存弧的權(quán)值等。hlinktlinktailvex:弧尾。headvex:弧頭。hlink:弧頭相同的弧中的下一條弧的地址。tlink:弧尾相同的弧中的下一條弧的地址。實(shí)例：ABCD有向圖G10123ABCD01022220033331∧∧∧∧∧∧∧∧datafirstinfirstouttailvexheadvexhlink

tlink7.3圖的遍歷什么叫圖的遍歷？從圖的任意點(diǎn)出發(fā)沿著一些邊訪問圖中的所有頂點(diǎn),且使每個(gè)頂點(diǎn)僅被訪問一次,這就叫圖的遍歷.圖的遍歷分為深度優(yōu)先遍歷和廣度優(yōu)先遍歷兩種.

v8v5v4v6v7v1v3v27.3.1深度優(yōu)先遍歷首先訪問出發(fā)點(diǎn)v,將其標(biāo)記為已訪問過;然后依次從v出發(fā)搜索v的每個(gè)鄰接點(diǎn)w,

若w未曾訪問過,則以w為新的出發(fā)點(diǎn)繼續(xù)進(jìn)行深度優(yōu)先遍歷,直至圖中所有和v有路徑相通的頂點(diǎn)均已被訪問過為止;

若此時(shí)圖中仍有未訪問過的節(jié)點(diǎn),則選一個(gè)未訪問過的節(jié)點(diǎn)作為源點(diǎn)重復(fù)上述操作,直至所有節(jié)點(diǎn)均已被訪問過.（遞歸的算法，翻譯成源代碼上機(jī)運(yùn)行效率非常低下）v8v5v4v6v7v1v3v212356487寫出無向圖G4從頂點(diǎn)A出發(fā)的深度優(yōu)先遍歷序列

ABCDEHM無向圖G4

12643757．3.2廣度優(yōu)先遍歷假設(shè)從圖中某頂點(diǎn)出發(fā)，在訪問了V之后依次訪問V的各個(gè)未曾訪問過的鄰接點(diǎn)，然后分別從這些鄰接點(diǎn)出發(fā)依次訪問它們的鄰接點(diǎn)，并使“先被訪問的頂點(diǎn)的鄰接點(diǎn)”先于“后被訪問的頂點(diǎn)的鄰接點(diǎn)”被訪問，直至圖中所有已被訪問的頂點(diǎn)的鄰接點(diǎn)都被訪問到。換句話說；廣度優(yōu)先搜索遍歷圖的過程是以V為起始點(diǎn)，由近及遠(yuǎn)，依次訪問和V有路徑相通且路徑長(zhǎng)度為1，2…的頂點(diǎn)。

v8v5v4v6v7v1v3v212356487寫出無向圖G4從頂點(diǎn)A出發(fā)的廣度優(yōu)先遍歷序列

ABCDEHM無向圖G4

12356477.4圖的連通性問題1、無向圖的連通分量和生成樹ABCDEFGIJLHMKABCDEHMFGIJLK生成樹：極小連通子圖。包含圖的所有n個(gè)結(jié)點(diǎn)，但只含圖的n-1條邊。在生成樹中添加一條邊之后，必定會(huì)形成回路或環(huán)。因?yàn)樵谏蓸涞娜我鈨牲c(diǎn)之間，本來就是連通的，添加一條邊之后，形成了這兩點(diǎn)之間的第二條通路。ABCDEHMABCDEHM無向圖G無向圖G的生成樹生成方法：進(jìn)行深度為主的遍歷或廣度為主的遍歷，得到深度優(yōu)先生成樹或廣度優(yōu)先生成樹。v8v5v4v6v7v1v3v212356487深度優(yōu)先生成樹：進(jìn)行深度優(yōu)先的遍歷，得到深度優(yōu)先生成樹。v8v5v4v6v7v1v3v212356487深度優(yōu)先生成樹：進(jìn)行深度優(yōu)先的遍歷，得到深度優(yōu)先生成樹。作業(yè)：請(qǐng)畫出無向圖G4的深度優(yōu)先生成樹ABCDEHM無向圖G4

ABCDEHM無向圖G4深度優(yōu)先生成樹

v8v5v4v6v7v1v3v212453876廣度優(yōu)先生成樹：進(jìn)行廣度優(yōu)先的遍歷，得到廣度優(yōu)先生成樹。作業(yè)：請(qǐng)畫出無向圖G4的廣度優(yōu)先生成樹ABCDEHM無向圖G4

ABCDEHM無向圖G4廣度優(yōu)先生成樹

生成森林：在進(jìn)行深度優(yōu)先的遍歷或廣度優(yōu)先的遍歷時(shí)，對(duì)于非連通圖，將得到多棵深度優(yōu)先生成樹或廣度優(yōu)先生成樹。稱之為生成森林。ABCDEFGIJLHMKABCDEHMFGIJLKABCDEHMFGIJLK無向圖G的廣度優(yōu)先生成森林請(qǐng)畫出無向圖G的廣度優(yōu)先生成森林。從頂點(diǎn)A開始，從頂點(diǎn)k開始，從頂點(diǎn)F開始。ABCDEFGIJLHMK無向圖G7.4.3最小代價(jià)生成樹（簡(jiǎn)稱：最小生成樹）

(MinimumSpanningCostTree)

1、定義：生成樹中邊的權(quán)值（代價(jià)）之和最小的樹。5v6v5v3v4v2v1651536642v6v5v3v4v2v1153422、MST性質(zhì)：假設(shè)G={V,E}是一個(gè)連通圖，U是結(jié)點(diǎn)集合V的一個(gè)非空子集。若u屬于U,v屬于V-U，(u,v)是連接U和V-U一條代價(jià)最小的邊，則必存在一棵包括邊(u,v)在內(nèi)的最小代價(jià)生成樹。解釋：該圖頂點(diǎn)的集合V={v1,v2,v3,v4,v5,v6}，U={v1,v2,v3}是頂點(diǎn)集合V的一個(gè)子集

V-U={v4,v5,v6}。(v2,v5)=3是連接這兩個(gè)頂點(diǎn)集的邊中代價(jià)最小的,[(v2,v5)=3，(v3,v5)=6，(v3,v6)=4，(v3,v4)=5，(v1,v4)=5）]；則必然存在一棵包含邊(v2,v5)的最小生成樹。圖示列出的最小生成樹就包括這條邊。5v6v5v3v4v2v1651536642v6v5v3v4v2v1

153423、求最小生成樹的算法1）Prim算法

Prim算法的基本描述：

設(shè)G=(V，E)是連通網(wǎng)；

U是最小生成樹的頂點(diǎn)集，TE是最小生成樹的邊集。算法從U={u0}(u0∈V，是圖G的任意一個(gè)頂點(diǎn)),TE={}開始；重復(fù)執(zhí)行下述操作：

在連接U和V-U兩個(gè)頂點(diǎn)集的邊中找一條代價(jià)最小的邊，加入到TE中，同時(shí)這條邊在V-U中的頂點(diǎn)加入到U中。重復(fù)這個(gè)過程，直至U=V為止。

Prim算法的實(shí)例

5v6v5v3v4v2v1651536642v6v5v3v4v2v1

153422）Kruscal算法

算法的基本思想：假設(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)都在同一連通分量上為止。Kruscal算法實(shí)例5v6v5v3v4v2v1651536642v6v5v3v4v2v1

15342554、最小生成樹的應(yīng)用

要在6個(gè)城市濱州、濟(jì)南、淄博、萊蕪、濰坊、東營(yíng)之間建立通信網(wǎng)絡(luò)，要求任意兩個(gè)城市之間都能通信。兩個(gè)城市之間直接構(gòu)建通信線路的預(yù)估費(fèi)用如下所示（有些城市之間由于自然條件或其他原因不能直接構(gòu)建通信線路；）單位：百萬元濱州濟(jì)南6濱州淄博1濱州東營(yíng)5濟(jì)南淄博5濟(jì)南萊蕪3淄博萊蕪6淄博濰坊4淄博東營(yíng)5萊蕪濰坊6濰坊東營(yíng)2

請(qǐng)?jiān)O(shè)計(jì)一個(gè)合適的構(gòu)建方案，使得總費(fèi)用最低。解：第一步：把雜亂無章的數(shù)據(jù)轉(zhuǎn)化成有組織的數(shù)據(jù)（圖）（數(shù)據(jù)的邏輯結(jié)構(gòu)）

5濰坊萊蕪淄博東營(yíng)濟(jì)南濱州651536642第二步：如何在計(jì)算機(jī)中存儲(chǔ)這個(gè)圖？假設(shè)采用鄰接表（數(shù)據(jù)的物理結(jié)構(gòu)）第三步：在鄰接表這種存儲(chǔ)結(jié)構(gòu)下，編寫算法，求出此圖的最小生成樹。替代：手工求出此圖的最小生成樹。

濰坊萊蕪淄博東營(yíng)濟(jì)南濱州

153425濰坊萊蕪淄博東營(yíng)濟(jì)南濱州6515366427.5有向無環(huán)圖及其應(yīng)用1、有向無環(huán)圖（DAG圖）定義：一個(gè)無環(huán)的有向圖稱做有向無環(huán)圖（DirectedAcyclineGraph）。簡(jiǎn)稱DAG圖。BEFGLMNBEFGLMNBEFGLMN判斷下列三個(gè)圖是不是DAG圖（有向無環(huán)圖）？

2、

DAG圖用途：描述工程項(xiàng)目或系統(tǒng)進(jìn)行的工具.

計(jì)算機(jī)專業(yè)學(xué)生的學(xué)習(xí)就是一個(gè)工程,每一門課程的學(xué)習(xí)就是整個(gè)工程的一些活動(dòng)。其中有些課程要求先修課程有些則不要求。下表列出的一些課程的先修關(guān)系：

C1高等數(shù)學(xué)

C2

程序設(shè)計(jì)基礎(chǔ)

C3

離散數(shù)學(xué)C1,C2

C4

數(shù)據(jù)結(jié)構(gòu)C3,C2C5

高級(jí)語言程序設(shè)計(jì)C2C6

編譯方法C5,C4C7

操作系統(tǒng)C4,C9C8

普通物理C1C9

計(jì)算機(jī)原理C8

可以用下面的DAG圖來描述這個(gè)工程項(xiàng)目：

C2C1C3C4C5C8C9C7C6C1高等數(shù)學(xué)C2程序設(shè)計(jì)基礎(chǔ)C3離散數(shù)學(xué)C1,C2C4數(shù)據(jù)結(jié)構(gòu)C3,C2C5高級(jí)語言程序設(shè)計(jì)C2C6編譯方法C5,C4C7操作系統(tǒng)C4,C9C8普通物理C1C9計(jì)算機(jī)原理C8

在這種有向圖中，頂點(diǎn)表示活動(dòng)，有向邊表示活動(dòng)的優(yōu)先關(guān)系，這樣的有向圖叫做頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)(ActiveOnVertices)簡(jiǎn)稱為AOV網(wǎng)。7.5.1拓?fù)渑判驍?shù)學(xué)上的拓?fù)渑判?

由某個(gè)集合上的一個(gè)偏序關(guān)系得到該集合上的一個(gè)全序關(guān)系,這個(gè)操作過程叫拓?fù)渑判?。（不考慮）有向無環(huán)圖G（AOV網(wǎng)）的拓?fù)渑判颍菏菍中所有頂點(diǎn)排成一個(gè)線性序列,使得對(duì)圖中任意一對(duì)頂點(diǎn)u和v,若<u,v>∈E(G)，則u在線性序列中出現(xiàn)在v之前.C2C1C3C4C5C8C9C7C6拓?fù)渑判虻幕静襟E是:(1)從圖中選擇一個(gè)沒有前驅(qū)(即入度為0)的頂點(diǎn)并輸出它.(2)從圖中刪去該頂點(diǎn),并且刪去從該頂點(diǎn)發(fā)出的全部有向邊.隨著邊的刪除,又會(huì)有無前驅(qū)的頂點(diǎn)。(3)重復(fù)上述兩步,直到剩余的圖中不再存在沒有前驅(qū)的頂點(diǎn)為止.132756413246571327564練習(xí)：對(duì)下圖進(jìn)行拓?fù)渑判?。C2C1C3C4C5C8C9C7C67.5.2關(guān)鍵路徑1、AOE（ActivityOnEdge）網(wǎng)絡(luò)與AOV

網(wǎng)絡(luò)對(duì)應(yīng)的是AOE（ActivityOnEdge）網(wǎng)絡(luò)，AOE是一個(gè)帶權(quán)的有向無環(huán)圖。其中頂點(diǎn)表示事件，弧表示活動(dòng)，它的權(quán)值定義為活動(dòng)進(jìn)行所需要的時(shí)間。

源點(diǎn)：表示整個(gè)工程的開始點(diǎn)，也稱起點(diǎn)。

收點(diǎn)：表示整個(gè)工程的結(jié)束點(diǎn)，也稱匯點(diǎn)。對(duì)于AOE－網(wǎng)，有待研究的問題是：（1）完成整項(xiàng)工程至少需要多少時(shí)間？（2）哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵？由于在AOE－網(wǎng)中有些活動(dòng)可以并行地進(jìn)行，所以完成工程的最短時(shí)間是從開始點(diǎn)到完成點(diǎn)的最長(zhǎng)路徑的長(zhǎng)度（這里所說的路徑長(zhǎng)度是指路徑上各活動(dòng)持續(xù)時(shí)間之和，不是路徑上弧的數(shù)目）。路徑長(zhǎng)度最長(zhǎng)的路徑叫做關(guān)鍵路徑（CriticalPath）。關(guān)鍵路徑上的活動(dòng)就是影響工程進(jìn)度的關(guān)鍵。

關(guān)鍵路徑的求解步驟：

(1)求事件結(jié)點(diǎn)的最早發(fā)生時(shí)間Ve(Vj)）：從起點(diǎn)到本結(jié)點(diǎn)的最長(zhǎng)的路徑。意味著事件最早能夠發(fā)生的時(shí)刻。從Ve(V1)=0開始向前遞推：

Ve(Vj)=Max{Ve(Vi)+dut(<Vi,Vj>)}<Vi,Vj>屬于T，其中T是所有以第Vj個(gè)頂點(diǎn)為頭的弧的集合。

V1V3V2V5V6V41351122221關(guān)鍵路徑的求解步驟：

(1)求事件結(jié)點(diǎn)的最早發(fā)生時(shí)間Ve(Vj)）：從起點(diǎn)到本結(jié)點(diǎn)的最長(zhǎng)的路徑。意味著事件最早能夠發(fā)生的時(shí)刻。從Ve(V1)=0開始向前遞推：

Ve(Vj)=Max{Ve(Vi)+dut(<Vi,Vj>)}<Vi,Vj>屬于T，其中T是所有以第Vj個(gè)頂點(diǎn)為頭的弧的集合。

V1V3V2V5V6V41351102222113568

(2)求事件的最遲發(fā)生時(shí)間（Vl(Vj)）：不影響工程的如期完工，本結(jié)點(diǎn)事件必須發(fā)生的時(shí)刻。從最后一個(gè)事件Vl(Vn)=Ve(Vn)起向后遞推：

Vl(Vi)=Min{Vl(Vj)-dut(<Vi,Vj>)}<Vi,Vj>屬于S，i=n,…,0；其中S是所有以第i個(gè)頂點(diǎn)為尾的弧的集合。

V1V3V2V5V6V41351122221304568V1V3V2V5V6V4事件結(jié)點(diǎn)的最遲發(fā)生時(shí)間1351122221304568V1V3V2V5V6V4事件結(jié)點(diǎn)的最早發(fā)生時(shí)間1351102222113568V1V2V1V3V1V4V2V3V3V4V3V6V4V5V4V6V5V6V2V6弧最早開始時(shí)間最遲開始時(shí)間00011335562103446566（3）求活動(dòng)的最早開始時(shí)間：e(<Vi,Vj>)=Ve(Vi)

求活動(dòng)的最遲開始時(shí)間：l(<Vi,Vj>)=Vl(Vj)-dut(<Vi,Vj>)2V5V1V3V2V6V4135112221V1V2V1V3V1V4V2V3V3V4V3V6V4V5V4V6V5V6V2V6弧最早發(fā)生時(shí)間最遲發(fā)生時(shí)間00011335562103446566關(guān)鍵活動(dòng)關(guān)鍵活動(dòng)關(guān)鍵活動(dòng)

（4）最遲開始時(shí)間和最早開始時(shí)間相等的活動(dòng)是關(guān)鍵活動(dòng)。關(guān)鍵活動(dòng)組成的路徑就是關(guān)鍵路徑。作業(yè)：求下圖源點(diǎn)v1到匯點(diǎn)v9的關(guān)鍵路徑解：（1）各個(gè)事件的最早發(fā)生時(shí)間如下圖所示：016147754619（2）各個(gè)事件的最遲發(fā)生時(shí)間如下圖所示：0161571196619事件結(jié)點(diǎn)的最遲發(fā)生時(shí)間事件結(jié)點(diǎn)的最早發(fā)生時(shí)間V1V2V1V3V1V4V2V5V4V6V5V7V5V8V6V8V7V9V3V5弧最早開始時(shí)間最遲開始時(shí)間000645777161402466978111615（3）求活動(dòng)的最早開始時(shí)間：e(<Vi,Vj>)=Ve(Vi)

求活動(dòng)的最遲開始時(shí)間：l(<Vi,Vj>)=Vl(Vj)-dut(<Vi,Vj>)0161477546190161571196196V8V9V1V2V1V3V1V4V2V5V4V6V5V7V5V8V6V8V7V9V3V5弧最早開始時(shí)間最遲開始時(shí)間000645777161402466978111615（4）最遲開始時(shí)間和最早開始時(shí)間相等的活動(dòng)是關(guān)鍵活動(dòng)。關(guān)鍵活動(dòng)組成的路徑就是關(guān)鍵路徑。V8V97.6最短路徑問題的提出：一位旅客要從A城到B城他希望選擇一條途中距離最短的路線；他希望選擇一條途中所花時(shí)間最短的路線；他希望選擇一條途中費(fèi)用最小的路線；v5v4v3v2v1v0

1006030101020550這些問題均是帶權(quán)圖上的最短路徑問題。邊上的權(quán)表示距離邊上的權(quán)代表時(shí)間邊的權(quán)代表費(fèi)用

如何求最短路徑？設(shè)G是帶權(quán)(>=0)有向圖，給定一個(gè)頂點(diǎn)