第7章圖圖是一種比線性表和樹更加復雜的數據結構。在線性表中，數據元素之間呈現一種線性關系，即每個元素只有一個直接前驅和一個直接后繼；在樹結構中，結點之間是一種層次關系，即每個結點只有一個直接前驅，但可有多個直接后繼；而在圖結構中，每個結點既可以有多個直接前驅，也可以有多個直接后繼圖結構可以描述各種復雜的數據對象，圖的應用已滲入到諸如語言學、邏輯學、物理、化學、電訊工程、計算機科學以及數學的其它分支中本章首先介紹圖的概念，然后討論圖在計算機中的表示方法以及有關圖的幾個典型應用及相應的算法圖的基本概念圖的存儲結構圖的遍歷圖的最小生成樹最短路徑有向無環(huán)圖及其應用5．1圖的基本概念圖的定義

圖是由頂點集合(vertex)及頂點間的關系集合組成的一種數據結構：

Graph＝(V,E)

其中

V

是頂點的有窮非空集合；

E

是頂點之間關系的有窮集合，也叫做邊(edge)集合無向圖

在無向圖中,頂點對(vi,vj)是無序的，(vi,vj)表示頂點vi和vj間相連的邊;v0v1v4v3v2無向圖G1v0v1v2v3有向圖G2有向圖

在有向圖中,頂點對<vi,vj>是有序的，<vi,vj>表示從頂點vi到頂點vj的一條弧,并稱vi為弧尾（或初始點），稱vj為弧頭（或終端點）圖的基本術語鄰接點、相關邊對于無向圖G=(V,E)，若邊(vi,vj)∈E，則稱vi和vj互為鄰接點(Adjacent)，邊(vi,vj)則是與頂點vi和vj相關聯的邊。對于有向圖G=(V,A)，若弧<vi,vj>∈A，則稱頂點vi鄰接到頂點vj，頂點vj鄰接自頂點vi，弧<vi,vj>和頂點vi、vj相關聯

在下面的討論中，不考慮頂點到其自身的邊或弧，也不允許一條邊或弧在圖中重復出現。同時用n表示圖中頂點的數目，用e表示邊或弧的數目v1v4v3v2v1v3v2完全圖若有n

個頂點的無向圖有n(n-1)/2

條邊,則此圖為完全無向圖。有n

個頂點的有向圖有n(n-1)

條邊,則此圖為完全有向圖子圖設有兩個圖G＝(V,E)

和G’＝(V’,E’),若V’V且E’E,則稱圖G’是圖G的子圖

v0v1v4v3v2無向圖G1v1v4v3v2子圖G1’頂點的度（Degree）圖中和vi相關聯的邊的數目，記為TD(vi)。在有向圖中,頂點的度等于該頂點的入度與出度之和頂點vi的入度指以vi為頭的弧的數目，記為ID(vi)頂點vi的出度(OutDegree)

指以vi為尾的弧的數目，記為OD(vi)有n個頂點，e條邊或弧的圖，滿足如下關系路徑在圖G＝(V,E)中,若從頂點vi出發(fā),沿一些邊(或弧)經過一些頂點vp1,vp2,…,vpm

到達頂點vj。則稱頂點序列(vi,vp1,vp2,...,vpm,vj)為從頂點vi到頂點vj的路徑簡單路徑路徑上各頂點v1,v2,...,vm

均不互相重復的路徑路徑長度路徑上邊(或弧)的條數回路若路徑上第一個頂點

v1與最后一個頂點vm重合,則稱這樣的路徑為回路或環(huán)連通若從頂點vi到頂點vj（i≠j）有路徑，則稱vi和vj是連通的。連通圖與連通分量

在無向圖中,若從頂點v1到頂點v2有路徑,則稱頂點v1與v2是連通的。如果圖中任意一對頂點都是連通的,則稱此圖是連通圖。非連通圖的極大連通子圖叫做連通分量強連通圖與強連通分量

在有向圖中,若對于每一對頂點vi和vj,都存在一條從vi到vj和從vj到vi的路徑,則稱此圖是強連通圖。非強連通圖的極大強連通子圖叫做強連通分量v2v0v3v1G2的兩個強連通分量v2v3v0v5v4v1非連通圖G3

v2v3v0v5v4v1圖G3的兩個連通分量v0v1v2v3有向圖G2v0v3v2v14967權、網圖的每條邊或弧上，標上具有某種含義的數值，這種與圖的邊相關的數值稱為權（Weight）。帶權的圖稱為網（Network）

5．2圖的存儲結構

圖的存儲結構或表示方式比較多，在選擇圖的存儲結構時，通常取決于具體的應用和所定義的操作。下面介紹兩種基本的存儲結構，即鄰接矩陣表示法和鄰接表。鄰接矩陣(AdjacencyMatrix)表示法在圖的鄰接矩陣表示中，有一個記錄各個頂點信息的頂點表，還有一個表示各個頂點之間關系的鄰接矩陣設圖G=(V,E)是一個有n個頂點的圖，則圖的鄰接矩陣是一個二維數組G.arcs[n][n]，定義:v0v1v4v3v2無向圖G1鄰接矩陣表示：v0v1v2v3有向圖G2鄰接矩陣表示：網絡的鄰接矩陣若G是網，則：Wij表示邊上的權值；∞代表一個計算機允許的、大于所有邊上權值的正整數鄰接矩陣表示：v0v3v2v14967網絡G4無向圖的鄰接矩陣是對稱的，有向圖的鄰接矩陣不一定是對稱的在無向圖中,統(tǒng)計第

i

行(列)中非零元素的個數可得頂點vi的度在有向圖中,統(tǒng)計第i行中非零元素的個數可得頂點vi

的出度，統(tǒng)計第i列中非零元素的個數可得頂點vi的入度鄰接矩陣的行表示頂點的出邊，列表示頂點的入邊，因此從鄰接矩陣很容易確定圖中任意兩個頂點間是否有邊（或弧）相連測試圖中邊（或?。┑臄的繒r，則必須按行、列逐次檢測圖的鄰接矩陣表示法的特點圖的鄰接矩陣表示的存儲結構定義#defineVEX_NUM10/*頂點數目*/typedefcharVextype;/*頂點類型*/typedefstruct{Vextypevexs[VEX_NUM];/*頂點表*/intarcs[VEX_NUM][VEX_NUM];/*鄰接矩陣*/}Mgraph;建立無向圖的鄰接矩陣算法/*算法5.1建立無向圖的鄰接矩陣G,e為邊的數目*/voidcreat

_Mgraph(Mgraph*G,inte){for(i=0;i<VEX_NUM;++i)scanf("%c",&G->vexs[i]);/*輸入頂點信息*/for(i=0;i<VEX_NUM;++i)for(j=0;j<VEX_NUM;++j)G->arcs[i][j]=0;for(k=0;k<e;k++){/*輸入表示邊(vi,vj)的頂點序號i,j*/scanf("%d,%d",&i,&j);G->arcs[i][j]=1;G->arcs[j][i]=1;}}

鄰接表(AdjacencyList)圖的鄰接表是一種順序分配和鏈式分配相結合的存儲結構在鄰接表中，對圖中的每個頂點建立一個單鏈表,鏈表的每一個結點代表一條邊,叫做表結點,結點中保存與該邊相關聯的另一頂點的頂點下標adjvex

和指向同一鏈表中下一個表結點的指針

nextarc

第i個單鏈表中的結點表示依附于頂點vi的所有的邊（對有向圖是以頂點vi為弧尾的?。┟總€鏈表上附設一個表頭結點,結點中存儲頂點vi的有關信息data和指向鏈表表中第一個表結點的指針firstarc

weightadjvexnextarc表結點頭結點datafirstarc每個鏈表上附設一個表頭結點鏈域（firstarc）指向表中第一個結點數據域（data）存儲頂點vi的名稱或者其他有關信息鄰接點域(adjvex)

與頂點vi鄰接的頂點在圖中的序號鏈域(nextarc)

依附于頂點vi的下一條邊或弧所對應的結點權值域(weight)

邊或弧所代表的權值圖的鄰接表存儲結構定義

#defineVEX_NUM10/*頂點數目*/typedefcharVextype;/*頂點類型*/typedefstructArcNode{intadjvex;structArcNode*nextarc;}ArcNode;/*表結點*/typedefstructvnode{Vextypedata;ArcNode*firstarc;}VNode;/*頭結點*/typedefVNodeALgraph[VEX_NUM];/*圖的鄰接鏈表*/v00v11v22v33v443∧1234∧4∧014∧123∧v0v1v4v3v2無向圖G1的鄰接表v0v1v2v3v00v11v2∧2v3313∧2∧0∧有向圖G2的鄰接表3∧0∧0∧1∧v00v11v2

2v33G2的逆鄰鏈表圖的鄰接表的特點設圖中有

n個頂點，e條邊，則用鄰接表表示無向圖時，需要n個頭結點，2e個表結點；用鄰接表表示有向圖時，只需n個頭結點，e

個表結點在無向圖中,統(tǒng)計第i個鏈表中表結點的個數可得頂點

vi的度在有向圖的鄰接表中,統(tǒng)計第i個鏈表中表結點的個數可得頂點vi的出度在有向圖的鄰接表中求

vi

的入度，必須掃描整個鄰接表，統(tǒng)計頂點域的值為i的表結點的數目在有向圖的逆鄰接表中,統(tǒng)計第i個鏈表中表結點的個數可得頂點vi

的入度

/*算法5.2建立有向圖的鄰接表G，e為弧的數目*/voidcreat_ALgraph(ALgraphG,inte){for(i=0;i<VEX_NUM;++i){scanf("%c",&G[i].data);/*輸入頂點信息*/G[i].firstarc=NULL;}for(k=0;k<e;k++){scanf(“%d,%d”,&i,&j);/*輸入表示弧<vi,vj>的頂點序號i,j*/p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=j;p->nextarc=G[i].firstarc;G[i].firstarc=p;}}思考：算法5.2作如何修改可建立無向圖的鄰接表？5．3圖的遍歷圖的遍歷：從圖中某一頂點出發(fā)遍歷圖中其余頂點，且使每一頂點僅被訪問一次遍歷圖的基本方法：深度優(yōu)先搜索DFS(DepthFirstSearch)

廣度優(yōu)先搜索BFS(BreadthFirstSearch

)圖的任一頂點都可能和其余頂點相鄰接,且可能存在回路，因此在訪問完某個頂點之后可能會沿著某些邊又回到了曾經訪問過的頂點,為了避免重復訪問,

可設置一個標志頂點是否被訪問過的輔助數組visited[]，它的初始狀態(tài)為0，在圖的遍歷過程中，一旦某一個頂點

vi被訪問，就立即讓visited[i]

置為1，防止它被多次訪問連通圖的深度優(yōu)先搜索遍歷DFS

(DepthFirstSearch)基本思想先訪問圖中某一起始頂點v

，然后由v

出發(fā)，訪問它的任一鄰接頂點

w1；再從w1

出發(fā)，訪問與w1鄰接但還沒有訪問過的頂點w2；然后再從w2

出發(fā)，進行類似的訪問，…

如此進行下去，直至到達所有的鄰接頂點都被訪問過的頂點u為止。接著，退回一步，退到前一次剛訪問過的頂點，看是否還有其它沒有被訪問的鄰接頂點。如果有，則訪問此頂點，之后再從此頂點出發(fā)，進行與前述類似的訪問；如果沒有，就再退回一步進行搜索。重復上述過程，直到連通圖中所有頂點都被訪問過為止。深度優(yōu)先搜索遍歷過程示例v0v1v2v5v6v3v4v7開始12345678結束搜索回退深度優(yōu)先搜索遍歷序列為

v0、v1、v3、v7、v4、v2、v6、v5連通圖的廣度優(yōu)先搜索遍歷類似于樹的先根遍歷

/*算法7.3從第i個頂點出發(fā)深度優(yōu)先遍歷以鄰接矩陣表示的圖G*/intvisited[NAX_VEX]={0};voidDfs_m(Mgraph*G,inti){printf("%3c",G->vexs[i]);/*訪問頂點vi*/visited[i]=1;for(j=0;j<VEX_NUM;j++)if((G->arcs[i][j]==1)&&(!visited[j]))Dfs_m(G,j);}

/*算法7.4從第i個頂點出發(fā)深度優(yōu)先遍歷以鄰接表表示的圖G*/intvisited[VEX_NUM]={0};voidDfs_L(ALgraphG,inti){printf("%3c",G[i].data);/*訪問頂點vi*/visited[i]=1;p=G[i].firstarc;while(p!=NULL){if(visited[p->adjvex]==0)Dfs_L(G,p->adjvex);p=p->nextarc;}}算法分析設圖中有n個頂點，e條邊如果用鄰接矩陣表示圖，搜索一個頂點的所有的邊，所需時間為O(n)，則遍歷圖中所有的頂點所需的時間為O(n2)如果用鄰接表表示圖，沿開始頂點v

的firstarc

鏈可以找到某個頂點v

的所有鄰接頂點w。由于總共有2e個邊結點，所以掃描邊的時間為O(e)。而且對所有頂點遞歸訪問1次，所以遍歷圖的時間復雜性為O(n+e)連通圖的廣度優(yōu)先搜索遍歷BFS

(BreadthFirstSearch)基本思想:從圖中某個頂點v出發(fā)，在訪問了v之后，依次訪問v的各個未曾訪問過的鄰接點；然后分別從這些鄰接點出發(fā)，依次訪問它們的未曾訪問過的鄰接點，直至所有頂點都被訪問過連通圖的廣度優(yōu)先搜索遍歷類似于樹的按層次遍歷廣度優(yōu)先搜索遍歷過程示例v0v1v2v5v6v3v4v7開始12345678廣度優(yōu)先搜索遍歷序列為

v0、v1、v2、v3、v4、v5、v6、v7廣度優(yōu)先搜索是一種分層的搜索過程，每向前走一步可能訪問一批頂點，不像深度優(yōu)先搜索那樣有往回退的情況。因此，廣度優(yōu)先搜索不是一個遞歸的過程，其算法也不是遞歸的為了實現逐層訪問，算法中使用了一個隊列，以記憶正在訪問的這一層和上一層的頂點，以便于向下一層訪問為避免重復訪問，需要一個輔助數組visited[]，給被訪問過的頂點加標記/*算法

7.5從第k個頂點出發(fā)廣度優(yōu)先遍歷以鄰接矩陣表示的圖G*/intvisited[VEX_NUM]={0};

voidBfs(MgraphG,intk){InitQueue(Q);/*初始化隊列Q*/printf("%3c",G.vexs[k]);/*訪問頂點vk*/visited[k]=1;EnQueue(Q,k);/*vk入隊列*/while(!QueueEmpty(Q)){/*隊列非空*/

DelQueue(Q,i);

/*隊頭頂點vi出隊列*/

for(j=0;j<VEX_NUM;j++)if(G->arcs[i][j]==1&&(!visited[j])){printf("%3c",G.vexs[j]);/*訪問頂點vi的未曾訪問的頂點vj*/visited[j]=1;

EnQueue(Q,j);/*vj入隊列*/}}}當無向圖是連通圖時，只需調用一次Dfs或Bfs算法，便可訪問圖中的所有頂點當無向圖為非連通圖時，從圖中某一頂點出發(fā)，利用Dfs或Bfs

算法不可能遍歷到圖中的所有頂點，只能訪問到該頂點所在的最大連通子圖(連通分量)的所有頂點若從非連通圖中每個連通分量中的一個頂點出發(fā)遍歷圖，則可求出無向圖的所有連通分量在算法中，需要對圖的每一個頂點進行檢測：若已被訪問過，則該頂點一定是落在圖中已求得的連通分量上；若還未被訪問，則從該頂點出發(fā)遍歷圖，可求得圖的另一個連通分量調用Dfs或Bfs

的次數就是連通分量的個數求圖的連通分量(Connectedcomponent)/*算法

7.6求圖的連通分量,G以鄰接矩陣表示*/intvisited[VEX_NUM]={0};

voidConponent(MgraphG){count=0;/*統(tǒng)計連通分量的個數*/

for(j=0;j<VEX_NUM;j++)if(!visited[j]){count++;printf(“\n第%d個連通分量是:”,count);Dfs_m(G,j);/*從vj出發(fā)遍歷一個連通分量*/}

printf(“\n共有%d個連通分量。\n”,count);}對右圖所示的非連通圖G3執(zhí)行算法Conponent，可得到以下輸出結果：第1個連通分量是:v0v1v5v4

第2個連通分量是:v2v3共有2個連通分量v2v3v0v5v4v1非連通圖G3

7.4圖的最小生成樹

(minimumcostspanningtree)設圖G=(V，E)

是個連通圖，當從圖任一頂點出發(fā)遍歷圖G時，將邊集E(G)

分成兩個集合T(G)

和B(G)。其中T(G)

是遍歷圖時所經過的邊的集合，B(G)

是遍歷圖時未經過的邊的集合。顯然，G1(V，T)

是圖G

的子圖。我們稱子圖G1是連通圖G

的生成樹。生成樹的概念生成樹的生成方法v0v1v2v5v6v3v4v7深度優(yōu)先生成樹按深度優(yōu)先搜索得到：廣度優(yōu)先生成樹v0v1v2v5v6v3v4v7按廣度優(yōu)先搜索法得到：生成樹由圖中全部n個頂點，n-1條邊的連通子圖組成使用不同的遍歷圖的方法，可以得到不同的生成樹；從不同的頂點出發(fā)，也可能得到不同的生成樹按照生成樹的定義，n個頂點的連通網絡的生成樹有n個頂點、n-1條邊網絡中所有生成樹中權值總和最小的生成樹為最小生成樹(也稱最小代價生成樹)構造最小生成樹的準則必須只使用該網絡中的邊來構造最小生成樹；必須使用且僅使用n-1條邊來聯結網絡中的n個頂點；不能使用產生回路的邊。網絡的最小生成樹6463556v0v1v3v4v2v5126(a)網絡46556v0v1v3v4v2v5(b)權值之和26463v0v1v3v4v2v512(c)權值之和16435v0v1v3v4v2v512(d)權值之和15普里姆算法構造最小生成樹的基本過程：設連通網G=(V，E)

,構造的最小生成樹T=(U，TE)，在圖中任選一個頂點

u0

作為初始頂點加入U

中，TE

初始為空；當U≠V

時，執(zhí)行以下步驟：

①在圖中選擇一條權值最小的邊(u，v)，且有u∈U，v∈V-U；②將頂點v

并入U中；③將邊(u，v)

并入TE

中。上述過程結束后，所求得的子圖T=(U，TE)

便是G的一棵最小生成樹普里姆(Prim)算法用普里姆算法構造最小生成樹示例（b）v0v21v0（a）4v5（c）v0v21v324v5（d）v0v215v1v324v5（e）v0v213v4（f）5v1v324v5v0v216463556v0v1v3v4v2v5126網絡設置輔助數組dge[],存放從U到V-U具有最小權值的邊其數據類型定義如下：

typedefstruct{Vextypeadjvex;intlowcost;}closedge[VEX_UNM];其中：

adjvex域存儲依附于該邊的在U中的頂點

lowcost域存儲該邊上的權值普里姆算法實現采用鄰接矩陣作為圖的存儲表示若兩個頂點之間不存在邊，則其權值用機內允許的最大數（MAX）表示6463556v0v1v3v4v2v5126網絡0616MM605M3M1505646M50M2M36M06MM4260Gn.arcs=鄰接矩陣

/*算法7.7從頂點u0出發(fā)構造網Gn的最小生成樹T，輸出T的各條邊*/voidPRIM(MgraphGn,Vextypeu0){closedgedge;k=LocatVex(Gn,u0);/*確定頂點u0在網Gn中的序號*/for(j=0;j<VEX_UNM;j++)/*初始化輔助數組*/if(j!=k){dge[j].adjvex=u0;dge[j].lowcost=Gn.arcs[k][j];}dge[k].lowcost=0;/*初始U={u0}*/for(i=0;i<VEX_NUM-1;i++){k=Mininum(dge);/*求權值最小的頂點，vk∈V-U*/

/*輸出生成樹T的邊及權值*/printf(dge[k].adjvex,Gn.vexs[k],dge[k].lowcost);dge[k].lowcost=0;/*頂點vk并入U*/for(j=0;j<VEX_NUM;j++)/*重新調整dge*/if(Gn.arcs[k][j]<dge[j].lowcost){dge[j].lowcost=Gn.arcs[k][j];dge[j].adjvex=Gn.vexs[k];}/*if*/}}intLocatVex(MgraphGn,Vextypeu0){

/*返回頂點u0在網Gn中的序號*/inti;for(i=0;i<VEX_NUM;i++)if(Gn.vexs[i]==u0)returni;}/*LocatVex*/intMininum(closedgedge){

/*在輔助數組dge中求出權值最小的頂點序號j，且vj∈V-U*/

for(i=0;i<VEX_NUM;i++)if(dge[i].lowcost!=0)break;min=i;for(j=i+1;j<VEX_NUM;j++)if(dge[j].lowcost!=0&&dge[j].lowcost<dge[min].lowcost)min=j;returnmin;}/*Mininum*/iclosedge12345UV-Ukadjvexlowcostv06v01v06{v0}{v1,

v2,

v3,

v4,

v5}2adjvexlowcostv250v06v26v24{v0,

v2

}{v1,

v3,

v4,

v5}5adjvexlowcostv250v52v260{v0,

v2,

v5

}{v1,

v3,

v4}3adjvexlowcostv2500v260{v0,

v2,

v5,

v3

}{v1,

v4}1adjvexlowcost000v130{v0,

v2,

v5,

v3,

v1}{v4}4adjvexlowcost00000{v0,

v2,

v5,

v3,

v1

,v4

}{}構造最小生成樹過程中輔助數組中各分量值的變化分析以上算法，設連通網絡有n

個頂點

，則該算法的時間復雜度為O(n2),它適用于邊稠密的網絡

克魯斯卡爾算法是按權值遞增的次序來構造最小生成樹,其基本思想是：設G=(V,E)

是連通網，最小生成樹T=(V,TE)。初始時，TE={φ}

，即T

僅包含網G

的全部頂點，T

中每個頂點自成一個連通分量，在圖G

的邊集E

中按權值自小至大依次選擇邊(u,v)

，若該邊依附的頂點u,v分別是當前T的兩個連通分量中的頂點，則將該邊加入到TE

中；若u,v是當前同一個連通分量中的頂點，則舍去此邊而選擇下一條權值最小的邊。依次類推，直到T中所有頂點都在同一連通分量上為止，T便成為G的一棵最小生成樹?？唆斔箍査惴ㄓ每唆斔箍査惴嬙熳钚∩蓸涫纠齰0v1v3v4v2v5(a)21v0v1v3v4v2v5(c)321v0v1v3v4v2v5(d)4321v0v1v3v4v2v5(e)54321v0v1v3v4v2v5(f)1v0v1v3v4v2v5(b)1算法可簡單描述如下：

T=(V，{φ})；

while(T中所有邊數e<n-1){

從E中選取當前最短邊(u，v)；

if((u，v)并人T之后不產生回路)

將邊(u，v)并入T中；從E中刪去邊(u，v)；

}設連通網絡有e條邊,可以證明克魯斯卡爾算法的時間復雜度是O(elog2e)，克魯斯卡爾算法適合于求邊稀疏的網的最小生成樹。7.5最短路徑(ShortestPath)最短路徑問題：如果從圖中某一頂點(稱為源點)到達另一頂點(稱為終點)的路徑可能不止一條，如何找到一條路徑使得沿此路徑上各邊上的權值總和達到最小。問題解法邊上權值非負情形的單源最短路徑問題

—

Dijkstra算法所有頂點之間的最短路徑

—Floyd算法從某源點到其余頂點之間的最短路徑問題的提法：給定一個帶權有向圖D與源點v，求從v到D中其它頂點的最短路徑。限定各邊上的權值大于或等于0為求得這些最短路徑，Dijkstra提出按路徑長度的遞增次序，逐步產生最短路徑的算法。首先求出長度最短的一條最短路徑，再參照它求出長度次短的一條最短路徑，依次類推，直到從頂點v到其它各頂點的最短路徑全部求出為止采用鄰接矩陣作為圖的存儲表示舉例說明510601020100v3v5v0v4v2v13050帶權有向圖從v0到其余各項點的最短路徑：v0→

v1

：無路徑v0→

v2

：10v0→

v3

：50（經v4）v0→

v4

：30v0→

v5

：60（經v4、v3）

∞∞10∞30100∞∞5∞∞∞∞∞∞50∞∞∞∞∞∞∞10∞∞∞20∞60∞∞∞∞∞∞Gn.arcs=鄰接矩陣引入輔助數組dist。它的每一個分量dist[i]表示當前找到的從源點v0到終點vi

的最短路徑的長度。初始狀態(tài)：若從源點v0到頂點vi有邊，則dist[i]為該邊上的權值；若從源點v0到頂點vi

沒有邊，則dist[i]為+

。引入輔助數組S。它的每一個分量S[i]記錄頂點vi是否已找到最短路徑。若從源點v0到頂點vi已找到最短路徑，則S[i]置為1；若從源點v0到頂點vi未找到最短路徑，則S[i]置為0。初始狀態(tài)：S[0]=1；S[1]～S[n-1]=0；一般情況下，假設S是已求得的最短路徑的終點的集合，則可證明：下一條最短路徑必然是從v0出發(fā)，中間只經過S中的頂點便可到達的那些頂點vx(vx

V-S)的路徑中的一條。引入輔助數組path。

path[i]表示當前找到的從源點v0到終點vi

的最短路徑上vi的前驅頂點,若從v0到vi無路徑，則path[i]置為-1。

每次求得一條最短路徑之后，其終點vk

加入集合S，然后對所有的vi

V-S，修改其dist[i]和path[i]的值。

初始化：S←{v0};

dist[j]←Gn.arcs[0][j],path[j]←0或–1

（j=1,2,…,n-1）//n為圖中頂點個數①求出最短路徑的長度：

dist[k]←min{dist[i]},i

V-S;S←S

U{k

};②修改：

dist[j]←min{dist[j],dist[k]+

Gn.arcs[k][j]}；

path[j]←k；對于每一個j

V-S;③判斷：若S=V或也無頂點可加入到S中,則算法結束，否則轉①。Dijkstra算法描述如下：/*算法5.8求有向網Gn的v0頂點到其余頂點v的最短路徑，path[v]是v0到v的最短路徑的前驅頂點，dist[v]是路徑長度*/voidDijkstra(MgraphGn,intv0,intpath[],intdist[]){ints[VEX_NUM];for(v=0;v<VEX_NUM;v++){/*初始化s、dist和path*/s[v]=0;dist[v]=Gn.arcs[v0][v]; if(dist[v]<MAXINT)path[v]=v0; elsepath[v]=-1;}dist[vo]=0;s[v0]=1;/*初始時源點v0∈S集*//*循環(huán)求v0到某個頂點v的最短路徑，并將v加入S集*/for(i=1;i<VEX_NUM-1;i++){min=MAXINT;for(w=0;w<VEX_NUM;w++) if(!s[w]&&dist[w]<min){/*頂點w不屬于S集且離v0更近*/v=w;min=dist[w];}s[v]=1;/*頂點v并入S*

for(j=0;j<VEX_NUM;j++)/*更新當前最短路徑及距離*/ if(!s[j]&&(min+Gn.arcs[v][j]<dist[j])){ dist[j]=min+Gn.arcs[v][j]; path[j]=v; }/*if*/}/*for*/}/*Dijkstra*/算法的時間復雜度：O(n2)voidPutpath(intv0,intp[],intd[]){

/*輸出源點v0到其余頂點的最短路徑和路徑長度*/

for(i=0;i<VEX_UNM;i++)if(d[i]<MAXINT&&i!=v0){ printf("v%d<--",i); next=p[i]; while(next!=v0){ printf("v%d<--",next); next=p[next]; } printf("v%d:%d\n",v0,d[i]); }elseif(i!=v0)printf("v%d<--v%d:nopath\n",i,v0);}Dijkstra算法動態(tài)執(zhí)行時各輔助數組的變化循環(huán)選擇終點S[]012345dist[]012345path[]0123450-1000000∞10∞30100-1-10-1001v21010000∞10

6030100-1-102002v4101

0100∞1050

30

90-1-104043v3101

11

00∞1050

3060-1-104

034v5101

111

0∞105030

60-1-104

035-101

11

10∞105030

60-1-104

03最后的輸出結果是：

v2<--v0:10v3<--v4<--v0:

50

v4<--v0:

30

v5<--v3<--v4<--v0:

60

v1<--v0:

nopath如何從表中讀取源點0到終點v的最短路徑?舉頂點5為例:

path[5]=3→path[3]=4→path[4]=0，反過來排列，得到路徑(0,4,3,5)，這就是源點0到終點5的最短路徑

應用Dijkstra算法最短路徑的C源程序#include<stdio.h>#include<stdlib.h>#include<conio.h>#defineVEX_NUM6/*頂點數目*/#defineEdge_NUM8/*弧數*/#defineMAXINT999typedefcharVextype;/*頂點類型*/typedefstruct{Vextypevexs[VEX_NUM];intarcs[VEX_NUM][VEX_NUM];}Mgraph;charvex[VEX_NUM]="012345";intvi[Edge_NUM]={0,0,0,1,2,3,4,4};/*弧尾集合*/intvj[Edge_NUM]={2,4,5,2,3,5,3,5};/*弧頭集合*/intnat[Edge_NUM]={10,30,100,5,50,10,20,60};/*權值集合*/voidcreat_Mgraph(Mgraph*G,inte){inti,j,k;for(i=0;i<VEX_NUM;++i)G->vexs[i]=vex[i];for(i=0;i<VEX_NUM;++i)for(j=0;j<VEX_NUM;++j)G->arcs[i][j]=MAXINT;for(k=0;k<e;k++){i=vi[k];j=vj[k];G->arcs[i][j]=nat[k];}}voidDijkstra(MgraphGn,intv0,intpath[],intdist[]){/*略*/

}voidPutpath(intv0,intp[],intd[]){/*略*/

}main(){MgraphGn;inti,j,v0;intpath[VEX_NUM],dis[VEX_NUM];clrscr();creat_Mgraph(&Gn,Edge_NUM);printf("\noutputGn.arcs:\n");for(i=0;i<VEX_NUM;++i){for(j=0;j<VEX_NUM;++j)printf("%5d",Gn.arcs[i][j]);printf("\n");}v0=0;

printf("\nDijkstr:\n");Dijkstra(Gn,v0,path,dis);printf("outputdist[]:\n");for(i=0;i<VEX_NUM;++i)printf("%5d",dis[i]);printf("\n\noutputpath[]:\n");for(i=0;i<VEX_NUM;++i)printf("%5d",path[i]);printf("\n");printf("\noutputpath-->:\n");Putpath(v0,path,dis);printf("\n");getch();}運行求有向網中每一對頂點間的最短路徑

問題的提法：已知一個各邊權值均大于0的帶權有向圖，對每一對頂點vi

vj，要求求出vi

與vj之間的最短路徑和最短路徑長度。 解決方法一:每次以一個頂點為源點，執(zhí)行Dijkstra算法，求得從該頂點到其他各頂點的最短路徑；重復執(zhí)行n次之后，就能求得從每一個頂點出發(fā)到其他各項點的最短路徑。解決方法二:弗洛伊德(Floyd)算法弗洛伊德(Floyd)算法的基本思想遞推地產生一個n階矩陣序列：

D(-1)，D(0)，D(1)，…，D(k-1)，D(k)，…，D(n-1)。其中：

D(-1)[i][j]=Gn.arcs[i][j];D(k)[i][j]=Min{D(k-1)[i][j],D(k-1)[i][k]+D(k-1)[k][j]}(0≤k≤n-1)D(0)[i][j]是從vi到vj中間頂點序號不大于0的最短路徑長度;D(k)[i][j]是從vi到vj中間頂點序號不大于k的最短路徑長度；D(n-1)[i][j]就是從vi到vj的最短路徑長度。為了記錄從vi到vj的最短路徑,設置一個n階方陣P,P(k-1)[i][j]是從vi到vj中間頂點序號不大于k-1的最短路徑上的vi的后一個頂點的序號，若vi到vj無路徑，設P[i][j]=-1。/*算法5.9求有向網Gn中各對頂點間的最短路徑P及路徑長度D*/voidFloyd(MgraphGn,intD[][VEX_UNM],intP[][VEX_UNM]){for(i=0;i<VEX_UNM;i++)/*P和D初始化*/for(j=0;j<VEX_UNM;j++){D[i][j]=Gn.arcs[i][j];if(Gn.arcs[i][j]<MAXINT)P[i][j]=j;elseP[i][j]=-1;}for(k=0;k<VEX_UNM;k++)/*進行n次迭代*/for(i=0;i<VEX_UNM;i++)for(j=0;j<VEX_UNM;j++)if(D[i][j]>D[i][k]+D[k][j]){

/*從vi經vk到vj的有一條更短的路徑*/D[i][j]=D[i][k]+D[k][j];/*修改長度和路徑*/P[i][j]=P[i][k];}/*if*/printf(“長度

路徑\n”);

/*輸出所有頂點對vi，vj間的最短路徑長度和最短路徑*/for(i=0;i<VEX_UNM;++i)for(j=0;j<VEX_UNM;++j){printf("%d:",D[i][j]);/*輸出最短路徑長度*/next=P[i][j];/*next是vi后繼頂點的序號*/if(next==-1)printf("%dto%dnopath.\n",i,j);else{printf("v%d",i);/*輸出起始頂點vi*/while(next!=j){/*輸出后繼頂點,并尋找下一個后繼頂點*/printf("-->v%d",next);next=P[next][j];}/*while*/printf("-->v%d\n",j);/*輸出終點vj*/}/*else*/}/*for*/}/*Floyd*/算法的時間復雜度為0（n3）D(-1)D(0)D(1)D(2)0120120120120041104110460461602602602

50223∞0370370370P(-1)P(0)P(1)P(2)0120120120120-112-112-111-11110-120-120-122-1220-1-100-100-100-1116v0v2v1423有向網04116023∞0鄰接矩陣Floyd算法動態(tài)執(zhí)行時D、P數組的變化

5.6有向無環(huán)圖及其應用拓撲排序計劃、施工過程、生產流程、程序流程等都是“工程”。一般都把工程分為若干個叫做“活動”的子工程。完成了這些活動，工程才完成例如，計算機專業(yè)的學生按照教學計劃學完一系列課程就是一個工程，每一門課程的學習就是整個工程的一些活動。其中有些課程要求先修課程，有些則不要求。這樣在有的課程之間有領先關系，有的課程可以并行地學習課程代號

課程名稱

先修課程

C1

高等數學-C2普通物理C1C3高級語言程序設計-C4

數據結構C1,C3C5數據庫基礎

C3C6匯編語言

C3C7計算機原理C6,C12C8操作系統(tǒng)C4,C6C9微機接口技術C6,C7

C10計算機網絡

C7,C12

C11電路分析C1,C2

C12電子技術基礎C11C8C1C11C12C100C2C4C3C6C5C7C9學生課程學習工程圖（AOV網）有向無環(huán)圖可以用來描述一項工程或任務的進行過程在這種有向圖中，用頂點表示活動，用有向邊<Vi,Vj>表示活動。Vi必須先于活動Vj

進行。這種有向圖叫做頂點表示活動的AOV

(ActivityOnVertices)網在AOV網中,若從活動Vi到活動Vj之間存在一條有向路徑,則稱活動Vi是活動Vj的前驅,活動Vj是活動Vi的后繼AOV網中不能出現有向回路，即有向環(huán)。在AOV網中如果出現了有向環(huán)，則意味著某項活動應以自己作為先決條件

檢測有向環(huán)的一種方法是對AOV網構造它的拓撲有序序列。即將各個頂點(代表各個活動)排列成一個線性有序的序列，使得AOV網中所有應存在的前驅和后繼關系都能得到滿足拓撲排序

構造AOV網全部頂點的拓撲有序序列的運算如果通過拓撲排序能將AOV網的所有頂點都排入一個拓撲有序的序列中，則該AOV網中必定不會出現有向環(huán)；相反，如果得不到滿足要求的拓撲有序序列，則說明AOV網中存在有向環(huán)，此AOV網所代表的工程是不可行的。例如，對學生選課工程圖進行拓撲排序，得到的拓撲有序序列為

C1,C2,C11,C3,C4,C5,C6,C8,C12,C7,C9,C10或

C1,C3,C2,C4,C5,C11,C6,C8,C12,C7，C9,C10一個AOV網的拓撲有序序列是不唯一的拓撲排序的方法

輸入AOV網絡。令n為頂點個數。 在AOV網絡中選一個沒有直接前驅(即入度為0)的頂點,并輸出之從圖中刪去該頂點,同時刪去所有它發(fā)出的有向邊;

重復以上、

步,直到全部頂點均已輸出，拓撲有序序列形成，拓撲排序完成；或圖中還有未輸出的頂點，但已跳出處理循環(huán)。這說明圖中還剩下一些頂點，它們都有直接前驅，再也找不到沒有前驅的頂點了。這時AOV網絡中必定存在有向環(huán)。拓撲排序的過程v0v3v1v4v2v5（a）AOV網v0v3v1v4v2v5(b)輸出v0v3v1v4v2v5（c）輸出v5v3v1v4v2（d）輸出v3v1v4v2輸出v2v1v4（f）輸出v1v4（g）輸出v4拓撲排序序列為：v0,v5,v3,v2,v1,v4存儲結構采用鄰接表，并且在頭結點中增設一個入度域（indegree），存放頂點的入度。入度域為零的頭結點即是無前驅的頂點，刪除該頂點及以它為尾的弧的操作，則可轉換為將它的所有弧頭頂點的入度減1來實現。0v006v50

4v43

∧2v213v321v12

∧

321∧41∧4∧43∧indegree(a)鄰接鏈表拓撲排序算法實現v0v3v1v4v2v5

AOV網為了避免在每一次選入度為零的頂點時重復掃描表頭數組，可以另外設一個棧臨時存放所有入度為零的頂點拓撲排序算法描述如下：

掃描頂點表,將入度為零的頂點入棧；

while(棧非空){

將棧頂頂點vj彈出,輸出并計數；在鄰接表中查vj的直接后繼vk,把vk的人度減1，若vk的人度為零則進棧；

}

若輸出的頂點數小于n，則表示有回路；否則拓撲排序正常結束。AOV網的鄰接表表示typedefstructarcnode{intadjvex;structarcnode*nextarc;}ArcNode;typedefstructvnode{vextypedata;intindegree;/*入度域*/ArcNode*firstarc;}VNode;typedefVNodeALgraph[VEX_UNM];

/*算法5.10對AOV網G進行拓撲排序，若G無回路，則輸出G的頂點的一個拓撲序列并返回1，否則返回0*/intToposort(ALgraphG){InitStact(S);/*置?？?/for(i=0;i<VEX_UNM;i++)/*建零入度頂點棧S*/if(G[i].indegree==0)Push(S,i);/*入度為零的頂點入棧*/count=0;/*對輸出頂點計數*/while(!StactEmpty(S)){Pop(S,j);/*入度為零的頂點vj出棧*/printf("%3c",G[j].data);count++;/*輸出vj并計數*/for(p=G[j].firstarc;p;p=p->nextarc){k=q->adjvex;G[k].indegree--;/*vj的鄰接點的入度減1*/

if(G[k].indegree==0)Pop(S,k);/*若入度為0，則進棧*/}/*for*/}/*while*/if(count<VEX_UNM)return0;/*該AOV網有回路*/elsereturn1;}/*Toposort*/

根據算法所得到的拓撲有序序列為：

v5,v0,v2,v1,v3,v4對一個有n個頂點和e條邊的有向網來說，初始建立入度為零的頂點棧的時間復雜度為O（n）；在拓撲排序過程中，若AOV網無回路，則每個頂點進、出棧各一次，入度減1的操作在for語句中共執(zhí)行e次，因而時間復雜度為O（n+e）算法的總的時間復雜度為O（n+e）。

*關鍵路徑如果在帶權的有向無環(huán)圖中用頂點表示事件(Event)用弧表示一個工程中的活動(Activity)

用弧上權值表示活動持續(xù)時間(Duration)此帶權的有向無環(huán)圖叫做用邊表示活動的網絡，簡稱AOE(ActivityOnEdges)網AOE網在某些工程估算方面非常有用。a10=2a11=4a6=2a9=4a3=5a8=7a7=9a1=6V8V9V7a4=1V4V6a5=1V2V5a2=4V1V3一個假想的AOE網9個事件:v1，v2，v3，…，v9，11項活動:a1,a2,a3,…，a11每個事件表示在它之前的活動已經完成，在它之后的活動可以開始如v1表示整個工程開始,v9表示整個工程結束,v5表示活動a4和a5已經完成，a7和a9可以開始與每個活動相聯系的數是執(zhí)行該活動所需的時間。比如，活動a1需要6天，活動a2需要4天等。

AOE網的特點:(1)沒有有向回路;(2)網中只有一個入度為零的頂點(源點)和一個出度為零的頂點(匯點)

AOE網表示一項工程時,需要研究的問題是：完成整項工程至少需要多少時間?哪些活動是影響整個工程進度的關鍵？在AOE網絡中,有些活動順序進行,有些活動并行進行。從源點到匯點的有向路徑可能不止一條，長度也可能不同。完成不同路徑的活動所需的時間雖然不同，但只有各條路徑上所有活動都完成了，整個工程才完成。完成整個工程所需的時間取決于從源點到匯點的最長路徑長度，即此路徑上所有活動的持續(xù)時間之和。關鍵路徑(CriticalPath)路徑長度最長的路徑圖示的AOE網中的一條關鍵路徑是

(v1,v2,v5,v7,v9)長度是18關鍵活動(CriticalActivity)

關鍵路徑上的所有活動。只要找到了關鍵活動，就可以找到關鍵路徑定義幾個與計算關鍵活動有關的