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

9.1圖的基本概念第8章圖9.2圖的存儲結構9.3圖的遍歷9.4生成樹和最小生成樹9.5最短路徑9.6拓撲排序本章小結9.7AOE網(wǎng)與關鍵路徑

(3)圖形結構

結點之間關系：N：M，多對多。

特點：沒有開始結點和終端結點，所有結點都可能有多個前驅(qū)結點和多個后繼結點。abcdfe9.1圖的基本概念9.1.1圖的定義

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

在圖G中,如果代表邊的頂點對是無序的,則稱G為無向圖,無向圖中代表邊的無序頂點對通常用圓括號括起來,用以表示一條無向邊，如（i，j）。如果表示邊的頂點對是有序的,則稱G為有向圖,在有向圖中代表邊的頂點對通常用尖括號括起來,如<i，j>。9.1.2圖的基本術語

1.端點和鄰接點在一個無向圖中,若存在一條邊(vi,vj),則稱vi和vj為此邊的兩個端點,并稱它們互為鄰接點。在一個有向圖中,若存在一條邊<vi,vj>,則稱此邊是頂點vi的一條出邊,同時也是頂點vj的一條入邊；稱vi和vj分別為此邊的起始端點(簡稱為起點)和終止端點(簡稱終點)；稱vi和vj互為鄰接點。2.頂點的度、入度和出度在無向圖中,頂點所具有的邊的數(shù)目稱為該頂點的度。在有向圖中,以頂點vi為終點的入邊的數(shù)目,稱為該頂點的入度。以頂點vi為始點的出邊的數(shù)目,稱為該頂點的出度。一個頂點的入度與出度的和為該頂點的度。若一個圖中有n個頂點和e條邊,每個頂點的度為di(1≤i≤n),則有：3.完全圖若無向圖中的每兩個頂點之間都存在著一條邊,有向圖中的每兩個頂點之間都存在著方向相反的兩條邊,則稱此圖為完全圖。顯然,完全無向圖包含有n(n-1)/2條邊,完全有向圖包含有n(n-1)條邊。例如,圖(a)所示的圖是一個具有4個頂點的完全無向圖,共有6條邊。圖(b)所示的圖是一個具有4個頂點的完全有向圖,共有12條邊。

4.稠密圖、稀疏圖當一個圖接近完全圖時,則稱為稠密圖。相反,當一個圖含有較少的邊數(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)的子圖。6.路徑和路徑長度在一個圖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。7.回路或環(huán)若一條路徑上的開始點與結束點為同一個頂點,則此路徑被稱為回路或環(huán)。開始點與結束點相同的簡單路徑被稱為簡單回路或簡單環(huán)。例如,右圖中,(v0,v2,v1,v0)就是一條簡單回路,其長度為3。8.連通、連通圖和連通分量在無向圖G中,若從頂點vi到頂點vj有路徑,則稱vi和vj是連通的。若圖G中任意兩個頂點都連通,則稱G為連通圖,否則稱為非連通圖。無向圖G中的極大連通子圖稱為G的連通分量。顯然,任何連通圖的連通分量只有一個,即本身,而非連通圖有多個連通分量。9.強連通圖和強連通分量在有向圖G中,若從頂點vi到頂點vj有路徑,則稱從vi到vj是連通的。若圖G中的任意兩個頂點vi和vj都連通,即從vi到vj和從vj到vi都存在路徑,則稱圖G是強連通圖。例如,右邊兩個圖都是強連通圖。有向圖G中的極大強連通子圖稱為G的強連通分量。顯然,強連通圖只有一個強連通分量,即本身,非強連通圖有多個強連通分量。10.權和網(wǎng)圖中每一條邊都可以附有一個對應的數(shù)值,這種與邊相關的數(shù)值稱為權。權可以表示從一個頂點到另一個頂點的距離或花費的代價。邊上帶有權的圖稱為帶權圖,也稱作網(wǎng)。

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

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

9.2圖的存儲結構

9.2.1鄰接矩陣存儲方法

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

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

A[i][j]=1:若(vi,vj)∈E(G)0:其他

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

A[i][j]=1:若<vi,vj>∈E(G)0:其他(3)如果G是帶權無向圖,則：

A[i][j]=wij:若vi≠vj且(vi,vj)∈E(G)0:i=j∞:其他(4)如果G是帶權有向圖,則：

A[i][j]=wij:若vi≠vj且<vi,vj>∈E(G)0:i=j∞:其他鄰接矩陣的特點如下：

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

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

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

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

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

(6)用鄰接矩陣方法存儲圖,很容易確定圖中任意兩個頂點之間是否有邊相連。但是,要確定圖中有多少條邊,則必須按行、按列對每個元素進行檢測,所花費的時間代價很大。這是用鄰接矩陣存儲圖的局限性。鄰接矩陣的數(shù)據(jù)類型定義如下：#defineMAXV<最大頂點個數(shù)> typedefstruct{intno; /*頂點編號*/InfoTypeinfo; /*頂點其他信息*/}VertexType; /*頂點類型*/typedefstruct /*圖的定義*/{intedges[MAXV][MAXV]; /*鄰接矩陣*/intvexnum,arcnum; /*頂點數(shù),弧數(shù)*/VertexTypevexs[MAXV]; /*存放頂點信息*/}MGraph;9.2.2鄰接表存儲方法

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

adjvex指與頂點vi鄰接的頂點的編號nextarc指向下一條邊或弧的結點,info存儲與邊或弧相關的信息,如權值等。data存儲頂點vi的名稱或其他信息,firstarc指向鏈表中第一個結點。adjvexnextarcinfodatafirstarc表結點表頭結點鄰接表的特點如下：

(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ù)目。鄰接表存儲結構的定義如下：typedefstructANode /*弧的結點結構類型*/{ intadjvex;/*該弧的終點位置*/ structANode*nextarc;/*指向下一條弧的指針*/ InfoTypeinfo; /*該弧的相關信息*/}ArcNode;typedefstructVnode/*鄰接表頭結點的類型*/{ Vertexdata; /*頂點信息*/ ArcNode*firstarc;/*指向第一條弧*/}VNode;typedefVNodeAdjList[MAXV]; /*AdjList是鄰接表類型*/typedefstruct{ AdjListadjlist; /*鄰接表*/intn,e; /*圖中頂點數(shù)n和邊數(shù)e*/}ALGraph; /*圖的類型*/

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

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

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

(3)分析上述兩個算法的時間復雜度。解：(1)在鄰接矩陣上查找值不為0的元素,找到這樣的元素后創(chuàng)建一個表結點并在鄰接表對應的單鏈表中采用前插法插入該結點。算法如下：voidMatToList(MGraphg,ALGraph*&G)/*將鄰接矩陣g轉(zhuǎn)換成鄰接表G*/{inti,j,n=g.vexnum;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.arcnum;}

(2)在鄰接表上查找相鄰結點,找到后修改相應鄰接矩陣元素的值。算法如下：

voidListToMat(ALGraph*G,MGraph&g){inti,j,n=G->n;ArcNode*p;for(i=0;i<n;i++){p=G->adjlist[i].firstarc;while(p!=NULL) {g.edges[i][p->adjvex]=1; p=p->nextarc; }}g.vexnum=n;g.arcnum=G->e;}

(3)算法1的時間復雜度均為O(n2)。算法2的時間復雜度為O(n+e),其中e為圖的邊數(shù)。9.3圖的遍歷9.3.1圖的遍歷的概念

從給定圖中任意指定的頂點(稱為初始點)出發(fā),按照某種搜索方法沿著圖的邊訪問圖中的所有頂點,使每個頂點僅被訪問一次,這個過程稱為圖的遍歷。

如果給定圖是連通的無向圖或者是強連通的有向圖,則遍歷過程一次就能完成,并可按訪問的先后順序得到由該圖所有頂點組成的一個序列。根據(jù)搜索方法的不同,圖的遍歷方法有兩種：一種叫做深度優(yōu)先搜索法(DFS)；另一種叫做廣度優(yōu)先搜索法(BFS)。

9.3.2深度優(yōu)先搜索遍歷

深度優(yōu)先搜索遍歷的過程是：從圖中某個初始頂點v出發(fā),首先訪問初始頂點v,然后選擇一個與頂點v相鄰且沒被訪問過的頂點w為初始頂點,再從w出發(fā)進行深度優(yōu)先搜索,直到圖中與當前頂點v鄰接的所有頂點都被訪問過為止。

例如,以上圖的鄰接表為例調(diào)用DFS()函數(shù),假設初始頂點編號v=2,見教材205。9.3.2深度優(yōu)先搜索遍歷以鄰接表為存儲結構的深度優(yōu)先搜索遍歷算法如下(其中,v是初始頂點編號,visited[]是一個全局數(shù)組,初始時所有元素均為0表示所有頂點尚未訪問過)：

voidDFS(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的下一條弧的弧頭結點*/}}9.3.3廣度優(yōu)先搜索遍歷

廣度優(yōu)先搜索遍歷的過程是：首先訪問初始點vi,接著訪問vi的所有未被訪問過的鄰接點vi1,vi2,…,vit,然后再按照vi1,vi2,…,vit的次序,訪問每一個頂點的所有未被訪問過的鄰接點,依次類推,直到圖中所有和初始點vi有路徑相通的頂點都被訪問過為止。

例如,以上圖的鄰接表為例調(diào)用BFS()函數(shù),假設初始頂點編號v=2,見教材206。9.3.3廣度優(yōu)先搜索遍歷以鄰接表為存儲結構,用廣度優(yōu)先搜索遍歷圖時,需要使用一個隊列,以類似于按層次遍歷二叉樹遍歷圖。對應的算法如下(其中,v是初始頂點編號)：

voidBFS(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進隊*/

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");}9.3.4非連通圖的遍歷

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

對于有向圖來說,若從初始點到圖中的每個頂點都有路徑,則能夠訪問到圖中的所有頂點；否則不能訪問到所有頂點,為此同樣需要再選初始點,繼續(xù)進行遍歷,直到圖中的所有頂點都被訪問過為止。采用深度優(yōu)先搜索遍歷非連通無向圖的算法如下：DFS1(ALGraph*g){inti;for(i=0;i<g->n;i+)/*遍歷所有未訪問過的頂點*/if(visited[i]==0)DFS(g,i);}采用廣度優(yōu)先搜索遍歷非連通無向圖的算法如下：BFS1(ALGraph*g){inti;for(i=0;i<g->n;i+)/*遍歷所有未訪問過的頂點*/if(visited[i]==0)BFS(g,i);}9.4生成樹和最小生成樹9.4.1生成樹的概念

一個連通圖的生成樹是一個極小連通子圖,它含有圖中全部頂點,但只有構成一棵樹的(n-1)條邊。如果在一棵生成樹上添加一條邊,必定構成一個環(huán)：因為這條邊使得它依附的那兩個頂點之間有了第二條路徑。

一棵有n個頂點的生成樹(連通無回路圖)有且僅有(n-1)條邊,如果一個圖有n個頂點和小于(n-1)條邊,則是非連通圖。如果它多于(n-1)條邊,則一定有回路。但是,有(n-1)條邊的圖不一定都是生成樹。

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

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

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

(3)不能使用產(chǎn)生回路的邊。9.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的一棵生成樹。

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

普里姆(Prim)算法是一種構造性算法。假設G=(V,E)是一個具有n個頂點的帶權連通無向圖,T=(U,TE)是G的最小生成樹,其中U是T的頂點集,TE是T的邊集,則由G構造最小生成樹T的步驟如下：(1)初始化U={v0}。v0到其他頂點的所有邊為候選邊；

(2)重復以下步驟n-1次,使得其他n-1個頂點被加入到U中：①從候選邊中挑選權值最小的邊輸出,設該邊在V-U中的頂點是v,將v加入U中；②考察當前V-U中的所有頂點vi,修改候選邊：若(v,vi)的權值小于原來和vi關聯(lián)的候選邊,則用(v,vi)取代后者作為候選邊。普里姆算法求解最小生成樹的過程9.4.5克魯斯卡爾算法

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

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

(2)將圖G中的邊按權值從小到大的順序依次選?。喝暨x取的邊未使生成樹T形成回路,則加入TE；否則舍棄,直到TE中包含(n-1)條邊為止?？唆斔箍査惴ㄇ蠼庾钚∩蓸涞倪^程9.5最短路徑9.5.1路徑的概念

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

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

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

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

第二組為其余未確定最短路徑的頂點集合(用U表示)。

按最短路徑長度的遞增次序依次把第二組的頂點加入S中。在加入的過程中,總保持從源點v到S中各頂點的最短路徑長度不大于從源點v到U中任何頂點的最短路徑長度。此外,每個頂點對應一個距離,S中的頂點的距離就是從v到此頂點的最短路徑長度,U中的頂點的距離從v到此頂點只包括S中的頂點為中間頂點的當前最短路徑長度。

狄克斯特拉算法的具體步驟如下：

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

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

(3)以k為新考慮的中間點,修改U中各頂點的距離：若從源點v到頂點u(u∈U)的距離(經(jīng)過頂點k,cvk+wku)比原來距離(不經(jīng)過頂點k，cvu)短,則修改頂點u的距離值為cvk+wku

。

(4)重復步驟(2)和(3)直到所有頂點都包含在S中。V到j的最小距離＝MIN(cvk+wkj,cvj)S U dist[]path[]01234560123456{0} {1,2,3,4,5,6}{0,4,6,6,∞,∞,∞}{0,0,0,0,-1,-1,-1}{0,1}{2,3,4,5,6}{0,4,5,6,11,∞,∞}{0,0,1,0,1,-1,-1}{0,1,2}{3,4,5,6} {0,4,5,6,11,9,∞}{0,0,1,0,1,2,-1}{0,1,2,3}{4,5,6} {0,4,5,6,11,9,∞}{0,0,1,0,1,2,-1}{0,1,2,3,5}{4,6} {0,4,5,6,10,9,17}{0,0,1,0,5,2,5}{0,1,2,3,5,4} {6} {0,4,5,6,10,9,16}{0,0,1,0,5,2,4}{0,1,2,3,5,4,6}{} {0,4,5,6,10,9,16}{0,0,1,0,5,2,4}8.5.3每對頂點之間的最短路徑

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

假設有向圖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的最短路徑長度。

初始時,有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的頂點。Ak+1[i,j]=MIN(Ak[i,j],Ak[i,k+1]+Ak[k+1,j]

那么,該路徑可分為兩段:(1)從頂點vi到頂點vk+1的最短路徑;(2)從頂點vk+1到頂點vj的最短路徑。此時最短路徑長度等于這兩段路徑長度之和。這兩種情況中的較小值,就是所要求的從頂點vi到頂點vj的路徑上所經(jīng)過的頂點編號不大于k+1的最短路徑。

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

A-1[i][j]=cost[i][j]Ak+1[i][j]=MIN{Ak[i][j],Ak[i][k+1]+Ak[k+1][j]}(0≤k≤n-1)

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

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

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

考慮頂點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。因此,有：

考慮頂點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。因此,有：

從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 路徑長度為：2A=Path=從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 路徑長度為：09.6拓撲排序

設G=(V,E)是一個具有n個頂點的有向圖,V中頂點序列v1,v2,…,vn稱為一個拓撲序列,當且僅當該頂點序列滿足下列條件：

若<vi,vj>是圖中的邊(即從頂點vi到vj有一條路徑),則在序列中頂點vi必須排在頂點vj之前。在一個有向圖中找一個拓撲序列的過程稱為拓撲排序。課程代號課程名稱先修課程C1高等數(shù)學無C2程序設計無C3離散數(shù)學C1C4數(shù)據(jù)結構C2,C3C5編譯原理C2,C4C6操作系統(tǒng)C4,C7C7計算機組成原理C2

例如,計算機專業(yè)的學生必須完成一系列規(guī)定的基礎課和專業(yè)課才能畢業(yè),假設這些課程的名稱與相應代號有如下關系：課程之間的先后關系可用有向圖表示：

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

拓撲排序方法如下：

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

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

(3)重復上述兩步,直到剩余的網(wǎng)中不再存在沒有前驅(qū)的頂點為止。

為了實現(xiàn)拓撲排序的算法,對于給定的有向圖,采用鄰接表作為存儲結構,為每個頂點設立一個鏈表,每個鏈表有一個表頭結點,這些表頭結點構成一個數(shù)組,