數(shù)據(jù)結構第8章圖

8.1圖的基本概念第8章圖8.2圖的存儲結構8.3圖的遍歷8.4生成樹和最小生成樹8.5最短路徑8.6拓撲排序

8.7AOE網(wǎng)與關鍵路徑18.1圖的基本概念8.1.1圖的定義

圖(Graph)G由兩個集合V(Vertex)和E(Edge)組成,記為G=(V,E),其中V是頂點的有限集合,記為V(G),E是連接V中兩個不同頂點(頂點對)的邊的有限集合,記為E(G)。2

在圖G中,如果代表邊的頂點對是無序的,則稱G為無向圖,無向圖中代表邊的無序頂點對通常用圓括號括起來,用以表示一條無向邊。如：無向邊(V1,V2)

如果表示邊的頂點對是有序的,則稱G為有向圖,在有向圖中代表邊的頂點對通常用尖括號括起來。如：有向邊<V1,V2>38.1.2圖的基本術語端點和鄰接點

在一個無向圖中,若存在一條邊(vi,vj),則稱vi和vj為此邊的兩個端點,并稱它們互為鄰接點。

ViVj4

在一個有向圖中,若存在一條邊<vi,vj>,則稱此邊是頂點vi的一條出邊,同時也是頂點vj的一條入邊；稱vi和vj分別為此邊的起始端點(簡稱為起點)和終止端點(簡稱終點)；稱頂點vi鄰接到頂點vj。稱頂點vj是頂點vi的出邊鄰接點。稱頂點vi是頂點vj的入邊鄰接點。ViVj52.頂點的度、入度和出度

在無向圖中,頂點所具有的邊的數(shù)目稱為該頂點的度。在有向圖中,以頂點vi為終點的入邊的數(shù)目,稱為該頂點的入度。以頂點vi為始點的出邊的數(shù)目,稱為該頂點的出度。一個頂點的入度與出度的和為該頂點的度。若一個圖中有n個頂點和e條邊,每個頂點的度為di(1≤i≤n),則有：63.完全圖

若無向圖中的每兩個頂點之間都存在著一條邊,有向圖中的每兩個頂點之間都存在著方向相反的兩條邊,則稱此圖為完全圖。顯然,完全無向圖包含有n(n-1)/2條邊,完全有向圖包含有n(n-1)條邊。例如,圖(a)所示的圖是一個具有4個頂點的完全無向圖,共有6條邊。圖(b)所示的圖是一個具有4個頂點的完全有向圖,共有12條邊。

74.稠密圖、稀疏圖

當一個圖接近完全圖時,則稱為稠密圖。相反,當一個圖含有較少的邊數(shù)(即當e<<n(n-1))時,則稱為稀疏圖。5.子圖

設有兩個圖G=(V,E)和G’=(V’,E’),若V’是V的子集,即V’V,且E’是E的子集,即E’E,則稱G’是G的子圖。例如圖(b)是圖(a)的子圖,而圖(c)不是圖(a)的子圖。86.路徑和路徑長度

在一個圖G=(V,E)中,從頂點vi到頂點vj的一條路徑是一個頂點序列(vi,vi1,vi2,…,vim,vj),若此圖G是無向圖,則邊(vi,vi1),(vi1,vi2),…,(vim-1,vim),(vim,vj)屬于E(G)；若此圖是有向圖,則<vi,vi1>,<vi1,vi2>,…,<vim-1,vim>,<vim,vj>屬于E(G)。

路徑長度是指一條路徑上經(jīng)過的邊的數(shù)目。若一條路徑上除開始點和結束點可以相同外,其余頂點均不相同,則稱此路徑為簡單路徑。例如,有圖中,(v0,v2,v1)就是一條簡單路徑,其長度為2。97.回路或環(huán)

若一條路徑上的開始點與結束點為同一個頂點,則此路徑被稱為回路或環(huán)。開始點與結束點相同的簡單路徑被稱為簡單回路或簡單環(huán)。例如,右圖中,(v0,v2,v1,v0)就是一條簡單回路,其長度為3。108.連通、連通圖和連通分量

在無向圖G中,若從頂點vi到頂點vj有路徑,則稱vi和vj是連通的。若圖G中任意兩個頂點都連通,則稱G為連通圖,否則稱為非連通圖。無向圖G中的極大連通子圖稱為G的連通分量。顯然,任何連通圖的連通分量只有一個,即本身,而非連通圖有多個連通分量。119.強連通圖和強連通分量

在有向圖G中,若從頂點vi到頂點vj有路徑,則稱從vi到vj是連通的。若圖G中的任意兩個頂點vi和vj都連通,即從vi到vj和從vj到vi都存在路徑,則稱圖G是強連通圖。例如,右邊兩個圖都是強連通圖。有向圖G中的極大強連通子圖稱為G的強連通分量。顯然,強連通圖只有一個強連通分量,即本身,非強連通圖有多個強連通分量。1210.權和網(wǎng)

圖中每一條邊都可以附有一個對應的數(shù)值,這種與邊相關的數(shù)值稱為權。權可以表示從一個頂點到另一個頂點的距離或花費的代價。邊上帶有權的圖稱為帶權圖,也稱作網(wǎng)。13

例有n個頂點的有向強連通圖最多需要多少條邊？最少需要多少條邊？

答：有n個頂點的有向強連通圖最多有n(n-1)條邊(構成一個有向完全圖的情況)；最少有n條邊(n個頂點依次首尾相接構成一個環(huán)的情況)。

148.2圖的存儲結構

8.2.1鄰接矩陣存儲方法鄰接矩陣是表示頂點之間相鄰關系的矩陣。設G=(V,E)是具有n(n＞0)個頂點的圖,頂點的順序依次為(v0,v1,…,vn-1),則G的鄰接矩陣A是n階方陣,其定義如下：

(1)如果G是無向圖,則：

(2)如果G是有向圖,則：

1516(3)如果G是帶權無向圖,則：

(4)如果G是帶權有向圖,則：

1718鄰接矩陣的特點如下：

(1)圖的鄰接矩陣表示是惟一的。

(2)無向圖的鄰接矩陣一定是一個對稱矩陣。因此,按照壓縮存儲的思想,在具體存放鄰接矩陣時只需存放上(或下)三角形陣的元素即可。

(3)不帶權的有向圖的鄰接矩陣一般來說是一個稀疏矩陣,因此,當圖的頂點較多時,可以采用三元組表的方法存儲鄰接矩陣。

(4)對于無向圖,鄰接矩陣的第i行(或第i列)非零元素(或非∞元素)的個數(shù)正好是第i個頂點vi的度。19

(5)對于有向圖,鄰接矩陣的第i行(或第i列)非零元素(或非∞元素)的個數(shù)正好是第i個頂點vi的出度(或入度)。

(6)用鄰接矩陣方法存儲圖,很容易確定圖中任意兩個頂點之間是否有邊相連。但是,要確定圖中有多少條邊,則必須按行、按列對每個元素進行檢測,所花費的時間代價很大。這是用鄰接矩陣存儲圖的局限性。20鄰接矩陣的數(shù)據(jù)類型定義如下：#defineMAXV<最大頂點個數(shù)>

typedefstruct{intno; /*頂點編號*/InfoTypeinfo; /*頂點其他信息*/}VertexType; /*頂點類型*/typedefstruct /*圖的定義*/{intedges[MAXV][MAXV]; /*鄰接矩陣*/intn,e; /*頂點數(shù),弧數(shù)*/VertexTypevexs[MAXV]; /*存放頂點信息*/}MGraph;21MGraphg;g:二維數(shù)組edgesne一維數(shù)組vexsedges[MAXV][MAXV]是鄰接矩陣vexs[MAXV]是頂點的數(shù)組228.2.2鄰接表存儲方法

圖的鄰接表存儲方法是一種順序分配與鏈式分配相結合的存儲方法。在鄰接表中,對圖中每個頂點建立一個單鏈表,第i個單鏈表中的結點表示依附于頂點vi的邊(對有向圖是以頂點vi為尾的弧)。每個單鏈表上附設一個表頭結點。表結點和表頭結點的結構如下：表結點表頭結點advexnextarcinfodatafirstarc23datafirstarcadvexnextarc24鄰接表的特點如下：

(1)鄰接表表示不惟一。這是因為在每個頂點對應的單鏈表中,各邊結點的鏈接次序可以是任意的,取決于建立鄰接表的算法以及邊的輸入次序。

(2)對于有n個頂點和e條邊的無向圖,其鄰接表有n個頂點結點和2e個邊結點。顯然,在總的邊數(shù)小于n(n-1)/2的情況下,鄰接表比鄰接矩陣要節(jié)省空間。

(3)對于無向圖,鄰接表的頂點vi對應的第i個鏈表的邊結點數(shù)目正好是頂點vi的度。

(4)對于有向圖,鄰接表的頂點vi對應的第i個鏈表的邊結點數(shù)目僅僅是vi的出度。其入度為鄰接表中所有adjvex域值為i的邊結點數(shù)目。25鄰接表存儲結構的定義如下：typedefstructANode /*弧的結點結構類型*/{ intadjvex;/*該弧的終點位置*/ structANode*nextarc;/*指向下一條弧的指針*/ InfoTypeinfo; /*該弧的相關信息*/}ArcNode;typedefstructVnode/*鄰接表頭結點的類型*/{ Vertexdata;/*頂點信息*/ ArcNode*firstarc;/*指向第一條弧*/}VNode;typedefVNodeAdjList[MAXV]; /*AdjList是鄰接表類型*/typedefstruct{ AdjListadjlist; /*鄰接表*/intn,e; /*圖中頂點數(shù)n和邊數(shù)e*/}ALGraph; /*圖的類型*/2627

例8.2給定一個具有n個結點的無向圖的鄰接矩陣和鄰接表。

(1)設計一個將鄰接矩陣轉換為鄰接表的算法；

(2)設計一個將鄰接表轉換為鄰接矩陣的算法；

(3)分析上述兩個算法的時間復雜度。解：(1)在鄰接矩陣上查找值不為0的元素,找到這樣的元素后創(chuàng)建一個表結點并在鄰接表對應的單鏈表中采用前插法插入該結點。算法如下：2829voidMatToList(MGraphg,ALGraph*&G)/*將鄰接矩陣g轉換成鄰接表G*/{inti,j,n=g.n;ArcNode*p; /*n為頂點數(shù)*/G=(ALGraph*)malloc(sizeof(ALGraph));for(i=0;i<n;i++)/*給所有頭結點的指針域置初值*/G->adjlist[i].firstarc=NULL;for(i=0;i<n;i++) /*檢查鄰接矩陣中每個元素*/for(j=n-1;j>=0;j--)if(g.edges[i][j]!=0) {p=(ArcNode*)malloc(sizeof(ArcNode));/*創(chuàng)建結點*p*/ p->adjvex=j; p->nextarc=G->adjlist[i].firstarc;/*將*p鏈到鏈表后*/ G->adjlist[i].firstarc=p; }G->n=n;G->e=g.e;}30

(2)在鄰接表上查找相鄰結點,找到后修改相應鄰接矩陣元素的值。算法如下：voidListToMat(ALGraph*G,MGraph&g){inti,j,n=G->n;ArcNode*p;for(i=0;i<n;i++)/*g.edges[i][j]賦初值0*/ for(j=0;j<n;j++)g.edges[i][j]=0;for(i=0;i<n;i++){p=G->adjlist[i].firstarc;while(p!=NULL) {g.edges[i][p->adjvex]=1; p=p->nextarc; }}g.n=n;g.e=G->e;}31

(3)上述兩個算法的時間復雜度均為O(n2)。對于(2)的算法,若不計算給a[i][j]賦初值0的雙重for循環(huán)語句,其時間復雜度為O(n+e),其中e為圖的邊數(shù)。328.3圖的遍歷8.3.1圖的遍歷的概念

從給定圖中任意指定的頂點(稱為初始點)出發(fā),按照某種搜索方法沿著圖的邊訪問圖中的所有頂點,使每個頂點僅被訪問一次,這個過程稱為圖的遍歷。如果給定圖是連通的無向圖或者是強連通的有向圖,則遍歷過程一次就能完成,并可按訪問的先后順序得到由該圖所有頂點組成的一個序列。根據(jù)搜索方法的不同,圖的遍歷方法有兩種：一種叫做深度優(yōu)先搜索法(DFS)；另一種叫做廣度優(yōu)先搜索法(BFS)。338.3.2深度優(yōu)先搜索遍歷

深度優(yōu)先搜索遍歷的過程是：從圖中某個初始頂點v出發(fā),首先訪問初始頂點v,然后選擇一個與頂點v相鄰且沒被訪問過的頂點w為初始頂點,再從w出發(fā)進行深度優(yōu)先搜索,直到圖中與當前頂點v鄰接的所有頂點都被訪問過為止。顯然,這個遍歷過程是個遞歸過程。以鄰接表為存儲結構的深度優(yōu)先搜索遍歷算法如下(其中,v是初始頂點編號,visited[]是一個全局數(shù)組,初始時所有元素均為0表示所有頂點尚未訪問過)：34voidDFS(ALGraph*G,intv){ArcNode*p;visited[v]=1; /*置已訪問標記*/printf("%d",v); /*輸出被訪問頂點的編號*/p=G->adjlist[v].firstarc; /*p指向頂點v的第一條弧的弧頭結點*/while(p!=NULL){if(visited[p->adjvex]==0)DFS(G,p->adjvex);

/*若p->adjvex頂點未訪問,遞歸訪問它*/ p=p->nextarc; /*p指向頂點v的下一條弧的弧頭結點*/}}35例如,以上圖的鄰接表為例調(diào)用DFS()函數(shù),假設初始頂點編號v=2,給出調(diào)用DFS()的執(zhí)行過程。36378.3.3廣度優(yōu)先搜索遍歷

廣度優(yōu)先搜索遍歷的過程是：首先訪問初始點vi,接著訪問vi的所有未被訪問過的鄰接點vi1,vi2,…,vit,然后再按照vi1,vi2,…,vit的次序,訪問每一個頂點的所有未被訪問過的鄰接點,依次類推,直到圖中所有和初始點vi有路徑相通的頂點都被訪問過為止。以鄰接表為存儲結構,用廣度優(yōu)先搜索遍歷圖時,需要使用一個隊列,以類似于按層次遍歷二叉樹遍歷圖。對應的算法如下(其中,v是初始頂點編號)：38voidBFS(ALGraph*G,intv){ArcNode*p;intw,i;intqueue[MAXV],front=0,rear=0; /*定義循環(huán)隊列*/intvisited[MAXV];/*定義存放結點的訪問標志的數(shù)組*/for(i=0;i<G->n;i++)visited[i]=0;/*訪問標志數(shù)組初始化*/printf("%2d",v);/*輸出被訪問頂點的編號*/visited[v]=1;/*置已訪問標記*/rear=(rear+1)%MAXV;queue[rear]=v; /*v進隊*/39

while(front!=rear) /*若隊列不空時循環(huán)*/ {front=(front+1)%MAXV; w=queue[front];/*出隊并賦給w*/

p=G->adjlist[w].firstarc;/*找w的第一個的鄰接點*/ while(p!=NULL) { if(visited[p->adjvex]==0)

{ printf(“%2d”,p->adjvex); /*訪問之*/

visited[p->adjvex]=1; rear=(rear+1)%MAXV;/*該頂點進隊*/

queue[rear]=p->adjvex; }

p=p->nextarc;/*找下一個鄰接頂點*/ } } printf("\n");}40例如,以上圖的鄰接表為例調(diào)用BFS()函數(shù),假設初始頂點編號v=2,給出調(diào)用BFS()的執(zhí)行過程。41428.3.4非連通圖的遍歷

對于無向圖來說,若無向圖是連通圖,則一次遍歷能夠訪問到圖中的所有頂點；但若無向圖是非連通圖,則只能訪問到初始點所在連通分量中的所有頂點,其他連通分量中的頂點是不可能訪問到的。為此需要從其他每個連通分量中選擇初始點,分別進行遍歷,才能夠訪問到圖中的所有頂點；

對于有向圖來說,若從初始點到圖中的每個頂點都有路徑,則能夠訪問到圖中的所有頂點；否則不能訪問到所有頂點,為此同樣需要再選初始點,繼續(xù)進行遍歷,直到圖中的所有頂點都被訪問過為止。43采用深度優(yōu)先搜索遍歷非連通無向圖的算法如下：DFS1(ALGraph*G){inti;for(i=0;i<G->n;i+)if(visited[i]==0) DFS(G,i);}44采用廣度優(yōu)先搜索遍歷非連通無向圖的算法如下：BFS1(ALGraph*G){inti;for(i=0;i<G->n;i+)if(visited[i]==0)BFS(G,i);}458.3.5圖遍歷算法的應用例8.3假設圖G采用鄰接表存儲，設計一個算法，判斷無向圖G是否連通。若連通則返回1；否則返回0.intConnect(ALGraph*G){inti,flag=1;for(i=0;i<G->n;i++)visited[i]=0;DFS(G,0);for(i=0;i<n;i++)if(visited[i]==0){flag=0;break;}returnflag;}46

例8.5假設圖G采用鄰接表存儲，設計一個算法輸出圖G中從頂點u到v的一條簡單路徑（假設圖G中從頂點u到v至少有一條簡單路徑）。解：采用深度優(yōu)先遍歷的方法。為此在深度優(yōu)先遍歷算法的基礎上增加v、path和d三個形參，其中path存放頂點u到v的路徑，d表示path中的路徑長度，其初值為-1。當從頂點u遍歷到頂點v后，輸出path并返回。voidFindaPath(AGraph*G,intu,intv,intpath[],intd);47voidFindaPath(AGraph*G,intu,intv,intpath[],intd){

//d表示path中的路徑長度，初始為-1intw,i;ArcNode*p;visited[u]=1;d++;path[d]=u; //路徑長度d增1，頂點u加入到路徑中

if(u==v) //找到一條路徑后輸出并返回

{printf("一條簡單路徑為:"); for(i=0;i<=d;i++)printf("%d",path[i]); printf("\n"); return;//找到一條路徑后返回

}p=G->adjlist[u].firstarc;//p指向頂點u的第一個相鄰點

while(p!=NULL){w=p->adjvex; //相鄰點的編號為w if(visited[w]==0) FindaPath(G,w,v,path,d); p=p->nextarc;//p指向頂點u的下一個相鄰點

}}48例8.7假設圖G采用鄰接表存儲，設計一個算法，輸出圖G中從頂點u到頂點v的長度為l

的所有簡單路徑。voidPathAll(ALGraph*G,intu,intv,intl,intpath[],intd)//d是到當前為止已經(jīng)走過的路徑長度。調(diào)用時初值為-1{intm,i;ArcNode*p;visited[u]=1;d++;path[d]=u;//將當前頂點添加到路徑中

if(u==v&&d==l

){cout<<“”;for(i=0;i<=d;i++)cout<<path[i]<<“”;cout<<endl;}49p=G->adjlist[u].firstarc;while(p!=NULL){m=p->adjvex;if(visited[m]==0)PathAll(G,m,v,l,path,d);p-p->nextarc;}visited[u]=0;//恢復環(huán)境，使得該頂點可重新使用}50主函數(shù)：viodmain(){intpath[MAXV],u,v,l,i,j;MGraphg;ALGraph*G;intA[MAXV][MAXV]={{0,1,0,1,0};{1,0,1,0,0};{0,1,0,1,1};{1,0,1,0,1};{0,0,1,1,0};};g.n=5;g.e=6;51for(i=0;i<g.n;i++)for(j=0;j<g.n;j++)g.edges[i][j]=A[i][j];MatToList(g,G);for(i=0;i<g.n;i++)visited[i]=0;printf(“圖G:”);DispAdj(G);//輸出鄰接表u=1;v=4;l=3;PathAll(G,u,v,l,path,-1);//輸出所有從u到v長度為l的路徑}528.4生成樹和最小生成樹8.4.1生成樹的概念

一個連通圖的生成樹是一個極小連通子圖,它含有圖中全部頂點,但只有構成一棵樹的(n-1)條邊。53

如果在一棵生成樹上添加一條邊,必定構成一個環(huán)：因為這條邊使得它依附的那兩個頂點之間有了第二條路徑。一棵有n個頂點的生成樹(連通無回路圖)有且僅有(n-1)條邊,如果一個圖有n個頂點和小于(n-1)條邊,則是非連通圖。如果它多于(n-1)條邊,則一定有回路。但是,有(n-1)條邊的圖不一定都是生成樹。54

對于一個帶權(假定每條邊上的權均為大于零的實數(shù))連通無向圖G中的不同生成樹,其每棵樹的所有邊上的權值之和也可能不同；圖的所有生成樹中具有邊上的權值之和最小的樹稱為圖的最小生成樹。按照生成樹的定義,n個頂點的連通圖的生成樹有n個頂點、n-1條邊。因此,構造最小生成樹的準則有三條：

(1)必須只使用該圖中的邊來構造最小生成樹；

(2)必須使用且僅使用n-1條邊來連接圖中的n個頂點；

(3)不能使用產(chǎn)生回路的邊。558.4.2無向圖的連通分量和生成樹

在對無向圖進行遍歷時,對于連通圖,僅需調(diào)用遍歷過程(DFS或BFS)一次,從圖中任一頂點出發(fā),便可以遍歷圖中的各個頂點。對非連通圖,則需多次調(diào)用遍歷過程,每次調(diào)用得到的頂點集連同相關的邊就構成圖的一個連通分量。設G=(V,E)為連通圖,則從圖中任一頂點出發(fā)遍歷圖時,必定將E(G)分成兩個集合T和B,其中T是遍歷圖過程中走過的邊的集合,B是剩余的邊的集合：T∩B=Φ,T∪B=E(G)。顯然,G'=(V,T)是G的極小連通子圖,即G'是G的一棵生成樹。

56

由深度優(yōu)先遍歷得到的生成樹稱為深度優(yōu)先生成樹；由廣度優(yōu)先遍歷得到的生成樹稱為廣度優(yōu)先生成樹。這樣的生成樹是由遍歷時訪問過的n個頂點和遍歷時經(jīng)歷的n-1條邊組成。對于非連通圖,每個連通分量中的頂點集和遍歷時走過的邊一起構成一棵生成樹,各個連通分量的生成樹組成非連通圖的生成森林。

578.4.3普里姆算法

普里姆(Prim)算法是求最小生成樹的一種構造性算法。假設G=(V,E)是一個具有n個頂點的帶權連通無向圖,T=(U,TE)是G的最小生成樹,其中U是T的頂點集,TE是T的邊集,則由G構造最小生成樹T的步驟如下：

(1)初始化={v0}。v0到其他頂點的所有邊為候選邊；

(2)重復以下步驟n-1次,使得其他n-1個頂點被加入到U中：①從候選邊中挑選權值最小的邊輸出,設該邊在V-U中的頂點是v,將v加入U中；②考察當前V-U中的所有頂點vi,修改候選邊：若(v,vi)的權值小于原來和vi關聯(lián)的候選邊,則用(v,vi)取代后者作為候選邊。58普里姆算法求解最小生成樹的過程59將帶權連通圖用帶權鄰接矩陣cost[n][n]存儲：60數(shù)組closest[0..n-1]存放生成樹的結點：若不在生成樹的頂點i與生成樹U中最接近的頂點j:Closest[i]=j數(shù)組lowcost[0..n-1]存放不在生成樹的頂點到生成樹U中最接近的頂點的邊的權值：Lowcost[i]=0若頂點i已經(jīng)是生成樹的頂點0<Lowcost[i]<∞若頂點i不是生成樹的頂點，此時，lowcost[i]=(i,closest[i])邊的權值lowcost[]={0,5,0,5,6,4}如:lowcost[5]=4點5到樹的最近值=4邊(5,2)=4Closest[]={_,2,_,2,2,2}如:closest[3]=2頂點3到樹中最近的點是2

61普里姆(Prim)算法如下：#defineINF32767/*INF表示∞*/voidPrim(intcost[][MAXV],intn,intv){intlowcost[MAXV],min;intclosest[MAXV],i,j,k;for(i=0;i<n;i++) /*給lowcost[]和closest[]置初值*/{lowcost[i]=cost[v][i];closest[i]=v; }62

for(i=1;i<n;i++) /*找出n-1個頂點*/ {min=INF; for(j=0;j<n;j++)/*在(V-U)中找出離U最近的頂點k*/ if(lowcost[j]!=0&&lowcost[j]<min){min=lowcost[j];k=j;}printf("邊(%d,%d)權為:%d\n",closest[k],k,min); lowcost[k]=0; /*標記k已經(jīng)加入U*/ for(j=0;j<n;j++) /*修改數(shù)組lowcost和closest*/if(cost[k][j]!=0&&cost[k][j]<lowcost[j]){lowcost[j]=cost[k][j];closest[j]=k;}}}63Prim()算法中有兩重for循環(huán),所以時間復雜度為O(n2)。

648.4.4克魯斯卡爾算法

克魯斯卡爾(Kruskal)算法是一種按權值的遞增次序選擇合適的邊來構造最小生成樹的方法。假設G=(V,E)是一個具有n個頂點的帶權連通無向圖,T=(U,TE)是G的最小生成樹,則構造最小生成樹的步驟如下：

(1)置U的初值等于V(即包含有G中的全部頂點),TE的初值為空集(即圖T中每一個頂點都構成一個分量)。

(2)將圖G中的邊按權值從小到大的順序依次選取：若選取的邊未使生成樹T形成回路,則加入TE；否則舍棄,直到TE中包含(n-1)條邊為止。65克魯斯卡爾算法求解最小生成樹的過程66

為了簡便,在實現(xiàn)克魯斯卡爾算法Kruskal()時,參數(shù)E存放圖G中的所有邊,假設它們是按權值從小到大的順序排列的。n為圖G的頂點個數(shù),e為圖G的邊數(shù)。

typedefstruct{ intu;/*邊的起始頂點*/ intv;/*邊的終止頂點*/ intw;/*邊的權值*/}Edge;

EdgeE[e]={{0,2,1},{3,5,2},{1,4,3},{2,5,4},{0,3,5},{2,3,5},{1,2,5},{0,1,6},{2,4,6},{4,5,6}};Kruskal()算法如下：67voidKruskal(EdgeE[],intn,inte){inti,j,m1,m2,sn1,sn2,k;intvset[MAXV];for(i=0;i<n;i++)vset[i]=i; /*初始化輔助數(shù)組*/k=1;/*k表示當前構造最小生成樹的第幾條邊,初值為1*/j=0;/*E中邊的下標,初值為0*/while(k<n)/*生成的邊數(shù)小于n時循環(huán)*/{m1=E[j].u;m2=E[j].v; /*取一條邊的頭尾頂點*/ sn1=vset[m1];sn2=vset[m2];/*分別得到兩個頂點所屬的集合編號*/68

if(sn1!=sn2) /*兩頂點屬于不同的集合,該邊是最小生成樹的一條邊*/ {printf("(%d,%d):%d\n",m1,m2,E[j].w); k++; /*生成邊數(shù)增1*/ for(i=0;i<n;i++)/*兩個集合統(tǒng)一編號*/ if(vset[i]==sn2)/*集合編號為sn2的改為sn1*/ vset[i]=sn1; } j++; /*掃描下一條邊*/}}

69

完整的克魯斯卡爾算法應包括對邊按權值遞增排序，上述算法假設邊已排序的情況下，時間復雜度為O(n2)。如果給定的帶權連通無向圖G有e條邊,n個頂點，采用堆排序(在第11章中介紹)對邊按權值遞增排序，那么用克魯斯卡爾算法構造最小生成樹的時間復雜度降為O(elog2e)。由于它與n無關，只與e有關，所以說克魯斯卡爾算法適合于稀疏圖。708.5最短路徑8.5.1路徑的概念

在一個無權的圖中,若從一頂點到另一頂點存在著一條路徑,則稱該路徑長度為該路徑上所經(jīng)過的邊的數(shù)目,它等于該路徑上的頂點數(shù)減1。由于從一頂點到另一頂點可能存在著多條路徑,每條路徑上所經(jīng)過的邊數(shù)可能不同,即路徑長度不同,我們把路徑長度最短(即經(jīng)過的邊數(shù)最少)的那條路徑叫做最短路徑,其路徑長度叫做最短路徑長度或最短距離。71

對于帶權的圖,考慮路徑上各邊上的權值,則通常把一條路徑上所經(jīng)邊的權值之和定義為該路徑的路徑長度或稱帶權路徑長度。從源點到終點可能不止一條路徑,把帶權路徑長度最短的那條路徑稱為最短路徑,其路徑長度(權值之和)稱為最短路徑長度或者最短距離。728.5.2從一個頂點到其余各頂點的最短路徑

問題：給定一個帶權有向圖G與源點v,求從v到G中其他頂點的最短路徑,并限定各邊上的權值大于或等于0。73

采用狄克斯特拉(Dijkstra)算法求解

基本思想是：設G=(V,E)是一個帶權有向圖,把圖中頂點集合V分成兩組：第一組為已求出最短路徑的頂點集合(用S表示,初始時S中只有一個源點,以后每求得一條最短路徑v,…vk,就將vk加入到集合S中,直到全部頂點都加入到S中,算法就結束了)

第二組為其余未確定最短路徑的頂點集合(用U表示)。按最短路徑長度的遞增次序依次把第二組的頂點加入S中。在加入的過程中,總保持從源點v到S中各頂點的最短路徑長度不大于從源點v到U中任何頂點的最短路徑長度。此外,每個頂點對應一個距離,S中的頂點的距離就是從v到此頂點的最短路徑長度,U中的頂點的距離從v到此頂點只包括S中的頂點為中間頂點的當前最短路徑長度。74狄克斯特拉算法的具體步驟如下：

(1)初始時,S只包含源點,即S={v},v到v的距離為0。U包含除v外的其他頂點,U中頂點u距離為邊上的權(若v與u有邊<v,u>)或∞(若u不是v的出邊鄰接點)。

(2)從U中選取一個距離最小的頂點k,把k加入S中(該選定的距離就是v到k的最短路徑長度)。

(3)以k為新考慮的中間點,修改U中各頂點的距離：若從源點v到頂點u(u∈U)的距離(經(jīng)過頂點k)比原來距離(不經(jīng)過頂點k)短,則修改頂點u的距離值,修改后的距離值的頂點k的距離加上邊<k,u>上的權。

(4)重復步驟(2)和(3)直到所有頂點都包含在S中。75S U v0到0～6各頂點的距離dist[]{0} {1,2,3,4,5,6}{0,4,6,6,∞,∞,∞}{0,1}{2,3,4,5,6}{0,4,5,6,11,∞,∞}{0,1,2}{3,4,5,6} {0,4,5,6,11,9,∞}{0,1,2,3}{4,5,6} {0,4,5,6,11,9,15}{0,1,2,3,5}{4,6} {0,4,5,6,10,9,17}{0,1,2,3,5,4} {6} {0,4,5,6,10,9,16}{0,1,2,3,5,4,6}{} {0,4,5,6,10,9,16}

則v0到v1～v6各頂點的最短距離分別為4、5、6、10、9和16。已求最短距離的頂點集未知最短距離的頂點集76數(shù)組dist[]=從源點v0到每個點的最短路徑長度

dist[i]=x從源點v0到點vi的最短路徑長度x數(shù)組Path[]=從源點v0到每個點i的最短路徑中點i的直接前驅(qū)點Path[i]=k從源點v0到點i的最短路徑中點i的直接前驅(qū)點k例:源點v0=0dist[6]=160—1---2---5---4---6path[6]=4,path[4]=5path[5]=2path[2]=1path[1]=0path[0]=-177狄克斯特拉算法(n為圖G的頂點數(shù),v0為源點編號)：voidDijkstra(MGraphg,intv0){intdist[MAXV],path[MAXV];ints[MAXV];intmindis,i,j,u;for(i=0;i<g.n;i++){dist[i]=g.edges[v0][i]; /*距離初始化*/ s[i]=0; /*s[]置空*/ if(g.edges[v0][i]<INF) /*路徑初始化*/

path[i]=v0; else

path[i]=-1; } s[v0]=1;path[v0]=0; /*源點編號v0放入s中*/78

for(i=0;i<g.n;i++)/*循環(huán)直到所有頂點的最短路徑都求出*/{mindis=INF; u=-1; for(j=0;j<g.n;j++)//選取不在s中且具有最小距離的頂點u if(s[j]==0&&dist[j]<mindis) {u=j;mindis=dist[j]; } s[u]=1; /*頂點u加入s中*/ for(j=0;j<g.n;j++)/*修改不在s中的頂點的距離*/ if(s[j]==0) if(g.edges[u][j]<INF&&dist[u]+g.edges[u][j]<dist[j])

{dist[j]=dist[u]+g.edges[u][j];path[j]=u;}

}Dispath(dist,path,s,g.n,v0); /*輸出最短路徑*/}

79voidPpath(intpath[],inti,intv0)/*前向遞歸查找路徑上的頂點*/{intk;k=path[i];if(k==v0)return; /*找到了起點則返回*/Ppath(path,k,v0); /*找k頂點的前一個頂點*/printf("%d,",k); /*輸出k頂點*/}80voidDispath(intdist[],intpath[],ints[],intn,intv0){inti;for(i=0;i<n;i++) if(s[i]==1) {printf(“從%d到%d的最短路徑長度為:%d\t路徑為:",v0,i,dist[i]); printf("%d,",v0); /*輸出路徑上的起點*/Ppath(path,i,v0); /*輸出路徑上的中間點*/printf("%d\n",i); /*輸出路徑上的終點*/ } elseprintf("從%d到%d不存在路徑\n",v0,i);}818.5.3每對頂點之間的最短路徑

問題：對于一個各邊權值均大于零的有向圖,對每一對頂點vi≠vj,求出vi與vj之間的最短路徑和最短路徑長度?？梢酝ㄟ^以每個頂點作為源點循環(huán)求出每對頂點之間的最短路徑。除此之外,弗洛伊德(Floyd)算法也可用于求兩頂點之間最短路徑。

82

假設有向圖G=(V,E)采用鄰接矩陣cost存儲,另外設置一個二維數(shù)組A用于存放當前頂點之間的最短路徑長度,分量A[i][j]表示當前頂點vi到頂點vj的最短路徑長度。弗洛伊德算法的基本思想是遞推產(chǎn)生一個矩陣序列A0,A1,…,Ak,…,An,其中Ak[i][j]表示從頂點vi到頂點vj的路徑上所經(jīng)過的頂點編號不大于k的最短路徑長度。83

初始時,有A-1[i][j]=cost[i][j]。當求從頂點vi到頂點vj的路徑上所經(jīng)過的頂點編號不大于k+1的最短路徑長度時,要分兩種情況考慮：一種情況是該路徑不經(jīng)過頂點編號為k+1的頂點,此時該路徑長度與從頂點vi到頂點vj的路徑上所經(jīng)過的頂點編號不大于k的最短路徑長度相同；另一種情況是從頂點vi到頂點vj的最短路徑上經(jīng)過編號為k+1的頂點。那么,該路徑可分為兩段,一段是從頂點vi到頂點vk+1的最短路徑,另一段是從頂點vk+1到頂點vj的最短路徑,此時最短路徑長度等于這兩段路徑長度之和。這兩種情況中的較小值,就是所要求的從頂點vi到頂點vj的路徑上所經(jīng)過的頂點編號不大于k+1的最短路徑。84

弗洛伊德思想可用如下的表達式來描述：

A-1[i][j]=g.edges[i][j]Ak[i][j]=min{Ak-1[i][j],Ak-1[i][k]+Ak-1[k][j]}(0≤k≤n-1)

Pathk[i][j]=從點i到點j的(中間頂點的編號不超過k的)最短路徑中頂點j的前一個頂點編號85

采用弗洛伊德算法求解過程86

考慮頂點v0,A0[i][j]表示由vi到vj,經(jīng)由頂點v0的最短路徑。只有從v2到v1經(jīng)過v0的路徑和從v2到v3經(jīng)過v0的路徑,不影響v2到v1和v2到v3的路徑長度,因此,有：

87

考慮頂點v1,A1[i][j]表示由vi到vj,經(jīng)由頂點v1的最短路徑。存在路徑v0-v1-v2,路徑長度為9,將A[0][2]改為9,path[0][2]改為1,因此,有：88考慮頂點v2,A2[i][j]表示由vi到vj,經(jīng)由頂點v2的最短路徑。存在路徑v3-v2-v0,長度為4,將A[3][0]改為4；存在路徑v3-v2-v1,長度為4,將A[3][1]改為4。存在路徑v1-v2-v0,長度為7,將A[1][0]改為7。將path[3][0]、path[3][1]和path[1][0]均改為2。因此,有：

89

考慮頂點v3,A3[i][j]表示由vi到vj,經(jīng)由頂點v3的最短路徑。存在路徑v0-v3-v2,長度為8比原長度短,將A[0][2]改為8；存在路徑v1-v3-v2-v0,長度為6(A[1][3]+A[3][0]=2+4=6)比原長度短,將A[1][0]改為6；存在路徑v1-v3-v2,長度為3,比原長度短,將A[1][2]改為3；將path[0][2]、path[1][0]后path[1][2]均改為3。因此,有：90

因此,最后求得的各頂點最短路徑長度A和Path矩陣為：

從0到0路徑為：0,0 路徑長度為：0從0到1路徑為：0,1 路徑長度為：5從0到2路徑為：0,3,2 路徑長度為：8從0到3路徑為：0,3 路徑長度為：7從1到0路徑為：1,3,2,0 路徑長度為：6從1到1路徑為：1,1 路徑長度為：0從1到2路徑為：1,3,2 路徑長度為：3從1到3路徑為：1,3 路徑長度為：291從2到0路徑為：2,0 路徑長度為：3從2到1路徑為：2,1 路徑長度為：3從2到2路徑為：2,2 路徑長度為：0從2到3路徑為：2,3 路徑長度為：2從3到0路徑為：3,2,0 路徑長度為：4從3到1路徑為：3,2,1 路徑長度為：4從3到2路徑為：3,2 路徑長度為：1從3到3路徑為：3,3 路徑長度為：092弗洛伊德算法如下：voidFloyd(MGraphg){intA[MAXV][MAXV],path[MAXV][MAXV];inti,j,k;for(i=0;i<g.n;i++) for(j=0;j<g.n;j++){A[i][j]=g.edges[i][j];if(i!=j&&g.edges[i][j]<INF)path[i][j]=i;elsepath[i][j]=-1;}93for(k=0;k<g.n;k++){for(i=0;i<g.n;i++)for(j=0;j<g.n;j++) if(A[i][j]>(A[i][k]+A[k][j])){A[i][j]=A[i][k]+A[k][j];path[i][j]=path[k][j];}}Dispath(g,A,path);/*輸出最短路徑*/}

948.6拓撲排序

設G=(V,E)是一個具有n個頂點的有向圖,V中頂點序列v1,v2,…,vn稱為一個拓撲序列,當且僅當該頂點序列滿足下列條件：若<vi,vj>是圖中的邊(即從頂點vi到vj有一條路徑),則在序列中頂點vi必須排在頂點vj之前。在一個有向圖中找一個拓撲序列的過程稱為拓撲排序。例如,計算機專業(yè)的學生必須完成一系列規(guī)定的基礎課和專業(yè)課才能畢業(yè),假設這些課程的名稱與相應代號有如下關系：95課程代號課程名稱先修課程C1高等數(shù)學無C2程序設計無C3離散數(shù)學C1C4數(shù)據(jù)結構C2,C3C5編譯原理C2,C4C6操作系統(tǒng)C4,C7C7計算機組成原理C296課程之間的先后關系可用有向圖表示：課程代號課程名稱先修課程C1高等數(shù)學無C2程序設計無C3離散數(shù)學C1C4數(shù)據(jù)結構C2,C3C5編譯原理C2,C4C6操作系統(tǒng)C4,C7C7計算機組成原理C297

對這個有向圖進行拓撲排序可得到一個拓撲序列：C1-C3-C2-C4-C7-C6-C5。也可得到另一個拓撲序列：C2-C7-C1-C3-C4-C5-C6,還可以得到其他的拓撲序列。學生按照任何一個拓撲序列都可以順序地進行課程學習。98

拓撲排序方法如下：

(1)從有向圖中選擇一個沒有前驅(qū)(即入度為0)的頂點并且輸出它。

(2)從有向圖中刪去該頂點,并且刪去從該頂點發(fā)出的全部有向邊。

(3)重復上述兩步,直到剩余的有向圖中不再存在沒有前驅(qū)(入度為0)的頂點為止。99

為了實現(xiàn)拓撲排序的算法,對于給定的有向圖,采用鄰接表作為存儲結構,為每個頂點設立一個鏈表,每個鏈表有一個表頭結點,這些表頭結點構成一個數(shù)組,表頭結點中增加一個存放頂點入度的域count。即將鄰接表定義中的VNode類型修改如下：

typedefstruct /*表頭結點類型*/{Vertexdata; /*頂點信息*/

intcount; /*存放頂點入度*/ArcNode*firstarc;/*指向第一條弧*/}VNode;100voidTopSort(VNodeadj[],intn){inti,j;intSt[MAXV],top=-1;/*棧St的指針為top*/ArcNode*p;for(i=0;i<n;i++)if(adj[i].count==0) /*入度為0的頂點入棧*/ {top++;St[top]=i;}while(top>-1)/*棧不為空時循環(huán)*/{i=St[top];top--; /*出棧*/printf("%d",i);p=adj[i].firstarc;while(p!=NULL){j=p->adjvex;adj[j].count--;if(adj[j].count==0) {top++;St[top]=j;}p=p->nextarc; /*找下一個相鄰頂點*/ }}}1018.7AOE網(wǎng)與關鍵路徑

若用前面介紹過的帶權有向圖(DAG)描述工程的預計進度,以頂點表示事件,有向邊表示活動,邊e的權c(e)表示完成活動e所需的時間(比如天數(shù)),或者說活動e持續(xù)時間。圖中入度為0的頂點表示工程的開始事件(如開工儀式),出度為0的頂點表示工程結束事件。則稱這樣的有向圖為AOE網(wǎng)(ActivityOnEdge)。

102

通常每個工程都只有一個開始事件和一個結束事件,因此表示工程的AOE網(wǎng)都只有一個入度為0的頂點,稱為源點(source),和一個出度為0的頂點,稱為匯點(converge)。如果圖中存在多個入度為0的頂點,只要加一個虛擬源點,使這個虛擬源點到原來所有入度為0的點都有一條長度為0的邊,變成只有一個源點。對存在多個出度為0的頂點的情況作類似的處理。所以只需討論單源點和單匯點的情況。

103

在AOE網(wǎng)中,從源點到匯點的所有路徑中,具有最大路徑長度的路徑稱為關鍵路徑。完成整個工程的最短時間就是網(wǎng)中關鍵路徑的長度,也就是網(wǎng)中關鍵路徑上各活動持續(xù)時間的總和,我們把關鍵路徑上的活動稱為關鍵活動。因此,只要找出AOE網(wǎng)中的關鍵活動,也就找到了關鍵路徑。注意:在一個AOE網(wǎng)中,可以有不止一條的關鍵路徑。

104

例如,下圖表示某工程的AOE網(wǎng)。共有9個事件和11項活動。其中A表示開始事件,G表示結束事件。105幾個定義：

(1)事件v的最早可發(fā)生時間：假設事件x是源點,事件y為匯點,并規(guī)定事件x的發(fā)生時間為0。定義圖中任一事件v的最早(eventearly)可發(fā)生時間ve(v)等于x到v所有路徑長度的最大值,即：

ve(v)=

上式中的MAX是對x到v的所有路徑p取最大值,c(p)表示路徑p的長度(路徑上邊長之和),即：c(p)=

完成整個工程所需的最少時間,等于事件y的最早可發(fā)生時間ve(y)。

106

(2)

事件v的最遲可發(fā)生時間：定義在不影響整個工程進度的前提下,事件v必須發(fā)生的時間稱為v的最遲(eventlate)可發(fā)生時間,記作vl(v)。vl(v)應等于ve(y)與v到y(tǒng)的最長路徑長度之差(y是匯點),即：

vl(v)=ve(y)-