數(shù)據(jù)結(jié)構(gòu)(CC++語言版)第六章new課件

第六章圖1.圖的基本概念2.圖的存儲結(jié)構(gòu)3.圖的遍歷4.最小生成樹5.最短路徑6.拓?fù)渑判?.關(guān)鍵路徑1第六章圖1.圖的基本概念1問題假設(shè)要在n個城市之間建立通信網(wǎng)。令圖G的頂點(diǎn)表示城市，邊表示連接兩個城市的通信線路，邊的權(quán)值表示通信線路的長度或代價。在n個城市間構(gòu)造通信網(wǎng)最少需要n-1條線路，問：如何選擇這n-1條邊，使得構(gòu)造這個通信網(wǎng)總的代價最小？2問題假設(shè)要在n個城市之間建立通信網(wǎng)。令圖G的頂點(diǎn)表示城市，邊1、熟悉圖的各種存儲結(jié)構(gòu)2、熟練掌握遍歷圖的算法3、應(yīng)用圖的遍歷算法求解各種簡單路徑問題學(xué)習(xí)要點(diǎn)：31、熟悉圖的各種存儲結(jié)構(gòu)學(xué)習(xí)要點(diǎn)：36.1圖的基本概念定義:

圖是由頂點(diǎn)集合(vertex)及邊的集合組成的一種數(shù)據(jù)結(jié)構(gòu)：

Graph＝(V,E)

其中

V={x|x

某個數(shù)據(jù)對象}

是頂點(diǎn)的有窮非空集合；

E={(x,y)|x,y

V}

是頂點(diǎn)之間關(guān)系的有窮集合，也叫做邊(edge)集合。例如:E={<A,B>,<C,D>,<A.D>,<B,C>}46.1圖的基本概念定義:圖是由頂點(diǎn)集合(vert

有向圖與無向圖若圖G中的每條邊都是有方向的，則稱G為有向圖。有向邊也稱為弧。若圖G中的每條邊都是沒有方向的，則稱G為無向圖。完全圖對有n個頂點(diǎn)的圖，若為無向圖且邊數(shù)為n(n-1)/2(?)，則稱其為無向完全圖；若為有向圖且邊數(shù)為n(n-1)(?)，則稱其為有向完全圖。

稠密圖、稀疏圖5有向圖與無向圖若圖G中的每條邊都是有方向的，則稱G為頂點(diǎn)的度一個頂點(diǎn)v的度是與它相關(guān)聯(lián)的邊的條數(shù)。記作TD(v)。頂點(diǎn)v的入度是以v為終點(diǎn)的有向邊的條數(shù),記作ID(v);頂點(diǎn)v

的出度是以v為始點(diǎn)的有向邊的條數(shù),記作OD(v)。

鄰接點(diǎn)：若（vi,vj）是一條無向邊，則稱頂點(diǎn)vi和vj互為鄰接點(diǎn)。1235687410796671231516ABDCE603045358040756頂點(diǎn)的度一個頂點(diǎn)v的度是與它相關(guān)聯(lián)的邊的條數(shù)。記作子圖

設(shè)有兩個圖G＝(V,E)和G‘＝(V’,E‘)。若V’V且E‘E,則稱圖G’是圖G的子圖。7子圖設(shè)有兩個圖G＝(V,E)和G‘＝(V’,E

路徑在圖G＝(V,E)中,若從頂點(diǎn)

vi出發(fā),沿一些邊經(jīng)過一些頂點(diǎn)

vp1,vp2,…,vpm，到達(dá)頂點(diǎn)vj。則稱頂點(diǎn)序列(vi

vp1vp2...vpm

vj)

為從頂點(diǎn)vi到頂點(diǎn)vj的路徑。它經(jīng)過的邊(vi,vp1)、(vp1,vp2)、...、(vpm,vj)應(yīng)是屬于E的邊。簡單路徑若路徑上各頂點(diǎn)v1,v2,...,vm均不互相重復(fù),則稱這樣的路徑為簡單路徑。回路若路徑上第一個頂點(diǎn)v1與最后一個頂點(diǎn)vm重合,則稱這樣的路徑為回路或環(huán)。路徑長度非帶權(quán)圖的路徑長度是指此路徑上邊的條數(shù)。帶權(quán)圖的路徑長度是指路徑上各邊的權(quán)之和。8路徑在圖G＝(V,E)中,若從頂點(diǎn)v圖的連通在無向圖G中，若兩個頂點(diǎn)vi和vj之間有路徑存在，則稱vi和vj是連通的。若G中任意兩個頂點(diǎn)都是連通的，則稱G為連通圖。非連通圖的極大連通子圖叫做連通分量。

強(qiáng)連通圖與強(qiáng)連通分量在有向圖中,若對于每一對頂點(diǎn)vi和vj,都存在一條從vi到vj和從vj到vi的路徑,則稱此圖是強(qiáng)連通圖。非強(qiáng)連通圖的極大強(qiáng)連通子圖叫做強(qiáng)連通分量。9圖的連通在無向圖G中，若兩個頂點(diǎn)vi和vj之間有強(qiáng)連通圖與1235687410796671231516ABDCE60304535804075權(quán)：某些圖的邊具有與它相關(guān)的數(shù),稱之為權(quán)。這種帶權(quán)圖叫做網(wǎng)。101235687410796671231516ABDCE603

生成樹一個連通圖的生成樹是它的極小連通子圖，在n個頂點(diǎn)的情形下，有n-1條邊。生成森林不予討論的圖包含頂點(diǎn)到其自身的邊；一條邊在圖中重復(fù)出現(xiàn)11生成樹一個連通圖的生成樹是它的極小不予討論的圖6.2圖的存儲結(jié)構(gòu)基本思想：圖需要存儲的信息：頂點(diǎn)和弧。引入兩個數(shù)組，一個記錄各個頂點(diǎn)信息的頂點(diǎn)表，還有一個表示各個頂點(diǎn)之間關(guān)系的鄰接矩陣。設(shè)圖A=(V,E)是一個有n個頂點(diǎn)的圖，則圖的鄰接矩陣是一個二維數(shù)組A.arcs[n][n]，定義：一.圖的數(shù)組表示法(鄰接矩陣表示法)1 若<vi,vj>或(vi,vj)E0 反之a(chǎn)rcs[i][j]=126.2圖的存儲結(jié)構(gòu)基本思想：一.圖的數(shù)組表示法(21435鄰接矩陣頂點(diǎn)矩陣1321435鄰接矩陣13BADCE鄰接矩陣頂點(diǎn)矩陣14BADCE鄰接矩陣14若G是帶權(quán)的圖,則鄰接矩陣定義為:

Wi,j 若<vi,vj>或(vi,vj)E0或∞ 反之A[i][j]=∞59∞∞

∞∞∞

∞

∞∞74∞∞∞G1.arcs=V1V2V3V4有向圖G15497有向網(wǎng)G1的鄰接矩陣為：15若G是帶權(quán)的圖,則鄰接矩陣定義為:Wi,j 若<vi,215346203050407080帶權(quán)圖的鄰接矩陣16215346203050407080帶權(quán)圖的鄰接矩陣16鄰接矩陣的特點(diǎn)：

無向圖的鄰接矩陣一定是一個對稱矩陣。無向圖的鄰接矩陣的第i行(或第i列)非零元素個數(shù)為第i個頂點(diǎn)的度D(vi)。有向圖的鄰接矩陣的第i行非∞元素個數(shù)為第i個頂點(diǎn)的出度OD(vi)，第i列非∞元素個數(shù)就是第i個頂點(diǎn)的入度ID(vi)。鄰接矩陣表示圖，很容易確定圖中任意兩個頂點(diǎn)之間是否有邊相連。容易判斷兩個頂點(diǎn)之間是否有長度為m的路徑相連。17鄰接矩陣的特點(diǎn)：17鄰接矩陣的實(shí)現(xiàn)(class定義)——C++：template<classT>classMGraph{public:MGraph(Ta[],intn,inte);MGraph();~MGraph(){};voiddfs(intv);voidbfs(intv);private:Tvertex[Maxsize];intarc[Maxsize][Maxsize];

intvertexnum,arcnum;}18鄰接矩陣的實(shí)現(xiàn)(class定義)——C++：18鄰接矩陣的構(gòu)造函數(shù)方法一:(無向圖)template<classT>MGraph::MGraph(Ta[],intn,inte){vertexnum=n,arcnum=e;for(i=0;i<vertexnum;i++)vertex[i]=a[i];for(i=0;i<vertexnum;i++)for(j=0;j<vertexnum;j++)arc[i][j]=0;for(k=0;k<arcnum;k++){cin>>i>>j;arc[i][j]=1;arc[j][i]=1;}}19鄰接矩陣的構(gòu)造函數(shù)方法一:(無向圖)for(k=0;k<鄰接矩陣的構(gòu)造函數(shù)方法二:(無向圖)template<classT>MGraph::MGraph(){cin>>vexnum>>arcnum;for(i=0;i<G.vexnum;i++)cin>>vertex[i];for(i=0;i<vexnum;i++)for(j=0;j<vexnum;j++)arc[i][j]＝0;for(k=0;k<arcnum;k++){cin>>vi>>vj;i=search(vertex,vi);j=search(vertex,vj);arc[i][j]=1;arc[j][i]=1;}}20鄰接矩陣的構(gòu)造函數(shù)方法二:(無向圖)for(k=0;k<StatusCreateGraph(Mgraph&G){ inti，j; AdjTypew; VexTypev1,v2; //輸入頂點(diǎn)數(shù)、邊數(shù)和是否輸入邊的相關(guān)信息的標(biāo)志 scanf(“%d%d”,&G.vexnum,&G.arcnum); for(i=0;i<G.vexnum;i++) //讀入所有的頂點(diǎn) scanf(“%c”,&G.vexs[i]); for(i=0;i<G.vexnum;i++) //初始化鄰接矩陣 for(j=0;j<G.vexnum;j++)pG->arcs[i][j]=INFINITY; for(i=0;i<G.arcnum;i++){ //輸入所有的邊 //輸入一條邊依附的兩個頂點(diǎn)和邊上的權(quán)值 scanf(“%c%c%f”,&v1,&v2,&w); //查詢兩個頂點(diǎn)在圖中存儲的位置 i=LocateVex(pG,v1); j=LocateVex(pG,v2);創(chuàng)建無向網(wǎng)的算法：21創(chuàng)建無向網(wǎng)的算法：21 pG->arcs[i][j].adj=w; pG->arcs[j][i]=pG.arcs[i][j]; } returnOK;}//查找某個頂點(diǎn)在圖中的存儲位置（下標(biāo)），找不到返回-1intLocateVex(Mgraph&G,VexTypevert){inti;for(i=0;i<G.vexnum;i++)if(pG->vexs[i]==vert)returni;return-1;}22 pG->arcs[i][j].adj=w;//查找鄰接矩陣表示法的缺點(diǎn)：鄰接矩陣占用的存儲單元個數(shù)只與圖中的結(jié)點(diǎn)個數(shù)有關(guān)，而與邊的數(shù)目無關(guān)。一個n個結(jié)點(diǎn)的圖，若其邊數(shù)比n2少得多，那么鄰接矩陣中會存在大量的無用單元。23鄰接矩陣表示法的缺點(diǎn)：23基本思想：如果對圖中的所有頂點(diǎn)都建立一個單鏈表（邊表）來存儲所有依附于該頂點(diǎn)的弧或邊，就可以把圖中所有已有的弧或邊的信息保存下來。對于圖中所有頂點(diǎn)還是使用一個一維數(shù)組來存放。在鄰接表表示法中，對于頂點(diǎn)單元i，需要存放的內(nèi)容有頂點(diǎn)信息以及指向依附于該頂點(diǎn)的所有的弧或邊組成的單鏈表（邊表）。對于邊表中弧單元，需要存放該弧指向的頂點(diǎn)的位置（也就是該弧依附的另一個頂點(diǎn)的位置）和指向下一條弧的指針。二.鄰接表(AdjacencyList)24基本思想：二.鄰接表(AdjacencyList)無向圖的鄰接表

把同一個頂點(diǎn)發(fā)出的邊鏈接在同一個邊鏈表中，鏈表的每一個結(jié)點(diǎn)代表一條邊，叫做邊結(jié)點(diǎn)，結(jié)點(diǎn)中保存有與該邊相關(guān)聯(lián)的另一頂點(diǎn)的頂點(diǎn)下標(biāo)dest

和指向同一鏈表中下一個邊結(jié)點(diǎn)的指針link。25無向圖的鄰接表25有向圖的鄰接表和逆鄰接表在有向圖的鄰接表中，第i個邊鏈表鏈接的邊都是頂點(diǎn)i

發(fā)出的邊。也叫做出邊表。在有向圖的逆鄰接表中，第i個邊鏈表鏈接的邊都是進(jìn)入頂點(diǎn)

i的邊。也叫做入邊表。26有向圖的鄰接表和逆鄰接表26帶權(quán)圖的邊結(jié)點(diǎn)中保存該邊上的權(quán)值cost。頂點(diǎn)i

的邊鏈表的表頭指針

adj

在頂點(diǎn)表的下標(biāo)為i的頂點(diǎn)記錄中，該記錄還保存了該頂點(diǎn)的其它信息。在鄰接表的邊鏈表中，各個邊結(jié)點(diǎn)的鏈入順序任意，視邊結(jié)點(diǎn)輸入次序而定。設(shè)圖中有n個頂點(diǎn)，e條邊，則用鄰接表表示無向圖時，需要n個頂點(diǎn)結(jié)點(diǎn)，2e個邊結(jié)點(diǎn)；用鄰接表表示有向圖時，若不考慮逆鄰接表，只需n個頂點(diǎn)結(jié)點(diǎn)，e個邊結(jié)點(diǎn)。27帶權(quán)圖的邊結(jié)點(diǎn)中保存該邊上的權(quán)值cost。27網(wǎng)(帶權(quán)圖)的鄰接表28網(wǎng)(帶權(quán)圖)的鄰接表28鄰接表中的結(jié)點(diǎn)類型定義：structArcNode{intadjvex;ArcNode*next;}template<classT>structVertexNode{Tvertex;ArcNode*firstedge;}29鄰接表中的結(jié)點(diǎn)類型定義：29鄰接表的實(shí)現(xiàn)(class定義)：template<classT>classALGraph{public:ALGgraph(Ta[],intn,inte);ALGraph();~ALGraph(){};voiddfs(intv);voidbfs(intv);private:VertexNodeadjlist[Maxsize];

intvertexnum,arcnum;}30鄰接表的實(shí)現(xiàn)(class定義)：30

鄰接表的構(gòu)造函數(shù)(方法一)：

ALGraph::ALGgraph(Ta[],intn,inte);{vexnum=n;arcnum=e;for(i=0;i<vexnum;i++){adjlist[i].vertex=a[i];adjlist[i].firstedge＝NULL;}for(k=0;k<arcnum;k++){cin>>i>>j;s＝newArcNode;s->adjvex＝j(luò);s->next＝adjlist[i].firstedge;adjlist[i].firstedge＝s;}}31鄰接表的構(gòu)造函數(shù)(方法一)：31

鄰接表的構(gòu)造函數(shù)(方法二)：

ALGraph::ALGraph(){cin>>vexnum>>arcnum;for(i=0;i<vexnum;i++){cin>>adjlist[i].vertex;adjlist[i].firstedge＝NULL;}for(k=0;k<arcnum;k++){cin>>vi>>vj;i=search(adjlist,vi);j=search(adjlist,vj);s＝newArcNode;s->adjvex＝j(luò);s->next＝adjlist[i].firstedge;adjlist[i].firstedge＝s;}}32鄰接表的構(gòu)造函數(shù)(方法二)：32

優(yōu)點(diǎn)：

在邊稀疏的情況下，節(jié)省存儲空間易于確定圖中任一頂點(diǎn)的度數(shù)和它的所有鄰接點(diǎn)。缺點(diǎn)：

判定任意兩個頂點(diǎn)之間是否有邊或弧不方便。鄰接表的優(yōu)缺點(diǎn)：33鄰接表的優(yōu)缺點(diǎn)：33給出其鄰接矩陣和鄰接表表示。請畫出：

（1）以a為起點(diǎn)的一棵深度優(yōu)先生成樹和廣度優(yōu)先生成樹。

（2）以d為起點(diǎn)的一棵深度優(yōu)先生成樹和廣度優(yōu)先生成樹。34給出其鄰接矩陣和鄰接表表示。346.3圖的遍歷概念從圖中某一頂點(diǎn)出發(fā)，沿著某條搜索路徑訪問圖中所有的頂點(diǎn)，且使每個頂點(diǎn)僅被訪問一次，就叫做圖的遍歷。復(fù)雜性圖的任一頂點(diǎn)都可能與其它頂點(diǎn)相通，即圖中可能存在回路，在訪問完某個頂點(diǎn)之后可能會沿著某些邊又回到了曾經(jīng)訪問過的頂點(diǎn)。為了避免重復(fù)訪問，需設(shè)置一個標(biāo)志頂點(diǎn)是否被訪問過的輔助數(shù)組visited[]，它的初始狀態(tài)為0，在圖的遍歷過程中，一旦某一個頂點(diǎn)i

被訪問，就立即讓visited[i]為1，防止它被多次訪問。356.3圖的遍歷概念35

類似于樹的先根遍歷，是樹的先根遍歷的推廣。圖的深度優(yōu)先遍歷規(guī)則：假設(shè)初始狀態(tài)是圖中所有頂點(diǎn)都未被訪問，則可從圖中某個頂點(diǎn)v出發(fā)，訪問此頂點(diǎn)，然后依次從v的未被訪問的鄰接點(diǎn)出發(fā)深度優(yōu)先遍歷圖，直至所有與v有通路的頂點(diǎn)都被訪問到；若此時圖中還有頂點(diǎn)未被訪問到，則另選圖中未被訪問的頂點(diǎn)作起點(diǎn)，重復(fù)上述過程，直到圖中所有頂點(diǎn)都被訪問到為止。V1V2V3V4V5V8V6V7深度優(yōu)先搜索(DFS:

DepthFirstSearch)36類似于樹的先根遍歷，是樹的先根遍歷的推廣。V1V2V3V深度優(yōu)先搜索的示例37深度優(yōu)先搜索的示例37voidDFS(MGraphG,inti){intj;VisitFunc(G.vexs[v]);//訪問第v個頂點(diǎn)visited[i]=TRUE;//設(shè)置訪問標(biāo)志為TRUE(已訪問)for(j=0;j<G.vexnum;j++)if(G.arcs[i][j]==1&&!visited[j])DFS(G,j);}圖的深度優(yōu)先搜索算法：Booleanvisited[MAX];Status(*VisitFunc)(intv);以鄰接矩陣表示法作為圖的存儲結(jié)構(gòu)連通圖：38voidDFS(MGraphG,inti){圖非連通圖：voidDFSTraverse(MGraphG,Status(*Visit)(VertexType)){intv;VisitFunc=Visit;for(v=0;v<G.vexnum;v++)visited[v]=FALSE;//訪問標(biāo)志數(shù)組初始化(未被訪問)for(v=0;v<G.vexnum;v++)if(!visited[v])DFS(G,v);//對尚未訪問的頂點(diǎn)調(diào)用DFS}問題：如何判斷一個圖是否是連通的？如何求出一個非連通圖中的連通分量個數(shù)？39非連通圖：voidDFSTraverse(MGraph例子遍歷結(jié)果：A、C、B、D40例子遍歷結(jié)果：A、C、B、D40算法分析：設(shè)圖中有n個頂點(diǎn)，e條邊。如果用鄰接矩陣表示圖，查找每一個頂點(diǎn)的所有的邊，所需時間為O(n)，則遍歷圖中所有的頂點(diǎn)所需的時間為O(n2)。如果用鄰接表表示圖，沿firstarcnextarc

鏈可以找到某個頂點(diǎn)v的所有鄰接頂點(diǎn)w。由于總共有2e個邊結(jié)點(diǎn)，所以掃描邊的時間為O(e)。而且對所有頂點(diǎn)遞歸訪問1次，所以遍歷圖的時間復(fù)雜性為O(n+e)。41算法分析：設(shè)圖中有n個頂點(diǎn)，e條邊。41類似于樹的層次遍歷。假設(shè)從圖中某個頂點(diǎn)v出發(fā)，在訪問了v之后，依次訪問v的各個未曾訪問過的鄰接點(diǎn)，并保證“先被訪問的頂點(diǎn)的鄰接點(diǎn)”要先于“后被訪問的頂點(diǎn)的鄰接點(diǎn)”被訪問。直至圖中所有已被訪問的頂點(diǎn)的鄰接點(diǎn)都被訪問到。若此時圖中還有未被訪問的頂點(diǎn)，則任選其中之一作為起點(diǎn)，重新開始上述過程，直至圖中所有頂點(diǎn)都被訪問到。對于廣度優(yōu)先遍歷：其關(guān)鍵之處在于怎么保證“先被訪問的頂點(diǎn)的鄰接點(diǎn)”要先于“后被訪問的頂點(diǎn)的鄰接點(diǎn)”被訪問，也就是先到先被訪問。廣度優(yōu)先搜索(BFS:BreadthFirstSearch)42廣度優(yōu)先搜索(BFS:BreadthFirstSea廣度優(yōu)先搜索的示例

廣度優(yōu)先搜索過程 廣度優(yōu)先生成樹43廣度優(yōu)先搜索的示例廣度優(yōu)先搜索過程 廣使用廣度優(yōu)先搜索在訪問了起始頂點(diǎn)v之后，由v出發(fā)，依次訪問v的各個未曾被訪問過的鄰接頂點(diǎn)w1,w2,…,wt，然后再順序訪問w1,w2,…,wt的所有還未被訪問過的鄰接頂點(diǎn)。再從這些訪問過的頂點(diǎn)出發(fā)，再訪問它們的所有還未被訪問過的鄰接頂點(diǎn)，…如此做下去，直到圖中所有頂點(diǎn)都被訪問到為止。廣度優(yōu)先搜索是一種分層的搜索過程，每向前走一步可能訪問一批頂點(diǎn)，不像深度優(yōu)先搜索那樣有往回退的情況。因此，廣度優(yōu)先搜索不是一個遞歸的過程，其算法也不是遞歸的。為了實(shí)現(xiàn)逐層訪問，算法中使用了一個隊(duì)列，以記憶正在訪問的這一層和上一層的頂點(diǎn)，以便于向下一層訪問。與深度優(yōu)先搜索過程一樣，為避免重復(fù)訪問，需要一個輔助數(shù)組visited[]，給被訪問過的頂點(diǎn)加標(biāo)記。44使用廣度優(yōu)先搜索在訪問了起始頂點(diǎn)v之后，由v出發(fā)，依voidBFSTraverse(MGraphG,Status(*Visit)(VertexType)){intv,j;LinkQueueQ;InitQueue(Q);//置空的輔助隊(duì)列Qfor(v=0;v<G.vexnum;v++)visited[v]=FALSE;//置初值for(v=0;v<G.vexnum;v++)if(!visited[v]){visited[v]=TRUE;//設(shè)置訪問標(biāo)志為TRUE(已訪問)Visit(G.vexs[v]);EnQueue(Q,v);//v入隊(duì)列while(!QueueEmpty(Q)){DeQueue(Q,u);//隊(duì)頭元素出隊(duì)并置為u

廣度優(yōu)先遍歷算法（鄰接矩陣表示法）：45voidBFSTraverse(MGraphG,Stafor(j=0;j<G.vexnum;j++)if(G.arcs[i][j]==1&&!visited[j]){visited[j]=TRUE;Visit(G.vexs[j]);EnQueue(Q,j);}}}}46for(j=0;例子遍歷結(jié)果：A、B、C、D47例子遍歷結(jié)果：A、B、C、D476.4圖的連通性利用遍歷判斷一個圖是否是連通圖?1.無向圖的連通性count=0;for(圖中每個頂點(diǎn)v)if(v未被訪問過){count++;從v出發(fā)遍歷該圖;}if(count==1)cout<<“連通的”elsecout<<“有count個連通分量”;486.4圖的連通性利用遍歷判斷一個圖是否是連通圖?482.有向圖的連通性

要利用深度優(yōu)先搜索dfs判斷count=0;for(圖中每個頂點(diǎn)v)if(v未被訪問過){count++;從v出發(fā)dfs遍歷該圖;記下被訪問的頂點(diǎn)序列;}if(count>1)cout<<“不連通”;else{從最后被訪問的頂點(diǎn)出發(fā)逆向dfs;if(全被訪問到)則是連通的;else該圖不連通.}492.有向圖的連通性49

生成樹的定義:n個頂點(diǎn)的連通網(wǎng)絡(luò)的生成樹有n個頂點(diǎn)、n-1條邊。生成樹是連通圖的極小連通子圖。問題：對于給定的連通網(wǎng)絡(luò)，如何求得其生成樹？

對含有n個頂點(diǎn)的連通圖G，從任一頂點(diǎn)出發(fā)，作一次深度優(yōu)先或廣度優(yōu)先遍歷，將遍歷過程中經(jīng)過的n-1條邊和圖中的n個頂點(diǎn)連接起來構(gòu)成一個極小連通子圖，就是圖G的一棵生成樹。用不同的遍歷圖的方法，可以得到不同的生成樹；從不同的頂點(diǎn)出發(fā)，也可能得到不同的生成樹。6.5最小生成樹

(minimumcostspanningtree)50生成樹的定義:n個頂點(diǎn)的連通網(wǎng)絡(luò)的生成樹有n個頂點(diǎn)最小生成樹

生成樹各邊的權(quán)值總和稱為生成樹的權(quán)。權(quán)最小的生成樹稱為最小生成樹。最小生成樹的應(yīng)用實(shí)例：假設(shè)要在n個城市之間建立通信網(wǎng)。令圖G的頂點(diǎn)表示城市，邊表示連接兩個城市的通信線路，邊的權(quán)值表示通信線路的長度或代價。在n個城市間構(gòu)造通信網(wǎng)最少需要n-1條線路，問：如何選擇這n-1條邊，使得構(gòu)造這個通信網(wǎng)總的代價最?。?/p>

構(gòu)造最小生成樹的準(zhǔn)則：必須只使用該網(wǎng)絡(luò)中的邊來構(gòu)造最小生成樹；必須使用且僅使用n-1條邊來聯(lián)結(jié)網(wǎng)絡(luò)中的n個頂點(diǎn)；不能使用產(chǎn)生回路的邊。51最小生成樹生成樹各邊的權(quán)值總和稱為生成樹的權(quán)。51MST性質(zhì)：

設(shè)G=（V，E）是一個連通網(wǎng)絡(luò)，U是頂點(diǎn)集V的一個真子集。若（u，v）是G中所有的一個頂點(diǎn)在U，另一個頂點(diǎn)不在U的邊中，具有最小權(quán)值的一條邊，則一定存在G的一棵最小生成樹包括此邊。uvUV—U最小生成樹的構(gòu)造算法：52MST性質(zhì)：uvUV—U最小生成樹的構(gòu)造算法：52證明（反證法）：假設(shè)G中任何一棵最小生成樹都不包含(u，v)。設(shè)T是一棵最小生成樹但不包含(u，v)。由于T是最小生成樹，所以T是連通的，因此有一條從u到v的路徑，且該路徑上必有一條連接兩個頂點(diǎn)集U、V-U的邊(u',v')，其中u'∈U，v'∈V-U。當(dāng)把邊

(u，v)加入到T中后，得到一個含有邊(u，v)的回路。刪除邊(u',v')，上述回路即被消除。由此得到另一棵生成樹T'，T和T'的區(qū)別僅在于用邊(u，v)代替了(u',v')。由于(u，v)的權(quán)<=(u',v')的權(quán)，所以，T'的權(quán)<=T的權(quán)，與假設(shè)矛盾。53證明（反證法）：53普里姆(Prim)算法:基本思想：從連通網(wǎng)絡(luò)N={V,E}中的某一頂點(diǎn)u0

出發(fā)，選擇與它關(guān)聯(lián)的具有最小權(quán)值的邊(u0,v)，將其頂點(diǎn)加入到生成樹的頂點(diǎn)集合U中。以后每一步從一個頂點(diǎn)在U中，而另一個頂點(diǎn)不在U中的各條邊中選擇權(quán)值最小的邊(u,v),把它的頂點(diǎn)加入到集合U中。如此繼續(xù)下去，直到網(wǎng)絡(luò)中的所有頂點(diǎn)都加入到生成樹頂點(diǎn)集合U中為止。54普里姆(Prim)算法:基本思想：54在構(gòu)造過程中，需引入一個輔助數(shù)組：

closedge[]用于存放生成樹外各頂點(diǎn)(V－Ｕ中各頂點(diǎn))到生成樹頂點(diǎn)集合內(nèi)頂點(diǎn)(Ｕ中各頂點(diǎn))的各邊的當(dāng)前最小權(quán)值；

struct{VertexTypeadjvex;VRTypelowcost;

}closedge[MAX_VERTEX_NUM];

對于每個頂點(diǎn)vi∈V-U,在數(shù)組closedge對應(yīng)一個相應(yīng)分量closedge[i-1]。其中：closedge[i-1].lowcost=Min{cost(vi,u)|u∈U}55在構(gòu)造過程中，需引入一個輔助數(shù)組：struct{55用普里姆算法構(gòu)造最小生成樹的過程12346556517325461234655132456用普里姆算法構(gòu)造最小生成樹的過程12346556517325從連通網(wǎng)絡(luò)N={V,E}中的選擇任一頂點(diǎn)u0

加入到生成樹Ｔ的頂點(diǎn)集合Ｕ中，并為集合

V－Ｕ中的各頂點(diǎn)置最小權(quán)值邊．while(生成樹T中頂點(diǎn)數(shù)目<n){

從集合V－Ｕ中各頂點(diǎn)對應(yīng)的最小權(quán)值邊中選取最短邊(u,v);將邊(u,v)及其在集合V－Ｕ中的頂點(diǎn)v，加到生成樹T中；調(diào)整集合V－Ｕ中各頂點(diǎn)對應(yīng)的最小權(quán)值邊；}Prim算法框架描述如下：57從連通網(wǎng)絡(luò)N={V,E}中的選擇任一頂點(diǎn)u0加入到voidMiniSpanTree_PRIM(MGraphG,VertexTypeu){inti,j,k;minsideclosedge;k=LocateVex(G,u);for(j=0;j<G.vexnum;++j){//輔助數(shù)組初始化if(j!=k){closedge[j].adjvex=u;closedge[j].lowcost=G.arcs[k][j].adj;}}closedge[k].lowcost=0;//U={u}

普里姆算法（鄰接矩陣表示法）：58voidMiniSpanTree_PRIM(MGraphfor(i=1;i<G.vexnum;++i){k=minimum(closedge);//求出T的下一個結(jié)點(diǎn)printf(closedge[k].adjvex,G.vexs[k]);//輸出生成樹的邊closedge[k].lowcost=0;//第K頂點(diǎn)并入U集for(j=0;j<G.vexnum;++j)if(G.arcs[k][j].adj<closedge[j].lowcost)closedge[j].lowcost=G.arcs[k][j].adj;}}59for(i=1;i<G.vexnum;++i){59克魯斯卡爾(Kruskal)算法基本思想：設(shè)有一個有n個頂點(diǎn)的連通網(wǎng)絡(luò)N={V,E},最初先構(gòu)造一個只有n個頂點(diǎn)，沒有邊的非連通圖T={V,},圖中每個頂點(diǎn)自成一個連通分量。當(dāng)在E中選到一條具有最小權(quán)值的邊時,若該邊的兩個頂點(diǎn)落在不同的連通分量上，則將此邊加入到T中；否則將此邊舍去，重新選擇一條權(quán)值最小的邊。如此重復(fù)下去，直到所有頂點(diǎn)在同一個連通分量上為止。60克魯斯卡爾(Kruskal)算法基本思想：60用克魯斯卡爾算法構(gòu)造最小生成樹的過程12346556517325461234655132461用克魯斯卡爾算法構(gòu)造最小生成樹的過程123465565173克魯斯卡爾算法的基本思想T=(V,φ)；While(T中所含邊數(shù)<n-1){從E中選取當(dāng)前最短邊(u,v);從E中刪除邊(u,v);if((u,v)并入T之后不產(chǎn)生回路)將邊(u,v)并入T中；}62克魯斯卡爾算法的基本思想623.Prim與Kruskal算法的性能比較:

(1)時間復(fù)雜性:Prim:O(n*n)Kruskal:O(eloge)(2)適用場合:Prim:稠密圖Kruskal:稀疏圖

633.Prim與Kruskal算法的性能比較:636.6最短路徑(ShortestPath)問題的提出：

假如要在計算機(jī)上建立一個交通咨詢系統(tǒng)，可用圖或網(wǎng)的結(jié)構(gòu)來表示實(shí)際的交通網(wǎng)絡(luò)，用頂點(diǎn)表示城市，邊表示城市之間的交通聯(lián)系。這個交通咨詢系統(tǒng)可以回答旅客提出的各種問題。如：一位旅客想從A城到B城，希望選擇中轉(zhuǎn)次數(shù)最少的路線。一位司機(jī)想選擇一條從A城到B城所需時間最少的路徑？

最短路徑問題：

如果從圖中某一頂點(diǎn)(稱為源點(diǎn))到達(dá)另一頂點(diǎn)(稱為終點(diǎn))的路徑可能不止一條，如何找到一條路徑使得沿此路徑上各邊上的權(quán)值總和達(dá)到最小。646.6最短路徑(ShortestPath)問題的提出求解算法：

邊上權(quán)值非負(fù)情形的單源最短路徑問題—

Dijkstra算法所有頂點(diǎn)之間的最短路徑—Floyd算法6565單源最短路徑問題(Dijkstra算法)問題的提法：給定一個帶權(quán)有向圖G與源點(diǎn)v，求從v到G中其它頂點(diǎn)的最短路徑。限定各邊上的權(quán)值大于或等于0。66單源最短路徑問題(Dijkstra算法)問題的提法：給定一從頂點(diǎn)v0到其余各頂點(diǎn)的最短路徑67從頂點(diǎn)v0到其余各頂點(diǎn)的最短路徑67為求得這些最短路徑，Dijkstra提出按路徑長度的遞增次序，逐步產(chǎn)生最短路徑的算法：

假設(shè)從源點(diǎn)v0到各終點(diǎn)v1，v2，…,vk間存在最短路徑，其路徑長度分別為：l1,l2,…,lk，并且lp為其中的最小值。即從源點(diǎn)v0到終點(diǎn)vp的路徑最短。顯然這條路徑上只有一條弧，否則它就不可能是所有最短路徑中長度最短者。第二條長度次短的（設(shè)從源點(diǎn)v0到終點(diǎn)vq）最短路徑只可能產(chǎn)生于下列兩種情況：一是從源點(diǎn)到該點(diǎn)有弧<v0,vq>存在；另一是從已求得最短路徑的點(diǎn)vp到該點(diǎn)有弧<vp,vq>存在，且弧<v0,vp>和<vp,vq>上的權(quán)值之和小于弧<v0,vq>的權(quán)值。

類推到一般情況：假設(shè)已求得最短路徑的的頂點(diǎn)集合S為{vp1,vp2,…,vpk}，則下一條最短路徑（設(shè)終點(diǎn)為x）或者為弧<v0,x>，或者為一條只經(jīng)過S中的頂點(diǎn)而最后到達(dá)終點(diǎn)x的路徑。68為求得這些最短路徑，Dijkstra提出按路徑長度的遞增次Dijkstra算法的實(shí)現(xiàn):

設(shè)置并逐步擴(kuò)充一個集合S，存放已求出的最短路徑的頂點(diǎn)，則尚未確定最短路徑的頂點(diǎn)集合是V-S。

引入一個輔助數(shù)組D[]。它的每一個分量D[i]表示當(dāng)前確定到的從源點(diǎn)v0到終點(diǎn)vi的最短路徑的長度（最短距離）。初始狀態(tài)：若從源點(diǎn)v0到頂點(diǎn)vi有邊，則D[i]為該邊上的權(quán)值；若從源點(diǎn)v0到頂點(diǎn)vi沒有邊，則D[i]為+。69Dijkstra算法的實(shí)現(xiàn):69（1）假設(shè)用鄰接矩陣來表示帶權(quán)有向圖，arc[i][j]表示

弧(vi,vj)上的權(quán)值。若(vi,vj)不存在，則置arc[i][j]為計算機(jī)上允許的最大值。S為已找到的從v出發(fā)的最短路徑的終點(diǎn)集合，其初始狀態(tài)為僅含源點(diǎn)。那么從v出發(fā)到圖上其余各頂點(diǎn)vi可能達(dá)到的最短路徑長度的初值為：

D[i]=arcs[LocateVex(G,v)][i]viV（2）選擇vj,使得 D[j]=Min{D[i]|vi

V-S}vj就是當(dāng)前求得的一條從v出發(fā)的最短路徑的終點(diǎn)。令 S＝S{j}（3）修改從v出發(fā)到集合V－S中的任一頂點(diǎn)vk可達(dá)的最短路徑長度。如果：

D[j]+arcs[j][k]<D[k]

則修改D[k]為

D[k]＝D[j]+arcs[j][k]Dijkstra算法具體描述：70（1）假設(shè)用鄰接矩陣來表示帶權(quán)有向圖，arc[i][j]表示voidShortestPath_DIJ(MGraphG,intv0,PathMatrix&P,

ShortPathTable&D){intv,w,i,j,min;Statusfinal[MAX_VERTEX_NUM];for(v=0;v<G.vexnum;++v){final[v]=FALSE;D[v]=G.arcs[v0][v].adj;for(w=0;w<G.vexnum;++w)P[v][w]=FALSE;//設(shè)空路徑if(D[v]<INFINITY){P[v][v0]=TRUE;P[v][v]=TRUE;}}D[v0]=0;final[v0]=TRUE;//將v0頂點(diǎn)加入S集for(i=1;i<G.vexnum;++i){min=INFINITY;//當(dāng)前所知離v0頂點(diǎn)的最近距離

71voidShortestPath_DIJ(MGraphGfor(w=0;w<G.vexnum;++w)if(!final[w])//w頂點(diǎn)在V-S中if(D[w]<min){v=w;min=D[w];}//w頂點(diǎn)離v0頂點(diǎn)更近final[v]=TRUE;//離v0頂點(diǎn)最近的v加入S集for(w=0;w<G.vexnum;++w){//更新當(dāng)前最短路徑及距離if(!final[w]&&(min+G.arcs[v][w].adj<D[w])){D[w]=min+G.arcs[v][w].adj;for(j=0;j<G.vexnum;++j)P[w][j]=P[v][j];P[w][w]=TRUE;}}}}72for(w=0;w<G.vexn所有頂點(diǎn)之間的最短路徑問題的提法：已知一個各邊權(quán)值均大于0的帶權(quán)有向圖，對每一對頂點(diǎn)vi

vj，要求求出vi

與vj之間的最短路徑和最短路徑長度。兩種解決方法：可以依次把有向網(wǎng)絡(luò)中的每個頂點(diǎn)作為源點(diǎn)，重復(fù)執(zhí)行DIJKSTRA算法n次，即可求出每對頂點(diǎn)之間的最短路徑。弗洛伊德（Floyd）算法73所有頂點(diǎn)之間的最短路徑問題的提法：已知一個各邊權(quán)值均大于0的Floyd算法的基本思想：

假設(shè)求從頂點(diǎn)vi到vj的最短路徑。如果從vi到vj有弧，則從vi到vj存在一條長度為arcs[i][j]的路徑，但該路徑不一定是最短路徑。因?yàn)榭赡艽嬖谝粭l從vi到vj，但包含有其它頂點(diǎn)為中間點(diǎn)的路徑。因此，尚需進(jìn)行n次試探，測試從vi到vj有能否有以頂點(diǎn)v0,v1,v2，…,vn-1為中間點(diǎn)的更短路徑.74Floyd算法的基本思想：74

Floyd算法的實(shí)現(xiàn)：實(shí)現(xiàn)Floyd算法的關(guān)鍵，是保留每一步所求得的所有頂點(diǎn)對之間的當(dāng)前最短路徑長度。為此，定義一個n階方陣序列：

D(-1),D(0),…,D(n-1).

其中D(-1)[i][j]=arcs[i][j]；

D(k)[i][j]=min{D(k-1)[i][j]，

D(k-1)[i][k]+D(k-1)[k][j]},k=0,1,…,n-1D(0)[i][j]是從頂點(diǎn)vi到vj,中間頂點(diǎn)是v0的最短路徑的長度,D(k)[i][j]是從頂點(diǎn)vi到vj,中間頂點(diǎn)的序號不大于k的最短路徑的長度,D(n-1)[i][j]是從頂點(diǎn)vi到vj的最短路徑長度。75Floyd算法的實(shí)現(xiàn)：為此，定義一個n階方陣序列：

voidShortestPath_FLOYD(MGraphG,PathMatrix&P,

DistancMatrix&D){intu,v,w,i;for(v=0;v<G.vexnum;v++)for(w=0;w<G.vexnum;w++){D[v][w]=G.arcs[v][w].adj;for(u=0;u<G.vexnum;u++)P[v][w][u]=FALSE;if(D[v][w]<INFINITY){//從v到w有直接路徑P[v][w][v]=TRUE;P[v][w][w]=TRUE;}}for(u=0;u<G.vexnum;u++)for(v=0;v<G.vexnum;v++)for(w=0;w<G.vexnum;w++)if(D[v][u]+D[u][w]<D[v][w]){D[v][w]=D[v][u]+D[u][w];for(i=0;i<G.vexnum;i++)P[v][w][i]=P[v][u][i]||P[u][w][i];}}Floyd算法：76voidShortestPath_FLOYD(MGrap6.7拓?fù)渑判蛴媱?、施工過程、生產(chǎn)流程、程序流程等都是“工程”。除了很小的工程外，一般都把工程分為若干個叫做“活動”的子工程。完成了這些活動，這個工程就可以完成了。例如，計算機(jī)專業(yè)學(xué)生的學(xué)習(xí)就是一個工程，每一門課程的學(xué)習(xí)就是整個工程的一些活動。其中有些課程要求先修課程，有些則不要求。這樣在有的課程之間有先后關(guān)系，有的課程可以并行地學(xué)習(xí)。776.7拓?fù)渑判蛴媱?、施工過程、生產(chǎn)流程、程序流程等都是AOV網(wǎng)：在一個表示工程的有向圖中，用頂點(diǎn)表示活動，用弧表示活動之間的優(yōu)先關(guān)系，稱這樣的有向圖為頂點(diǎn)表示活動的網(wǎng)，簡稱AOV網(wǎng)。

應(yīng)用舉例——拓?fù)渑判駻OV網(wǎng)什么是工程？工程有什么共性？AOV網(wǎng)中出現(xiàn)回路意味著什么？78AOV網(wǎng)：在一個表示工程的有向圖中，用頂點(diǎn)表示活動，用弧表示AOV網(wǎng)：在一個表示工程的有向圖中，用頂點(diǎn)表示活動，用弧表示活動之間的優(yōu)先關(guān)系，稱這樣的有向圖為頂點(diǎn)表示活動的網(wǎng)，簡稱AOV網(wǎng)。

應(yīng)用舉例——拓?fù)渑判駻OV網(wǎng)2.AOV網(wǎng)中不能出現(xiàn)回路。AOV網(wǎng)特點(diǎn)：1.AOV網(wǎng)中的弧表示活動之間存在的某種制約關(guān)系。

什么是工程？工程有什么共性？79AOV網(wǎng)：在一個表示工程的有向圖中，用頂點(diǎn)表示活動，用弧表示拓?fù)湫蛄校涸O(shè)G=(V，E)是一個具有n個頂點(diǎn)的有向圖，V中的頂點(diǎn)序列v1,v2,…,vn稱為一個拓?fù)湫蛄?，?dāng)且僅當(dāng)滿足下列條件：若從頂點(diǎn)vi到vj有一條路徑，則在頂點(diǎn)序列中頂點(diǎn)vi必在頂點(diǎn)vj之前。拓?fù)渑判颍簩σ粋€有向圖構(gòu)造拓?fù)湫蛄械倪^程稱為拓?fù)渑判?。?yīng)用舉例——拓?fù)渑判蛲負(fù)渑判蛲負(fù)湫蛄惺沟肁OV網(wǎng)中所有應(yīng)存在的前驅(qū)和后繼關(guān)系都能得到滿足。80拓?fù)湫蛄校涸O(shè)G=(V，E)是一個具有n個頂點(diǎn)的有向圖，V中的基本思想：⑴從AOV網(wǎng)中選擇一個沒有前驅(qū)的頂點(diǎn)并且輸出；⑵從AOV網(wǎng)中刪去該頂點(diǎn)，并且刪去所有以該頂點(diǎn)為尾的?。虎?/p>

重復(fù)上述兩步，直到全部頂點(diǎn)都被輸出，或AOV網(wǎng)中不存在沒有前驅(qū)的頂點(diǎn)。

應(yīng)用舉例——拓?fù)渑判蛲負(fù)渑判蛲負(fù)渑判虻慕Y(jié)果？81基本思想：應(yīng)用舉例——拓?fù)渑判蛲負(fù)渑判蛲負(fù)渑判虻慕Y(jié)果？81AOE網(wǎng)AOE網(wǎng)：在一個表示工程的帶權(quán)有向圖中，用頂點(diǎn)表示事件，用有向邊表示活動，邊上的權(quán)值表示活動的持續(xù)時間，稱這樣的有向圖叫做邊表示活動的網(wǎng)，簡稱AOE網(wǎng)。AOE網(wǎng)中沒有入邊的頂點(diǎn)稱為始點(diǎn)（或源點(diǎn)），沒有出邊的頂點(diǎn)稱為終點(diǎn)（或匯點(diǎn)）。

AOE網(wǎng)的性質(zhì)：⑴只有在某頂點(diǎn)所代表的事件發(fā)生后，從該頂點(diǎn)出發(fā)的各活動才能開始；⑵只有在進(jìn)入某頂點(diǎn)的各活動都結(jié)束，該頂點(diǎn)所代表的事件才能發(fā)生。應(yīng)用舉例——關(guān)鍵路徑82AOE網(wǎng)AOE網(wǎng)：在一個表示工程的帶權(quán)有向圖中，用頂點(diǎn)表示事事件事件含義v1開工v2活動a1完成，活動a4可以開始v3活動a2完成，活動a5可以開始…………v9活動a10和a11完成，整個工程完成AOE網(wǎng)應(yīng)用舉例——關(guān)鍵路徑v2v1v3v4v5v8v6v7v9a1=6a4=1a7=9a10=2a11=4a8=7a9=4a5=1a6=2a3=5a2=483事件事件含義AOE網(wǎng)應(yīng)用舉例—應(yīng)用舉例——關(guān)鍵路徑AOE網(wǎng)可以回答下列問題：1.完成整個工程至少需要多少時間?2.為縮短完成工程所需的時間,應(yīng)當(dāng)加快哪些活動?

AOE網(wǎng)從始點(diǎn)到終點(diǎn)的路徑可能不止一條，只有各條路徑上所有活動都完成了，整個工程才算完成。因此，完成整個工程所需的最短時間取決于從始點(diǎn)到終點(diǎn)的最長路徑長度，即這條路徑上所有活動的持續(xù)時間之和。這條路徑長度最長的路徑就叫做關(guān)鍵路徑。84應(yīng)用舉例——關(guān)鍵路徑AOE網(wǎng)可以回答下列問題：AOE網(wǎng)從始點(diǎn)關(guān)鍵路徑應(yīng)用舉例——關(guān)鍵路徑關(guān)鍵路徑：在AOE網(wǎng)中，從始點(diǎn)到終點(diǎn)具有最大路徑長度（該路徑上的各個活動所持續(xù)的時間之和）的路徑稱為關(guān)鍵路徑。關(guān)鍵活動：關(guān)鍵路徑上的活動稱為關(guān)鍵活動。由于AOE網(wǎng)中的某些活動能夠同時進(jìn)行，故完成整個工程所必須花費(fèi)的時間應(yīng)該為始點(diǎn)到終點(diǎn)的最大路徑長度。關(guān)鍵路徑長度是整個工程所需的最短工期。85關(guān)鍵路徑應(yīng)用舉例——關(guān)鍵路徑關(guān)鍵路徑：在AOE網(wǎng)中，從始點(diǎn)到要找出關(guān)鍵路徑，必須找出關(guān)鍵活動,即不按期完成就會影響整個工程完成的活動。關(guān)鍵路徑應(yīng)用舉例——關(guān)鍵路徑首先計算以下與關(guān)鍵活動有關(guān)的量：⑴事件的最早發(fā)生時間ve[k]⑵事件的最遲發(fā)生時間vl[k]⑶活動的最早開始時間e[i]⑷活動的最晚開始時間l[i]

最后計算各個活動的時間余量l[k]-e[k]，時間余量為0者即為關(guān)鍵活動。86要找出關(guān)鍵路徑，必須找出關(guān)鍵活動,即不按期完成就會影響整個ve[k]是指從始點(diǎn)開始到頂點(diǎn)vk的最大路徑長度。這個長度決定了所有從頂點(diǎn)vk發(fā)出的活動能夠開工的最早時間。應(yīng)用舉例——關(guān)鍵路徑ve[1]=0ve[k]=max{ve[j]+len<vj,vk>}(<vj,vk>∈p[k])p[k]表示所有到達(dá)vk的有向邊的集合

⑴事件的最早發(fā)生時間ve[k]vjvk87ve[k]是指從始點(diǎn)開始到頂點(diǎn)vk的最大路徑長度。這個長度決vl[k]是指在不推遲整個工期的前提下,事件vk允許的最晚發(fā)生時間。⑵事件的最遲發(fā)生時間vl[k]應(yīng)用舉例——關(guān)鍵路徑vjvjvkvl[n]=ve[n]vl[k]=min{vl[j]-len<vk,vj>}（<vk,vj>∈s[k]）s[k]為所有從vk發(fā)出的有向邊的集合88vl[k]是指在不推遲整個工期的前提下,事件vk允許的最晚發(fā)⑶活動的最早開始時間e[i]應(yīng)用舉例——關(guān)鍵路徑若活動ai是由弧<vk

,vj>表示，則活動ai的最早開始時間應(yīng)等于事件vk的最早發(fā)生時間。因此，有：e[i]=ve[k]89⑶活動的最早開始時間e[i]應(yīng)用舉例——關(guān)鍵路徑若活動活動ai的最晚開始時間是指，在不推遲整個工期的前提下，ai必須開始的最晚時間。若ai由弧<vk，vj>表示，則ai的最晚開始時間要保證事件vj的最遲發(fā)生時間不拖后。因此，有：l[i]=vl[j]-len<vk,vj>⑷活動的最晚開始時間l[i]應(yīng)用舉例——關(guān)鍵路徑v2v7v6v5v4v1v3v9v8vl[k]181416107866090活動ai的最晚開始時間是指，在不推遲整個工期的前提下，aiC1高等數(shù)學(xué)C2程序設(shè)計基礎(chǔ)C3離散數(shù)學(xué)C1,C2

C4數(shù)據(jù)結(jié)構(gòu)C3,C2C5高級語言程序設(shè)計C2C6編譯方法C5,C4C7操作系統(tǒng)C4,C9C8普通物理C1C9計算機(jī)原理C8

課程代號課程名稱先修課程91C1高學(xué)生課程學(xué)習(xí)工程圖92學(xué)生課程學(xué)習(xí)工程圖92

可以用有向圖表示一個工程。在這種有向圖中，用頂點(diǎn)表示活動，用有向邊<Vi,Vj>表示活動的前后次序。Vi必須先于活動Vj

進(jìn)行。這種有向圖叫做頂點(diǎn)表示活動的

AOV網(wǎng)(ActivityOnVertices)。在AOV網(wǎng)中，如果活動Vi必須在活動Vj

之前進(jìn)行，則存在有向邊<Vi,Vj>，AOV網(wǎng)中不能出現(xiàn)有向回路，即有向環(huán)。在AOV網(wǎng)中如果出現(xiàn)了有向環(huán)，則意味著某項(xiàng)活動應(yīng)以自己作為先決條件。因此，對給定的AOV網(wǎng)，必須先判斷它是否存在有向環(huán)。93可以用有向圖表示一個工程。在這種有向93檢測有向環(huán)的一種方法是對AOV網(wǎng)構(gòu)造它的拓?fù)溆行蛐蛄?。即將各個頂點(diǎn)(代表各個活動)排列成一個線性有序的序列，使得AOV網(wǎng)中所有應(yīng)存在的前驅(qū)和后繼關(guān)系都能得到滿足。這種構(gòu)造AOV網(wǎng)全部頂點(diǎn)的拓?fù)溆行蛐蛄械倪\(yùn)算就叫做拓?fù)渑判?。如果通過拓?fù)渑判蚰軐OV網(wǎng)的所有頂點(diǎn)都排入一個拓?fù)溆行虻男蛄兄?，則該AOV網(wǎng)中必定不會出現(xiàn)有向環(huán)；相反，如果得不到滿足要求的拓?fù)溆行蛐蛄?，則說明AOV網(wǎng)中存在有向環(huán)，此AOV網(wǎng)所代表的工程是不可行的。94檢測有向環(huán)的一種方法是對AOV網(wǎng)構(gòu)造它的拓94例如，對學(xué)生選課工程圖進(jìn)行拓?fù)渑判颍玫降耐負(fù)溆行蛐蛄袨镃1,C2,C3,C4,C5,C6,C8,C9,C7

或C1,C8,C9,C2,C5,C3,C4,C7,C695例如，對學(xué)生選課工程圖進(jìn)行拓?fù)渑判颍玫降耐負(fù)溆行蛐蛄袨?5進(jìn)行拓?fù)渑判虻姆椒ㄝ斎階OV網(wǎng)。令n為頂點(diǎn)個數(shù)。1、在AOV網(wǎng)中選則一個入度為0的頂點(diǎn),并輸出之；2、從圖中刪去該頂點(diǎn),同時刪去所有它發(fā)出的有向邊;重復(fù)以上兩步,直到全部頂點(diǎn)均已輸出，拓?fù)溆行蛐蛄行纬桑負(fù)渑判蛲瓿桑换驁D中還有未輸出的頂點(diǎn)，但已跳出處理循環(huán)。這說明圖中還剩下一些頂點(diǎn)，它們都有直接前驅(qū)，再也找不到入度為0的頂點(diǎn)。這時AOV網(wǎng)中必定存在有向環(huán)。96進(jìn)行拓?fù)渑判虻姆椒ㄝ斎階OV網(wǎng)。令n為頂點(diǎn)個數(shù)。961、掃描鄰接表，計算各頂點(diǎn)的入度；2、將入度為0的頂點(diǎn)入棧；3、while(棧非空){將棧頂頂點(diǎn)v彈出并輸出之；檢查v的出邊，將每條出邊<v,u>終點(diǎn)u的入度減1，若u的入度變?yōu)?，則把u推入棧；}3、若輸出的頂點(diǎn)數(shù)小于n，則輸出“有回路”；否則拓?fù)渑判蛘＝Y(jié)束。拓?fù)渑判蛩惴蚣?71、掃描鄰接表，計算各頂點(diǎn)的入度；拓?fù)渑判蛩惴蚣?7算法分析設(shè)AOV網(wǎng)有n個頂點(diǎn)，e條邊。初始建立入度為0的頂點(diǎn)棧，要檢查所有頂點(diǎn)一次，執(zhí)行時間為O(n)；排序中，若AOV網(wǎng)無回路，則每個頂點(diǎn)入、出棧各一次，每個邊表結(jié)點(diǎn)被檢查一次，執(zhí)行時間為O(n+e)，所以總的時間復(fù)雜度為O(n+e)。98算法分析98作業(yè)完成并實(shí)現(xiàn)本章的所有重要算法99作業(yè)完成并實(shí)現(xiàn)本章的所有重要算法99第六章圖1.圖的基本概念2.圖的存儲結(jié)構(gòu)3.圖的遍歷4.最小生成樹5.最短路徑6.拓?fù)渑判?.關(guān)鍵路徑100第六章圖1.圖的基本概念1問題假設(shè)要在n個城市之間建立通信網(wǎng)。令圖G的頂點(diǎn)表示城市，邊表示連接兩個城市的通信線路，邊的權(quán)值表示通信線路的長度或代價。在n個城市間構(gòu)造通信網(wǎng)最少需要n-1條線路，問：如何選擇這n-1條邊，使得構(gòu)造這個通信網(wǎng)總的代價最?。?01問題假設(shè)要在n個城市之間建立通信網(wǎng)。令圖G的頂點(diǎn)表示城市，邊1、熟悉圖的各種存儲結(jié)構(gòu)2、熟練掌握遍歷圖的算法3、應(yīng)用圖的遍歷算法求解各種簡單路徑問題學(xué)習(xí)要點(diǎn)：1021、熟悉圖的各種存儲結(jié)構(gòu)學(xué)習(xí)要點(diǎn)：36.1圖的基本概念定義:

圖是由頂點(diǎn)集合(vertex)及邊的集合組成的一種數(shù)據(jù)結(jié)構(gòu)：

Graph＝(V,E)

其中

V={x|x

某個數(shù)據(jù)對象}

是頂點(diǎn)的有窮非空集合；

E={(x,y)|x,y

V}

是頂點(diǎn)之間關(guān)系的有窮集合，也叫做邊(edge)集合。例如:E={<A,B>,<C,D>,<A.D>,<B,C>}1036.1圖的基本概念定義:圖是由頂點(diǎn)集合(vert

有向圖與無向圖若圖G中的每條邊都是有方向的，則稱G為有向圖。有向邊也稱為弧。若圖G中的每條邊都是沒有方向的，則稱G為無向圖。完全圖對有n個頂點(diǎn)的圖，若為無向圖且邊數(shù)為n(n-1)/2(?)，則稱其為無向完全圖；若為有向圖且邊數(shù)為n(n-1)(?)，則稱其為有向完全圖。

稠密圖、稀疏圖104有向圖與無向圖若圖G中的每條邊都是有方向的，則稱G為頂點(diǎn)的度一個頂點(diǎn)v的度是與它相關(guān)聯(lián)的邊的條數(shù)。記作TD(v)。頂點(diǎn)v的入度是以v為終點(diǎn)的有向邊的條數(shù),記作ID(v);頂點(diǎn)v

的出度是以v為始點(diǎn)的有向邊的條數(shù),記作OD(v)。

鄰接點(diǎn)：若（vi,vj）是一條無向邊，則稱頂點(diǎn)vi和vj互為鄰接點(diǎn)。1235687410796671231516ABDCE60304535804075105頂點(diǎn)的度一個頂點(diǎn)v的度是與它相關(guān)聯(lián)的邊的條數(shù)。記作子圖

設(shè)有兩個圖G＝(V,E)和G‘＝(V’,E‘)。若V’V且E‘E,則稱圖G’是圖G的子圖。106子圖設(shè)有兩個圖G＝(V,E)和G‘＝(V’,E

路徑在圖G＝(V,E)中,若從頂點(diǎn)

vi出發(fā),沿一些邊經(jīng)過一些頂點(diǎn)

vp1,vp2,…,vpm，到達(dá)頂點(diǎn)vj。則稱頂點(diǎn)序列(vi

vp1vp2...vpm

vj)

為從頂點(diǎn)vi到頂點(diǎn)vj的路徑。它經(jīng)過的邊(vi,vp1)、(vp1,vp2)、...、(vpm,vj)應(yīng)是屬于E的邊。簡單路徑若路徑上各頂點(diǎn)v1,v2,...,vm均不互相重復(fù),則稱這樣的路徑為簡單路徑。回路若路徑上第一個頂點(diǎn)v1與最后一個頂點(diǎn)vm重合,則稱這樣的路徑為回路或環(huán)。路徑長度非帶權(quán)圖的路徑長度是指此路徑上邊的條數(shù)。帶權(quán)圖的路徑長度是指路徑上各邊的權(quán)之和。107路徑在圖G＝(V,E)中,若從頂點(diǎn)v圖的連通在無向圖G中，若兩個頂點(diǎn)vi和vj之間有路徑存在，則稱vi和vj是連通的。若G中任意兩個頂點(diǎn)都是連通的，則稱G為連通圖。非連通圖的極大連通子圖叫做連通分量。

強(qiáng)連通圖與強(qiáng)連通分量在有向圖中,若對于每一對頂點(diǎn)vi和vj,都存在一條從vi到vj和從vj到vi的路徑,則稱此圖