數(shù)據(jù)結構（C語言版）（第三版）（微課版）第6章 圖

第6章圖教學要求相關知識點圖的常用術語：有向圖、無向圖、完全圖、有向完全圖、稀疏圖、稠密圖、網(wǎng)、鄰接點、路徑、簡單路徑、回路或環(huán)、簡單回路、連通、連通圖、強連通圖、生成樹圖的鄰接矩陣存儲表示圖的鄰接表存儲表示圖的深度優(yōu)先遍歷(Depth-FirstSearch,DFS)圖的廣度優(yōu)先遍歷(Breadth-FirstSearch,BFS)最小生成樹拓撲排序和關鍵路徑最短路徑教學要求學習重點圖的存儲與操作圖的遍歷、最小生成樹、最短路徑算法目錄圖的存儲與操作圖的遍歷圖與最小生成樹3圖的定義和基本術語124最短路徑5AOV網(wǎng)與拓撲排序AOE網(wǎng)與關鍵路徑本章小結7686.1圖的定義和基本術語6.1圖的定義和基本術語圖的定義及基本術語1.圖的定義在圖中的數(shù)據(jù)元素通常稱為頂點，圖G(Graph)是由頂點集合(vertex)及頂點之間的關系集合（稱為邊或弧）組成的一種數(shù)據(jù)結構。記為G=(V,E)。2.圖的基本術語(1)無向邊如果頂點vi和vj間的邊沒有方向，則稱該邊為無向邊(Edge)。用無序偶對表示：(vi，vj)。6.1圖的定義和基本術語(2)有向邊(弧)如果頂點vi和vj間的邊有方向，則稱該邊為有向邊(或稱為弧Arc)。用有序偶對表示：<vi，vj>。(3)無向圖在一個圖G中，任意兩個頂點構成的偶對(vi，vj)∈E都是無序的，即兩點相連形成的邊都是沒有方向的，則稱該圖為無向圖(Undigraph)。圖6.1(a)所示是一個無向圖G1。圖6.1(a)無向圖G1

6.1圖的定義和基本術語(4)有向圖在一個圖G中，任意兩個頂點構成的偶對(vi，vj)∈E都是有序的，即兩點相連形成的邊都是有方向的，則稱該圖為有向圖(Digraph)。如圖6.1(b)所示是一個有向圖G2，在該圖中，G2=(V2,E2)，V2={v1,v2,v3}，E2={<v1,v2>,<v2,v1>,<v2,v3>,<v1,v3>}。圖6.1(b)有向圖G26.1圖的定義和基本術語(5)弧頭、弧尾在無向圖中，任意兩個頂點之間的連線稱為邊，并且不區(qū)分首尾；在有向圖中，任意兩個頂點之間的連線稱為弧，并且，有向圖的弧需區(qū)分弧頭和弧尾。例如：將頂點vi和vj之間的連線記為有序偶對<vi，vj>，其中頂點vi稱為初始點(弧尾Tail)，即弧的射出端，就是不帶箭頭的一端。頂點vj稱為終端點(或弧頭Head)，即弧的射入端，就是帶著箭頭的一端。6.1圖的定義和基本術語(6)權、網(wǎng)在邊或者弧上的數(shù)據(jù)信息稱為邊的權(Weight)。權值可以表示從一個頂點到另一個頂點的距離、時間或者價格等。帶權的圖稱為網(wǎng)(Network)。

圖6.2(a)無向網(wǎng)G3圖6.2(b)有向網(wǎng)G4。6.1圖的定義和基本術語(7)完全圖如果無向圖中任意兩個頂點間都存在邊，則稱之為無向完全圖(CompletedGraph)。在一個含有n個頂點的無向完全圖中，邊數(shù)為n(n-1)/2條。如果有向圖中任意兩個頂點間都存在方向互為相反的兩條弧，則稱之為有向完全圖。在一個含有n個頂點的有向完全圖中，邊數(shù)為n(n-1)條。(8)稠密圖、稀疏圖當一個圖接近完全圖時，稱之為稠密圖(DenseGraph)；相反地，當一個圖中含有較少的邊或弧時，則稱之為稀疏圖(SparseGraph)。6.1圖的定義和基本術語(9)子圖若有兩個圖G1和G2，其中，G1=(V1,E1)，G2=(V2,E2)，且滿足如下條件：V2?V1，E2?E1即V2為V1的子集，E2為E1的子集，則稱圖G2為圖G1的子圖。6.1圖的定義和基本術語(10)鄰接點和度對于無向圖，假若頂點v和頂點w之間存在一條邊，則稱頂點v和w互為鄰接點；和頂點v關聯(lián)的邊的數(shù)目定義為v的度。記為ID(v)。無向圖不區(qū)分入度和出度。對于有向圖，由于弧有方向性，則有入度和出度之分。頂點的出度(OutDegree)是以頂點v為弧尾的弧的數(shù)目，記為OD(v)；頂點的入度(InDegree)是以頂點v為弧頭的弧的數(shù)目，記為ID(v)；頂點的度記為TD(v)，有TD(v)=OD(v)+ID(v)。6.1圖的定義和基本術語(11)路徑、路徑長度頂點vi到頂點vj的路徑(Path)是指從頂點vi到頂點vj之間所經(jīng)歷的頂點序列vi，vi,1…vi,m，vj，其中(vi，vi,1)(vi,m，vj)和(vi,j，vi,j+1)∈E都是圖中的邊(1≤j≤m-1)。路徑的長度是路徑上的邊或弧的數(shù)目。(12)簡單路徑、回路、簡單回路頂點序列中頂點不重復出現(xiàn)的路徑，稱為簡單路徑；若頂點序列中第一個頂點和最后一個頂點相同，則稱該路徑為回路或環(huán)(Cycle)；若頂點序列中除第一個頂點和最后一個頂點相同外，其余頂點不重復，則稱該回路為簡單回路或者簡單環(huán)。6.1圖的定義和基本術語(13)連通圖、連通分量無向圖G中，如果從頂點vi到頂點vj有路徑，則稱頂點vi和vj是連通的。如果對于圖中任意兩個頂點vi、vj∈V，vi和vj都是連通的，則稱圖G為連通圖(ConnectedGraph)。在無向圖中，在滿足連通條件時，盡可能多地包含原圖中的頂點和這些頂點之間的邊的連通子圖稱為該圖的連通分量(ConnectedComponent)；連通圖的連通分量是它本身，非連通圖的連通分量可能為多個。6.1圖的定義和基本術語例如：圖6.3中的G5就是一個連通圖。而G6就是非連通圖，但有2個連通分量，如圖6.4所示。6.3連通圖G5圖6.4非連通圖G6及兩個連通分量6.1圖的定義和基本術語(14)強連通圖、強連通分量有向圖G中，如果從vi到vj有路徑，則稱頂點vi和頂點vj是連通的；若圖中任意兩個頂點之間都存在兩條互為反方向的路徑，即從vi到vj及從vj到vi都有路徑，則稱此有向圖為強連通圖。有向圖中的極大連通子圖稱作該有向圖的強連通分量。6.1圖的定義和基本術語例如，圖6.5中的G7就是一個強連通圖。而G8就是非強連通圖，但有2個強連通分量，如圖6.6所示。圖6.6非強連通圖G8及兩個連通分量圖6.5強連通圖G76.1圖的定義和基本術語(15)生成樹連通圖G的生成樹，是包含G的全部n個頂點的一個極小連通子圖，該極小連通子圖有(n-1)條邊。如圖6.7所示，是連通圖G5的生成樹。如果在一棵生成樹上添加一條邊，必定構成一個環(huán)，因為這條邊的出現(xiàn)使得它依附的那兩個頂點之間有了第二條路徑。一棵有n個頂點的生成樹有且僅有(n-1)條邊。如果一個圖有n個頂點和小于(n-1)條邊，則是非連通圖。如果它多于(n-1)條邊，則一定有環(huán)。但需要大家注意的是，有(n-1)條邊的圖不一定是生成樹。6.1圖的定義和基本術語(16)生成森林如果一個有向圖有且僅有一個頂點的入度為0，其他頂點的入度均為1，則這個圖是一棵有向樹。當一個有向圖有多個頂點的入度為0時，它的生成森林則由多棵有向樹構成。這個生成森林含有圖中全部的頂點和相應的弧。如圖6.8所示是有向圖G9及其生成森林。6.1圖的定義和基本術語連通圖G5及生成樹有向圖G9及生成森林6.2圖的存儲與操作6.2圖的存儲與操作鄰接矩陣鄰接矩陣（AdjacencyMatrix）是用兩個數(shù)組來表示圖，一個數(shù)組是一維數(shù)組，存儲圖中頂點的信息，另一個數(shù)組是二維數(shù)組，即矩陣，存儲頂點之間相鄰的信息，也就是邊（或?。┑男畔ⅰ?.2圖的存儲與操作1.圖的鄰接矩陣存儲法無向圖G5的鄰接矩陣6.2圖的存儲與操作1.圖的鄰接矩陣存儲法有向圖G9的鄰接矩陣6.2圖的存儲與操作2.網(wǎng)的鄰接矩陣存儲法無向網(wǎng)的鄰接矩陣6.2圖的存儲與操作2.網(wǎng)的鄰接矩陣存儲法有向網(wǎng)的鄰接矩陣6.2圖的存儲與操作3.鄰接矩陣表示法的特點(1)因為無向圖的鄰接矩陣具有對稱性，一定是一個對稱矩陣，所以可以采取壓縮存儲的方式只存儲矩陣的上三角(或下三角)矩陣元素。(2)無向圖(網(wǎng))的鄰接矩陣的第i行(或第i列)非零元素(或非∞元素)的個數(shù)正好是第i個頂點的度TD(vi)。(3)有向圖(網(wǎng))的鄰接矩陣的第i行非零元素(或非∞元素)的個數(shù)正好是第i個頂點的出度OD(vi)。(4)有向圖(網(wǎng))的鄰接矩陣的第i列非零元素(或非∞元素)的個數(shù)正好是第i個頂點的入度ID(vi)。6.2圖的存儲與操作4.鄰接矩陣表示法的優(yōu)缺點用鄰接矩陣方法存儲圖，很容易確定圖中任意兩個頂點之間是否有邊相連（鄰接），但要確定圖中有多少條邊，則必須按行、按列對每個元素進行檢測，所花費的時間代價很大，同時，鄰接矩陣存儲空間為O(n2)，所以適用于稠密圖。6.2圖的存儲與操作5.圖的鄰接矩陣存儲定義/*圖的鄰接矩陣存儲*/#defineMAXSIZE10typedefcharElemType;/*定義頂點數(shù)據(jù)類型*/typedefstruct{ElemTypeV[MAXSIZE];/*頂點信息*/

intarcs[MAXSIZE][MAXSIZE];//鄰接矩陣

inte;/*邊數(shù)*/

intn;/*頂點數(shù)*/}Graph;/*圖的鄰接矩陣數(shù)據(jù)類型*/6.2圖的存儲與操作6.鄰接矩陣操作(1)在圖中查找頂點在圖G中查找頂點v，找到返回其在頂點數(shù)組中的索引號；若不存在，返回-1intLocateVex(GraphG,ElemTypev){inti;

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

if(G.V[i]==v)returni;

return-1;}6.2圖的存儲與操作(2)在屏幕上顯示圖G的鄰接矩陣表示算法6.2在屏幕上顯示圖G的鄰接矩陣表示voidDisplayAdjMatrix(GraphG){inti,j;

printf("圖的鄰接矩陣表示：\n");

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

{for(j=0;j<G.n;j++) printf("%3d",G.arcs[i][j]);

printf("\n");

}}6.2圖的存儲與操作(3)無向圖/無向網(wǎng)/有向圖/有向網(wǎng)的鄰接矩陣的建立算法6.3創(chuàng)建無向圖/無向網(wǎng)/有向圖/有向網(wǎng)的鄰接矩陣voidCreateUndirectedGraphAdj(Graph*pg){

inti,j,k;

ElemTypev1,v2;

for(k=0;k<pg->e;k++)/*邊數(shù)e*/

{scanf("%c%c",&v1,&v2);/*輸入一條邊的兩個端點(圖)*/

scanf("%c%c%d",&v1,&v2,&w);/*輸入一條邊的兩個頂點及邊的權(網(wǎng))*/6.2圖的存儲與操作/*確定兩個頂點在圖G中的位置*/

i=LocateVex(*pg,v1);j=LocateVex(*pg,v2);/*創(chuàng)建鄰接矩陣*/if(i>=0&&j>=0){pg->arcs[i][j]=1;pg->arcs[j][i]=1;/*創(chuàng)建無向圖的鄰接矩陣*/

pg->arcs[i][j]=w;pg->arcs[j][i]=w;/*創(chuàng)建無向網(wǎng)的鄰接矩陣*/

pg->arcs[i][j]=1;/*創(chuàng)建有向圖的鄰接矩陣*/

pg->arcs[i][j]=w;/*創(chuàng)建有向網(wǎng)的鄰接矩陣*/}

}}6.2圖的存儲與操作鄰接表1.圖的鄰接表存儲法鄰接表(AdjacencyList)是圖的一種順序存儲與鏈式存儲結合的存儲方法；對于圖G中的每個頂點Vi，將所有鄰接于Vi的頂點Vj鏈成一個單鏈表，這個單鏈表就稱為頂點Vi的鄰接表；再將所有頂點的鄰接表表頭放到數(shù)組中。6.2圖的存儲與操作在鄰接表表示中，包括兩種結點結構。

(1)頭節(jié)點：由2個域構成。頂點域vex標記頂點vi的信息，鏈域(firstarc)標記第一個鄰接節(jié)點。

(2)表節(jié)點：由3個域構成，鄰接點域(adjvex)標記與頂點vi鄰接的點在圖中的位置，鏈域(nextarc)標記下一個與vi鄰接的節(jié)點，數(shù)據(jù)域data標記和邊(或弧)的相關信息，例如權值等。vexfirstarcadjvexnextarcdata圖6.11鄰接表的節(jié)點結構6.2圖的存儲與操作2.圖的逆鄰接表存儲法有向圖的鄰接表不方便查找以vi為弧頭的節(jié)點數(shù)逆鄰接表為每一個頂點建立一個以vi為弧頭的表。無向圖G1的鄰接表(a)無向圖G1的鄰接表僅以頂點編號作為信息輸入，時間復雜度為O(n+e)。6.2圖的存儲與操作2.圖的逆鄰接表存儲法有向圖G2的鄰接表和逆鄰接表(b)有向圖G2的鄰接表(c)有向圖G2的逆鄰接表僅以頂點編號作為信息輸入，時間復雜度為O(n+e)。6.2圖的存儲與操作3.無向圖的鄰接表存儲法的特點（1）第i個鏈表中結點的數(shù)目為第i個頂點的度。（2）所有鏈表中結點的數(shù)目的一半為圖中邊的數(shù)目。（3）占用的存儲單元數(shù)目為n＋2e。（n為頂點數(shù)，e為邊數(shù)）

4.有向圖的鄰接表存儲法的性質(zhì)（1）鄰接表中，第i個鏈表中結點的數(shù)目為頂點i的出度。逆鄰接表中，第i個鏈表中結點的數(shù)目為頂點i的入度。（2）所有鏈表中結點的數(shù)目為圖中弧的數(shù)目。（3）占用的存儲單元數(shù)為n＋e。（n為頂點數(shù)，e為弧數(shù)）6.2圖的存儲與操作5.鄰接表存儲法的優(yōu)缺點在鄰接表中可以快速找到某一頂點的鄰接點，但是要確定任意兩個頂點(vi和vj)間是否有邊(或弧)，就必須搜索第i個或者第j個鏈表，在這個方面遠不及鄰接矩陣快捷。6.2圖的存儲與操作6.圖的鄰接表存儲定義#defineMAXSIZE10typedefcharElemType;/*定義頂點類型為char*//*邊節(jié)點的類型定義*/typedefstructArcNode{intadjVex;

structArcNode*nextArc;

intweight;}ArcNode;6.2圖的存儲與操作/*頂點節(jié)點的類型定義*/typedefstructVNode{ElemTypedata;

ArcNode*firstArc;}VNode;/*圖的鄰接表數(shù)據(jù)類型*/typedefstruct{VNodeadjList[MAXSIZE];

intn,e;/*圖的頂點數(shù)和弧數(shù)*/}ALGraph;6.2圖的存儲與操作7.鄰接表操作(1)在圖G中查找頂點在圖G中查找頂點v，找到后返回其在頂點數(shù)組中的索引號；若不存在，返回-1intLocateVex(ALGraphG,ElemTypev){inti;

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

if(G.adjList[i].data==v)returni;

return-1;}6.2圖的存儲與操作(2)無向圖的鄰接表/有向圖的鄰接表/逆鄰接表的建立voidCreateUndirectedGraphLink(ALGraph*pg){inti,j,k;

ElemTypev1,v2;

ArcNode*s;

for(i=0;i<=pg->n;i++) /*n為頂點數(shù)*/

{scanf("%c",&pg->adjList[i].data); /*構造頂點信息*/

pg->adjList[i].firstArc=NULL;}

6.2圖的存儲與操作

for(k=0;k<pg->e;k++) /*e為邊數(shù)*/

{scanf("%c%c",&v1,&v2);/*確定兩個頂點在圖G中的位置*/

i=LocateVex(*pg,v1);j=LocateVex(*pg,v2);

if(i>=0&&j>=0)

{

/*創(chuàng)建無向圖的鄰接表*/

6.2圖的存儲與操作

s=(ArcNode*)malloc(sizeof(ArcNode));s->adjVex=j;s->nextArc=pg->adjList[i].firstArc;pg->adjList[i].firstArc=s;//頭插法s=(ArcNode*)malloc(sizeof(ArcNode));s->adjVex=i;

s->nextArc=pg->adjList[j].firstArc;pg->adjList[j].firstArc=s;//頭插法6.2圖的存儲與操作

/*創(chuàng)建有向圖的鄰接表*/

s=(ArcNode*)malloc(sizeof(ArcNode));s->adjVex=j;

s->nextArc=pg->adjList[i].firstArc;pg->adjList[i].firstArc=s;//頭插法6.2圖的存儲與操作

/*創(chuàng)建有向圖的逆鄰接表*/

s=(ArcNode*)malloc(sizeof(ArcNode));s->adjVex=i;

s->nextArc=pg->adjList[j].firstArc;pg->adjList[j].firstArc=s;//頭插法

}}}6.2圖的存儲與操作(3)在屏幕上顯示圖G的鄰接表表示voidDisplayAdjList(ALGraphG){inti;ArcNode*p;printf("圖的鄰接表表示：");

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

{printf("\n%4c",G.adjList[i].data);

p=G.adjList[i].firstArc;

while(p!=NULL){printf("->%d",p->adjVex);

p=p->nextArc;}

}

printf("\n");}6.3圖的遍歷6.3圖的遍歷圖的遍歷：從圖中的任意頂點出發(fā)，訪問其余頂點，并且保證所有頂點都被訪問且只被訪問一次，稱此過程為圖的遍歷(TraversingGraph)。判斷圖的連通性、拓撲排序和求關鍵路徑都以圖的遍歷為基礎。圖的遍歷過程中應該注意以下問題：(1)如何選取起始節(jié)點。在無向圖中，我們可以任意選取起始節(jié)點。在有向圖中，我們應當盡量選取入度為0的節(jié)點作為起始節(jié)點。(2)當遍歷的圖是非連通圖時，從一個節(jié)點出發(fā)只能訪問它所在的連通分量上的所有節(jié)點，并不能訪問圖的所有節(jié)點。遍歷還需考慮不同連通分量的起始節(jié)點的選取問題。6.3圖的遍歷(3)圖中的一個節(jié)點可能和多個節(jié)點相鄰接，我們?nèi)绾芜x取下一個鄰接點。(4)無向圖和有向圖中都有可能存在回路，那么在一個節(jié)點被訪問之后有可能因為回路的存在而再次被訪問，我們?nèi)绾伪苊庖粋€節(jié)點被多次訪問。6.3圖的遍歷深度優(yōu)先遍歷算法1.圖的深度優(yōu)先（DFS）遍歷深度優(yōu)先遍歷(depth-firstsearch，DFS)類似于樹的先根遍歷，是樹的先根遍歷的推廣。假設給定圖G的初態(tài)是所有頂點均未曾訪問過，在G中任選頂點V為出發(fā)點（源點），則深度優(yōu)先搜索遍歷可定義為：（1）首先訪問出發(fā)點V；（2）然后依次從V出發(fā)搜索V的每個鄰接點W，若W未曾訪問過，則以W為新的出發(fā)點繼續(xù)進行深度優(yōu)先搜索遍歷，直至圖中所有和源點V有路徑相通的頂點（也稱為從源點可達的頂點）均已被訪問為止；6.3圖的遍歷（3）若此時圖中仍有未訪問的頂點，則另選一個尚未訪問的頂點作為新的源點重復上述過程，直至圖中所有頂點均已被訪問為止。這兩種深度優(yōu)先搜索遍歷序列為：v1v2v5v4v8v3v7v6v1v2v5v4v8v3v6v7從頂點V1出發(fā)的深度優(yōu)先搜索遍歷序列可能有多種，這里只給出其中的兩種，其它的可類似分析。6.3圖的遍歷顯然，圖的深度優(yōu)先遍歷是一個遞歸的過程?？梢远x一個訪問標記數(shù)組visited[0…n-1]，初始值均為false，一旦某個節(jié)點被訪問，立即對其相應分量置true，由此可以區(qū)別圖中節(jié)點是否被訪問過，并最終遍歷所有節(jié)點，同時避免了節(jié)點的重復訪問。6.3圖的遍歷2.圖的深度優(yōu)先遍歷操作算法6.7從圖的某一節(jié)點出發(fā)進行深度優(yōu)先搜索voidDFSTraverse(GraphG){intv;for(v=0;v<G.n;v++)visited[v]=0;/*初始化標識數(shù)組*/for(v=0;v<G.n;v++)/*保證非連通圖的遍歷*//*從第v個頂點出發(fā)遞歸地深度優(yōu)先遍歷圖G*/if(!visited[v])DFS(G,v);}6.3圖的遍歷算法6.8利用鄰接矩陣實現(xiàn)連通圖的深度優(yōu)先遍歷/*從第i個頂點出發(fā)遞歸地深度優(yōu)先遍歷圖G*/voidDFS(GraphG,inti){intj;printf("%3c",G.V[i]);/*訪問第i個頂點*/visited[i]=1;for(j=0;j<G.n;j++)

if((G.arcs[i][j]==1)&&(visited[j]==0))

DFS(G,j);//對i的尚未訪問的鄰接點j遞歸調(diào)用DFS}6.3圖的遍歷算法6.9用鄰接表實現(xiàn)連通圖的深度優(yōu)先遍歷/*從第i個頂點出發(fā)遞歸地深度優(yōu)先遍歷圖G*/voidDFS(ALGraphG,inti){ArcNode*p;printf(“%3c”,G.adjList[i].data);//訪問頂點ivisited[i]=1;p=G.adjList[i].firstArc;while(p!=NULL){if(visited[p->adjVex]==0)//未訪問的鄰接點DFS(G,p->adjVex);//遞歸調(diào)用DFSp=p->nextArc;}}6.3圖的遍歷廣度優(yōu)先遍歷算法1.圖的廣度優(yōu)先遍歷廣度優(yōu)先搜索(Breadth_FirstSearch)遍歷類似于樹的按層次遍歷。設圖G的初態(tài)是所有的頂點均未訪問過，在G中任選一頂點vi為源點，過程為：（1）首先訪問出發(fā)點vi，并將其訪問標志置為已被訪問，即visited[i]=true；（2）依次訪問頂點vi的所有鄰接點w0，w1，……，wt；（3）再依次訪問頂點w0，w1，……，wt的所有鄰接點。（4）如此類推，直至圖中所有的頂點都被訪問到。6.3圖的遍歷從頂點V1出發(fā)的廣度優(yōu)先搜索遍歷序列可能有多種，這里只給出其中的三種，其它的可類似分析。這三種廣度優(yōu)先搜索遍歷序列為：v1，v2，v3，v4，v5，v6，v7，v8v1，v3，v2，v7，v6，v5，v4，v8v1，v2，v3，v5，v4，v7，v6，v86.3圖的遍歷2.圖的廣度優(yōu)先遍歷操作算法6.10對圖進行廣度優(yōu)先遍歷voidBFSTraverse(GraphG){intv;for(v=0;v<G.n;v++)//初始化標志數(shù)組

visited[v]=0;for(v=0;v<G.n;v++)//保證全圖的遍歷

if(!visited[v])BFS(G,v);//從第v個頂點出發(fā)遞歸地廣度優(yōu)先遍歷圖G}

6.3圖的遍歷算法6.11廣度優(yōu)先遍歷以鄰接矩陣存儲的圖//從第k個頂點出發(fā)廣度優(yōu)先遍歷圖G,G以鄰接矩陣表示voidBFS(GraphG,intk){inti,j; InitQueue(&Q);/*初始化隊列*/printf("%3c",G.V[k]);/*訪問第k個頂點*/visited[k]=1;EnQueue(&Q,k);/*第k個頂點進隊*/while(!QueueEmpty(&Q))/*隊列非空*/{DelQueue(&Q,&i);6.3圖的遍歷for(j=0;j<G.n;j++){if((G.arcs[i][j]==1)&&(visited[j]==0)){/*訪問第i個頂點的末曾訪問的頂點j*/printf("%3c",G.V[j]);visited[j]=1;EnQueue(&Q,j);/*第k個頂點進隊*/}}}}6.3圖的遍歷算法6.12廣度優(yōu)先遍歷以鄰接表存儲的圖voidBFS(ALGraphG,intk){inti;ArcNode*p;InitQueue(&Q);/*初始化隊列*/printf(“%3c”,G.adjList[k].data);//訪問頂點kvisited[k]=1; EnQueue(&Q,k);/*第k個頂點進隊*/while(!QueueEmpty(&Q))/*隊列非空*/

{

DelQueue(&Q,&i);p=G.adjList[i].firstArc;/*獲取第1個鄰接點*/6.3圖的遍歷while(p!=NULL){if(visited[p->adjVex]==0){/*訪問第i個頂點的末曾訪問的頂點*/printf("%3c",G.adjList[p->adjVex].data);visited[p->adjVex]=1;EnQueue(&Q,p->adjVexp=p->nextArc;}p=p->nextArc;}}}

6.4圖與最小生成樹6.4圖與最小生成樹生成樹和森林的概念在一個有n個頂點的連通圖G中，存在一個極小的連通子圖G’，G’包含圖G的所有頂點，但只有n-1條邊，并且G’是連通的，稱G’為G的生成樹。6.4圖與最小生成樹由深度優(yōu)先搜索得到的生成樹稱為深度優(yōu)先生成樹，簡稱為DFS生成樹；由廣度優(yōu)先搜索得到的生成樹稱為廣度優(yōu)先生成樹，簡稱為BFS生成樹。無向圖G11的兩種生成樹無向圖G11深度優(yōu)先生成樹廣度優(yōu)先生成樹6.4圖與最小生成樹若一個圖是非連通圖或非強連通圖，但有若干個連通分量或若干個強連通分量，則通過深度優(yōu)先搜索遍歷或廣度優(yōu)先搜索遍歷，不能得到生成樹，但可以得到生成森林，且若非連通圖有n個頂點，m個連通分量或強連通分量，則可以遍歷得到m棵生成樹，合起來為生成森林，森林中包含n-m條樹邊。6.4圖與最小生成樹最小生成樹無向連通帶權圖G的權為生成樹T中各邊的權值總和；邊的權值總和最小的生成樹，稱為最小代價生成樹(MinimumcostSpanningTree，MST)。構造最小生成樹的準則如下：(1)必須只使用該網(wǎng)中的邊來構造最小生成樹；(2)必須使用且僅使用n-1條邊來連接網(wǎng)中的n個頂點；(3)不能使用產(chǎn)生回路的邊。6.4圖與最小生成樹最小生成樹在帶權的連通無向圖G=(V,E)上，構造最小生成樹有普里姆算法和克魯斯卡爾算法，它們都是應用最小生成樹MST的性質(zhì)：U是頂點V的一個非空子集，若(u,v)是一條具有最小權值的邊，其中u∈U,v∈V?U，則一定存在一棵包含邊(u,v)的最小生成樹。6.4圖與最小生成樹1.通過普里姆算法生成最小生成樹(1)普里姆(Prim)算法的基本思想設G=(V,E)是帶權圖，V是圖G的頂點集，E是邊集。①在圖中任取一個頂點k作為開始點，令U={k}，W=V-U，TE={ф}，其中W為圖中剩余頂點的集合。②在由一個頂點在U中，另一個頂點在W中的兩個頂點構成的所有邊中，找出一條權值最小的邊(u，v)(u∈U，v∈W)，將該邊作為最小生成樹的樹邊放入TE，并將頂點v加入集合U中，并從W中刪去這個頂點。③重復②，直到W為空集為止。此時TE中有n-1條邊，此時T=(U,TE)就是G的一棵最小生成樹。6.4圖與最小生成樹普里姆算法是從最小生成樹中頂點的角度出發(fā)來考慮的，因為圖中有n個頂點，按照生成樹的定義，所有的頂點都必須加入到最小生成樹中，所以除去最初選定的頂點，剩余的n-1個頂點在加入到最小生成樹的過程中可以選擇n-1條邊加入到最小生成樹的邊集中。6.4圖與最小生成樹6.4圖與最小生成樹(2)普里姆算法的操作記錄從頂點集U到V-U的代價最小的邊需要設置一個MinEdge類型的輔助數(shù)組，類型定義如下：#defineMAXSIZE10typedefcharElemType;/*定義頂點類型*/typedefstruct{ ElemTypeadjvax;//U中的頂點

intlowcost;//邊的權值}MinEdge;//記錄從頂點集U到V-U的代價最小的邊需要的輔助數(shù)組類型6.4圖與最小生成樹//求集合V-U依附于頂點u(u∈U)的權值最小的頂點的序號/*在輔助數(shù)組中求出權值最小的頂點序號*/intMinCost(GraphG,MinEdgee[]){inti,j,min;

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

if(e[i].lowcost!=0)break;

min=i;

for(j=i+1;j<G.n;j++)

if(e[j].lowcost!=0&&e[j].lowcost<e[min].lowcost)min=j;

returnmin;}

6.4圖與最小生成樹/*【算法6.13普里姆算法】*//*從頂點v出發(fā)構造網(wǎng)G的最小生成樹，并輸出最小生成樹的各條邊*/voidMiniSpanTree_PRIM(GraphG,ElemTypev){inti,j,k;

MinEdgee[MAXSIZE];

k=LocateVex(G,v);/*確定頂點v在網(wǎng)G中的序號*/

for(j=0;j<G.n;j++)/*初始化輔助數(shù)組*/

if(j!=k)

{e[j].adjvax=v;

e[j].lowcost=G.arcs[k][j]

}6.4圖與最小生成樹

/*初始頂點生成樹集合，lowcost值為0，表示該頂點已并入生成樹集合*/

e[k].lowcost=0;

for(i=0;i<G.n-1;i++)

{k=MinCost(G,e);//求輔助數(shù)組中權值最小頂點

/*輸入最小生成樹的一條邊和對應的權值*/printf("(%c,%c,%d)“,e[k].adjvax,G.V[k],e[k].lowcost);

e[k].lowcost=0;//將頂點k并入生成樹集合6.4圖與最小生成樹

for(j=0;j<G.n;j++)/*重新調(diào)整e*/

if(G.arcs[k][j]<e[j].lowcost)

{e[j].adjvax=G.V[k];

e[j].lowcost=G.arcs[k][j];

}

}

printf("\n");}表6.1給出了在用算法6.13構造圖6.17的圖G13的最小生成樹的過程中，MinEdge類型數(shù)組元素的兩個成員分量及兩個集合的取值變化情況。

6.4圖與最小生成樹最小生成樹1.通過普里姆算法生成最小生成樹

e[vi]e[v1]e[v2]e[v3]e[v4]e[v5]e[v6]e[v7]UMinCostW=V-Uadjvexlowcostv10v118v1∞v1∞v1∞v12v14{v1}2{v2,v3,v4,v5,v6,v7}adjvexlowcostv10v118v1∞v1∞v69v10v14{v1,v6}4{v2,v3,v4,v5,v7}adjvexlowcostv10v713v1∞v1∞v69v10v10{v1,v6,v7}9{v2,v3,v4,v5}adjvexlowcostv10v713v1∞v51v60v10v10{v1,v6,v7,v5}1{v2,v3,v4}adjvexlowcostv10v713v45v50v60v10v10{v1,v6,v7,v5,v4}5{v2,v3}adjvexlowcostv10v36v40v50v60v10v10{v1,v6,v7,v5,v4,v3}6{v2}adjvexlowcostv10v30v40v50v60v10v10{v1,v6,v7,v5,v4,v3,v2}

{}6.4圖與最小生成樹6.4圖與最小生成樹2.通過克魯斯卡爾算法生成最小生成樹普里姆算法適用于稠密圖，而克魯斯卡爾算法適用于稀疏圖?？唆斔箍査惴ㄊ菑倪叺慕嵌惹髨D的最小生成樹。克魯斯卡爾算法考慮問題的出發(fā)點是為了使生成樹上邊的權值之和達到最小，這樣應使生成樹中每一條邊的權值盡可能小。6.4圖與最小生成樹克魯斯卡爾算法具體做法如下：(1)將圖中所有邊按權值遞增順序排列；(2)先構造一個只含n個頂點的子圖；(3)依次選取權值較小的邊，但要求后面選取的邊不能與前面選取的邊構成回路，若構成回路，則放棄該條邊，再去選取后面權值較大的邊。(4)重復第(3)步，在具有n個頂點的圖中，選夠n-1條邊即可。圖6.18是圖6.17(a)帶權無向圖的克魯斯卡爾算法構造最小生成樹的過程。6.4圖與最小生成樹6.5最短路徑6.5最短路徑單源點到其余各頂點的最短路徑

1.單源點最短路徑的定義在網(wǎng)圖中，求點A到點B的所有路徑中，邊的權值之和最短的那一條路徑。這條路徑就是兩點之間的最短路徑，并稱路徑上的第一個頂點為起點(Sourse)，最后一個頂點為終點(Destination)。最短路徑問題是圖的一個比較典型的應用問題。而單源點最短路徑是其中比較重的一個應用。設有向圖G=(V,E)。以某指定頂點為源點，求從出發(fā)到圖中其余各點的最短路徑稱為單源最短路徑。6.5最短路徑源點終點最短路徑路徑長度v6v1<v6，v1>2v6v2<v6，v7，v2>17v6v3<v6，v5，v4，v3>15v6v4<v6，v5，v4>10v6v5<v6，v5>9v6v7<v6，v7>4

通過表6.2可以看出，從v6出發(fā)到v3存在4條路徑，分別是<v6，v1，v2，v3>、<v6，v7，v2，v3>、<v6，v5，v7，v2，v3>、<v6，v5，v4，v3>，這四條路徑的長度分別是26，23，49，15。通過比較得出，<v6，v5，v4，v3>是v6到v3的最短路徑。

6.5最短路徑2.迪杰斯特拉(Dijlstra)算法迪杰斯特拉提出了按路長遞增產(chǎn)生各頂點的最短路徑算法。(1)迪杰斯特拉算法的基本思想把圖中所有頂點分成兩組，第一組包括已確定最短路徑的頂點，第二組包括未確定最短路徑的頂點，然后按最短路徑長度遞增的次序逐個把第二組的頂點加到第一組中，直至從源點出發(fā)可以到達的所有頂點都包括到第一組中。保持從源點到第一組各頂點的最短路徑長度都不大于從源點到第二組的任何頂點的最短路徑長度。每一個頂點都對應一個距離值，第一組頂點對應的距離值就是從源點到此頂點的只包括第一組的頂點為中間頂點的最短路徑長度。6.5最短路徑設v0是起始源點，S是已求得最短路徑的終點集合。迪杰斯特拉算法的基本思想是：①V-S=未確定最短路徑的頂點的集合，初始時S={v0}，長度最短路徑是邊數(shù)為1且權值最小的路徑。②下一條長度最短的路徑：vi

V-S，先求出v0到vi且中間只經(jīng)S中頂點的最短路徑；上述最短路徑中長度最小者即為下一條長度最短的路徑，將所求最短路徑的終點加入S中。③重復②直到求出所有終點的最短路徑。6.5最短路徑(2)迪杰斯特拉算法的實現(xiàn)為實現(xiàn)迪杰斯特拉算法，我們需要引入一個輔助數(shù)組D[i]，用于保存從源點出發(fā)到達頂點vi的最短路徑，其值為最短路徑長度。①初始時，若源點到頂點vi有邊，則D[i]為邊上的權值；否則，D[i]為∞。從v0出發(fā)，長度最短的路徑是(v0，vj)，即D[j]=min{D[i]|vi∈V-S}，將頂點vj加入S集合，同時將其從集合V-S中去掉；6.5最短路徑②求下一條長度最短的路徑：修改從v0出發(fā)到達集合V-S中所有頂點的最短路徑的長度。這些路徑可能是v0直達vk，或者是從v0出發(fā)經(jīng)過S中的某一個或一些頂點。如果D[j]+arcs[j][k]<D[k](vk∈V-S)，則修改D[k]為D[j]+arcs[j][k]。③最短路徑中長度最小者即為下一條長度最短的路徑，即D[j]=min{D[i]|vi∈V-S}。將頂點vj加入S集合，同時將其從集合V-S中去掉；④重復②和③直到求出所有頂點的最短路徑。最短路徑終點vi從v6頂點出發(fā)到其余各頂點的最短路徑path[i]的變化情況i=0i=1i=2i=3i=4i=5i=6

dist[v1]path[v1]

2<v6,v1>

dist[v2]path[v2]

∞20<v6,v1,v2>17<v6,v7,v2>17<v6,v7,v2>17<v6,v7,v2>17<v6,v7,v2>dist[v3]path[v3]

∞∞∞∞15<v6,v5,v4,v3>

dist[v4]path[v4]

∞∞∞10<v6,v5,v4>

dist[v5]path[v5]

9<v6,v5>9<v6,v5>9<v6,v5>

dist[v6]path[v6]0

dist[v7]path[v7]

4<v6,v7>4<v6,v7>

vj

v1v7v5v4v3v2S{v6}{v6,v1}{v6,v1,v7}{v6,v1,v7,v5}{v6,v1,v7,v5,v4}{v6,v1,v7,v5,v4,v3}{v6,v1,v7,v5,v4,v3,v2}6.5最短路徑voidDijkstra(GraphG,intv0,intpath[],intdist[])/*求有向圖G的v0頂點到其余頂點v的最短路徑，path[i]是v0到vi的最短路徑上的前驅(qū)頂點，dist[i]是路徑長度*/{ inti,j,v,w; intmin;ints[MAXSIZE]; for(i=0;i<G.n;i++)/*初始化s，dist和path*/ {s[i]=0;dist[i]=G.arcs[v0][i]; if(dist[i]<Max)path[i]=v0; elsepath[i]=-1;} dist[v0]=0;s[v0]=1;/*初始源點v0屬于s集*/ /*循環(huán)求v0到某個頂點v的最短路徑，并將v加入s集*/

6.5最短路徑for(i=1;i<G.n-1;i++){min=Max; for(w=0;w<G.n;w++)//w不屬于s且離v0更近 {if(!s[w]&&dist[w]<min) {v=w;min=dist[w];}} s[v]=1;/*頂點v并入s*/ for(j=0;j<G.n;j++)//更新最短路徑及距離 {if(!s[j]&&(min+G.arcs[v][j]<dist[j])) {dist[j]=min+G.arcs[v][j];path[j]=v;} }}}

6.6AOV網(wǎng)與拓撲排序6.6AOV網(wǎng)與拓撲排序AOV網(wǎng)在一個有向圖中，若用頂點表示活動，有向邊表示活動間的先后關系，稱該有向圖為用頂點表示活動的網(wǎng)絡(ActivityOnVertexnetwork，AOV)。若從頂點vi到頂點vj之間存在一條有向路徑，稱頂點vi是頂點vj的前驅(qū)，或者稱頂點vj是頂點vi的后繼。即若<vi，vj>是圖中的邊，則稱頂點vi是頂點vj的直接前驅(qū)，頂點vj是頂點vi的直接后繼。6.6AOV網(wǎng)與拓撲排序AOV網(wǎng)大工程被劃分成許多子工程(稱為活動)。在大工程實施過程中，有些活動開始是以它的所有前序活動的結束為先決條件的，必須在其他有關活動完成后才能開始；有些活動沒有先決條件，可以安排在任意時間開始。AOV網(wǎng)是一種可以形象地反映出整個工程中各個活動之間前后關系的有向圖。6.6AOV網(wǎng)與拓撲排序表6.4各課程先后依存關系表課程課程名稱先修課程C1高等數(shù)學無C2C語言程序設計無C3離散數(shù)學C1，C2C4數(shù)據(jù)結構C2，C3C5Java程序設計C2C6編譯方法C5，C7C7操作系統(tǒng)C4，C9C8數(shù)字邏輯C1C9計算機組成原理C8圖6.20課程開設的先后關系AOV網(wǎng)6.6AOV網(wǎng)與拓撲排序拓撲排序拓撲排序(TopologicalSort)是圖中重要的運算之一，在實際中應用很廣泛。對給定的AOV網(wǎng)應首先判定網(wǎng)中是否存在環(huán)。檢測的辦法是對有向圖進行拓撲排序（TopologicalSort），拓撲排序指按照有向圖給出的次序關系，將圖中頂點排成一個線性序列，對于有向圖中沒有限定次序關系的頂點，則加上任意的次序關系，所得頂點的線性序列稱之為拓撲排序序列。6.6AOV網(wǎng)與拓撲排序1.拓撲排序的定義給出有向圖G=(V，E)，對于V中的頂點的線性序列(v1，v-2，…，vk)，如果滿足如下條件：若在G中從頂點vi到vj有一條路徑，則在序列中頂點vi必在頂點vj之前，稱該序列為G的一個拓撲序列。構造有向圖的拓撲序列的過程稱為拓撲排序。6.6AOV網(wǎng)與拓撲排序(1)拓撲排序的注意事項①在AOV網(wǎng)中，若不存在回路，則所有活動可排成一個線性序列，使得每個活動的所有前驅(qū)活動都排在該活動的前面，那么該序列為拓撲序列。②拓撲序列不是唯一的。③對AOV網(wǎng)不一定都有拓撲序列。④將AOV圖中頂點排成一個線性序列，若該線性序列中包含AOV網(wǎng)全部的頂點，則AOV網(wǎng)中無環(huán)，否則，AOV網(wǎng)中存在有向環(huán)，該網(wǎng)所代表的工程是不可行的。6.6AOV網(wǎng)與拓撲排序(2)拓撲序列的實際意義如果按照拓撲序列中的頂點次序進行每一項活動，就能夠保證在開始每一項活動時，它的所有前驅(qū)活動均已完成，從而使整個工程順序執(zhí)行。6.6AOV網(wǎng)與拓撲排序2.拓撲排序的基本步驟①在AOV網(wǎng)中選一個入度為0的頂點(沒有前驅(qū))并輸出它；②從AOV網(wǎng)中刪除此頂點及從該頂點發(fā)出來的所有有向邊；③重復①②兩步，直到AOV網(wǎng)中所有的頂點都被輸出或網(wǎng)中不存在入度為0的頂點。6.6AOV網(wǎng)與拓撲排序2.拓撲排序的基本步驟對圖6.20進行拓撲排序。列舉兩種得到的拓撲有序序列：C1，C8，C9，C2，C3，C4，C7，C5，C6或 C1，C8，C9，C2，C5，C3，C4，C7，C66.7AOE網(wǎng)與關鍵路徑6.7AOE網(wǎng)與關鍵路徑AOE網(wǎng)若在帶權的有向圖中，以頂點表示事件；有向邊表示活動；邊上的權值表示活動的開銷(如該活動持續(xù)的時間)。則稱此帶權的有向圖為AOE(activityonedge)網(wǎng)。如果用AOE網(wǎng)來表示一項工程，可以如下信息：完成預定工程計劃所需要進行的活動；每個活動計劃的完成時間；要發(fā)生哪些事件以及這些事件與活動之間的關系。針對某一工程對應的AOE網(wǎng)，我們可以用確定關鍵路徑的方法來驗證該工程能否完成，并且要估計工程的完成所需要的時間以及確定哪些活動會影響工程進度。6.7AOE網(wǎng)與關鍵路徑AOE網(wǎng)在AOE網(wǎng)中，只有在某頂點所代表的事件發(fā)生后，從該頂點出發(fā)的各有向邊所代表的活動才能開始；只有在進入每個頂點的各有向邊所代表的活動都已經(jīng)結束后，該頂點所代表的事件才能發(fā)生。一個表示工程的AOE網(wǎng)應該是沒有回路的有向網(wǎng)，網(wǎng)中僅存在一個入度為0的頂點，稱作開始頂點(源點)，它表示整個工程的開始；網(wǎng)中僅存在一個出度為0的頂點，稱為結束頂點(匯點)，它表示整個工程的結束。6.7AOE網(wǎng)與關鍵路徑圖6.21是一個有9個活動11個事件的AOE網(wǎng)。頂點v1、v2、…、v9表示事件；<v1，v2>，<v1，v3>，<v1，v4>…<v8，v9>表示活動。其中v1為開始頂點，入度是0；v9為結束頂點，出度是0。6.7AOE網(wǎng)與關鍵路徑關鍵路徑1.相關術語(1)AOE網(wǎng)的路徑長度AOE網(wǎng)的路徑長度是該路徑上各個活動所需時間的總和。(2)關鍵路徑由于AOE網(wǎng)中的某些活動能夠同時進行，故完成整個工程所必須花費的時間應該為：源點到終點的最大路徑長度(路徑長度是指該路徑上的各個活動所需時間之和)。具有最大路徑長度的路徑稱為關鍵路徑。關鍵路徑上的活動稱為關鍵活動。6.7AOE網(wǎng)與關鍵路徑(3)事件的最早發(fā)生時間ve(i)從源點到頂點i的最大路徑長度代表的時間，意味著所有以頂點i為弧尾的活動的最早開始時間計算方法如下：①令ve(1)=0，i=2；②ve(i)=Max{ve(k)+t(k,i)|k為i的直接前驅(qū)}；③++i，重復②，直到i>n。6.7AOE網(wǎng)與關鍵路徑(4)事件的最遲發(fā)生時間vl(i)事件vi允許的最晚發(fā)生時間vl(k)是指在不推遲整個工程工期(即保證結束頂點vn在ve(n)時刻發(fā)生)的前提下，