【精品數(shù)據(jù)結(jié)構(gòu)課件】圖

1、2020/9/9,1,第7章 圖,本章主題：圖的基本概念、圖的存儲結(jié)構(gòu)和圖的常用算法 教學(xué)目的： 教學(xué)重點：圖的各種存儲方式及其運算 教學(xué)難點：圖結(jié)構(gòu)存儲方式的選擇，幾種經(jīng)典圖算法的實現(xiàn) 本章內(nèi)容：圖的基本概念 圖的存儲結(jié)構(gòu) 圖的遍歷 最小生成樹 最短路徑 拓撲排序 關(guān)鍵路徑,2020/9/9,2,本章主要介紹圖的基本概念、圖的存儲結(jié)構(gòu)和有關(guān)圖的一些常用算法。通過本章學(xué)習(xí)，讀者應(yīng)該： 1) 了解圖的定義和術(shù)語 2) 掌握圖的各種存儲結(jié)構(gòu) 3) 掌握圖的深度優(yōu)先搜索和廣度優(yōu)先搜索遍歷算法 4) 理解最小生成樹、最短路徑、拓撲排序、關(guān)鍵路徑等圖的常用算法,本章學(xué)習(xí)導(dǎo)讀,2020/9/9,3,圖（G

2、raph）是一種較線性表和樹更為復(fù)雜的非線性結(jié)構(gòu)。是對結(jié)點的前趨和后繼個數(shù)不加限制的數(shù)據(jù)結(jié)構(gòu)，用來描述元素之間“多對多”的關(guān)系。 在線性結(jié)構(gòu)中，結(jié)點之間的關(guān)系是線性關(guān)系，除開始結(jié)點和 終端結(jié)點外，每個結(jié)點只有一個直接前趨和直接后繼。 在樹形結(jié)構(gòu)中，結(jié)點之間的關(guān)系實質(zhì)上是層次關(guān)系，同層上的每個結(jié)點可以和下一層的零個或多個結(jié)點（即孩子）相關(guān)，但只能和上一層的一個結(jié)點（即雙親）相關(guān)（根結(jié)點除外）。 在圖結(jié)構(gòu)中，對結(jié)點（圖中常稱為頂點）的前趨和后繼個數(shù)不加限制的，即結(jié)點之間的關(guān)系是任意的。 由此，圖的應(yīng)用極為廣泛，特別是近年來的迅速發(fā)展，已滲透到諸如語言學(xué)、邏輯學(xué)、物理、化學(xué)、電訊工程、計算機科學(xué)以及

3、數(shù)學(xué)的其它分支中。,2020/9/9,4,7. 1 .1 圖的定義 圖是由一個頂點集 V 和一個弧集 R構(gòu)成的數(shù)據(jù)結(jié)構(gòu)。 Graph = (V, R ) V = x | x 某個數(shù)據(jù)對象 ， 是頂點的有窮非空集合； R邊的有限集合 R = (x, y) | x, y V 無向圖 或 R = | x, y V /鄰接矩陣類型 typedef struct VertexType vexsMAX_VERTEX_NUM; /頂點表 AdjMatrix arcs; /鄰接矩陣 int vexnum,arcnum; /圖的頂點數(shù)和弧數(shù) MGraph; 由于一般圖的邊或弧較少，其鄰接矩陣的非零元素較少，屬稀

4、疏矩陣，因此會造成一定存儲空間的浪費。,2020/9/9,23,建立鄰接矩陣算法: void CreateMGraph(MGraph ,j=LocateVex(G,v2); G.arcsij=w; G.arcsji=w; return; ,2020/9/9,24,void PrintMGraph(MGraph G) /輸出 int i,j; printf(Output Vertices:); printf(%s,G.vexs); printf(n); printf(Output AdjMatrix:n); for (i=0;iG.vexnum;i+) for (j=0;jG.vexnum;j+

5、) printf(%4d,G.arcsij); printf(n); return; ,2020/9/9,25,7.2.2 鄰接表 圖的鏈式存儲結(jié)構(gòu) 1) 為每個頂點建立一個單鏈表， 2) 第i個單鏈表中包含頂點Vi的所有鄰接頂點。 鄰接表是圖的一種鏈式存儲結(jié)構(gòu)。類似于樹的孩子鏈表表示法。在鄰接表中為圖中每個頂點建立一個單鏈表，用單鏈表中的一個結(jié)點表示依附于該頂點的一條邊（或表示以該頂點為弧尾的一條?。?，稱為邊（或?。┙Y(jié)點。,2020/9/9,26,把同一個頂點發(fā)出的邊鏈接在同一個邊鏈表中，鏈表的每一個結(jié)點代表一條邊，叫做表結(jié)點（邊結(jié)點），鄰接點域adjvex保存與該邊相關(guān)聯(lián)的另一頂點的頂點下

6、標 ， 鏈域nextarc存放指向同一鏈表中下一個表結(jié)點的指針 ，數(shù)據(jù)域info存放邊的權(quán)。邊鏈表的表頭指針存放在頭結(jié)點中。頭結(jié)點以順序結(jié)構(gòu)存儲，其數(shù)據(jù)域data存放頂點信息，鏈域firstarc指向鏈表中第一個頂點。,2020/9/9,27,帶權(quán)圖的邊結(jié)點中info保存該邊上的權(quán)值 。 頂點 Vi 的邊鏈表的頭結(jié)點存放在下標為 i 的頂點數(shù)組中。 在鄰接表的邊鏈表中，各個邊結(jié)點的鏈入順序任意，視邊結(jié)點輸入次序而定。 設(shè)圖中有 n 個頂點，e 條邊，則用鄰接表表示無向圖時，需要 n 個頂點結(jié)點，2e 個邊結(jié)點；用鄰接表表示有向圖時，若不考慮逆鄰接表，只需 n 個頂點結(jié)點，e 個邊結(jié)點。 建立鄰

7、接表的時間復(fù)雜度為O(n*e)。若頂點信息即為頂點的下標，則時間復(fù)雜度為O(n+e)。,2020/9/9,28,有向圖的鄰接表和逆鄰接表,在有向圖的鄰接表中，第 i 個鏈表中結(jié)點的個數(shù)是頂點Vi的出度。 在有向圖的逆鄰接表中，第 i 個鏈表中結(jié)點的個數(shù)是頂點Vi 的入度。,2020/9/9,29,圖7-7 為圖7-6 (a)的的鄰接表和逆鄰接表,圖7-7 有向圖的鄰接表和逆鄰接表,7-6 (a),2020/9/9,30,網(wǎng)絡(luò) (帶權(quán)圖) 的鄰接表,2020/9/9,31,存儲表示 typedef struct ArcNode int adjvex; struct ArcNode *nextar

8、c; int info; ArcNode; /邊結(jié)點類型 typedef struct VNode VertexType data; ArcNode *firstarc; VNode,AdjListMAX_VERTEX_NUM; typedef struct AdjList vertices; /鄰接表 int vexnum,arcnum; ALGraph;,2020/9/9,32,int LocateVex(ALGraph G,char u) int i; for (i=0;iG.vexnum;i+) if(u= =G.verticesi.data) return i; if (i= =G.

9、vexnum) printf(Error u!n);exit(1); return 0; ,void CreateALGraph_adjlist(ALGraph ,2020/9/9,33,printf(Input Arcs(v1,v2 ,2020/9/9,34,7.2.3 十字鏈表 十字鏈表 (Orthogonal List)是有向圖的另一種鏈式存儲結(jié)構(gòu)?？煽醋魇菍⒂邢驁D的鄰接表和逆鄰接表結(jié)合的一種鏈表。 在十字鏈表中，為每個頂點vi設(shè)置一個結(jié)點，它包含數(shù)據(jù)域data和兩個鏈域firstout、firstin，稱為頂點結(jié)點。數(shù)據(jù)域data用于存放頂點vi的有關(guān)信息；鏈域firstin指向以頂點

10、vi為弧頭的第一個弧結(jié)點；鏈域firstout指向以頂點vi為弧尾的第一個弧結(jié)點。 弧結(jié)點包括四個域：尾域tailvex、頭域headvex，鏈域hlink和tlink。 hlink指向弧頭相同的下一條弧，tlink指向弧尾相同的下一條弧；data頂點信息，firstin以該頂點為頭的第一個弧結(jié)點，firstout以該結(jié)點為尾的第一個弧結(jié)點,頂點結(jié)點,弧結(jié)點,2020/9/9,35,圖7-8 十字鏈表,圖7-8為圖7-6 (a)有向圖的十字鏈表。,采用十字鏈表表示有向圖，很容易找到以頂點vi為弧尾的弧和以頂點vi為弧頭的弧，因此頂點的出度、入度都很容易求得。,2020/9/9,36,十字鏈表的

11、數(shù)據(jù)類型定義如下： #define MAXV typedef struct /弧結(jié)點 int tailvex,headvex; /弧尾和弧頭頂點位置 struct ArcNode *hlink,*tlink; /弧頭相同和弧尾相同的弧的鏈域 ArcNode; typedef struct /頂點結(jié)點 VertexType data; /頂點信息 ArcNode *firstin,*firstout; /分別指向該頂點的第一條入弧和出弧 VexNode;,2020/9/9,37,7.2.4 鄰接多重表 鄰接多重表是無向圖的另一種鏈式存儲結(jié)構(gòu)。在鄰接多重表中設(shè)置一個邊結(jié)點表示圖中的一條邊。邊結(jié)點包

12、含五個域，結(jié)構(gòu)如下所示：,其中：mark 域 標志域，用于對該邊進行標記； ivex 域 存放該邊依附的一個頂點vi的位置信息； ilink 域 該鏈域指向依附于頂點vi的另一條邊的邊結(jié)點； jvex 域 存放該邊依附的另一個頂點vj的位置信息； jlink 域 該鏈域指向依附于頂點vj的另一條邊的邊結(jié)點。 鄰接多重表為每個頂點設(shè)置一個結(jié)點，其結(jié)構(gòu)如下：,2020/9/9,38,圖7-9 鄰接多重表,圖7-9為圖7-5 (a)無向圖的鄰接多重表。,由鄰接多重表可以看出，表示邊（vi，vj）的邊結(jié)點通過鏈域ilink和jlink鏈入了頂點vi和頂點vj的兩個鏈表中，實現(xiàn)了用一個邊結(jié)點表示一個邊的

13、目的，克服了在鄰接表中用兩個邊結(jié)點表示一個邊的缺點。因此鄰接多重表是無向圖的一種很有效的存儲結(jié)構(gòu)。,2020/9/9,39,鄰接多重表的結(jié)點數(shù)據(jù)類型定義如下： #define MAXV typedef struct /邊結(jié)點類型 int mark; /訪問標識 int ivex,jvex; /該邊的兩個頂點位置信息 struct Enode *ilink,*jlink; /分別指向依附這兩個頂點的下一條邊 Enode; typedef struct /頂點結(jié)點類型 VertexType data; /頂點數(shù)據(jù)域 ENode *firstedge; /指向第一條依附該頂點的邊 Vnode;,20

14、20/9/9,40,7.3 圖的遍歷,和樹的遍歷相似，若從圖中某頂點出發(fā)訪遍圖中每個頂點，且每個頂點僅訪問一次，此過程稱為圖的遍歷。 (Traversing Graph)。 但是，在圖中有回路，從圖中某一頂點出發(fā)訪問圖中其它頂點時，可能又會回到出發(fā)點，而圖中或許還有頂點沒有訪問到，因此，圖的遍歷較樹的遍歷更復(fù)雜。 圖的遍歷算法是求解圖的連通性問題、拓撲排序和求關(guān)鍵路徑等算法的基礎(chǔ)。 圖的遍歷順序有兩種：深度優(yōu)先搜索（DFS）和廣度優(yōu)先搜索（BFS）。對每種搜索順序，訪問各頂點的順序也不是唯一的。,2020/9/9,41,7.3.1 深度優(yōu)先搜索（DFS） 1 深度優(yōu)先搜索思想 深度優(yōu)先搜索遍歷

15、類似于樹的先序遍歷。假定給定圖G的初態(tài)是所有頂點均未被訪問過，在G中任選一個頂點i作為遍歷的初始點，則深度優(yōu)先搜索遞歸調(diào)用包含以下操作： （1）訪問搜索到的未被訪問的鄰接點； （2）將此頂點的visited數(shù)組元素值置1； （3）搜索該頂點的未被訪問的鄰接點，若該鄰接點存在，則從此鄰接點開始進行同樣的訪問和搜索。 深度優(yōu)先搜索DFS可描述為： （1）訪問v0頂點； （2）置 visitedv0=1； （3）搜索v0未被訪問的鄰接點w，若存在鄰接點w，則DFS(w)。,2020/9/9,42,遍歷過程： DFS 在訪問圖中某一起始頂點 v 后，由 v 出發(fā)，訪問它的任一鄰接頂點 w1；再從 w1

16、 出發(fā)，訪問與 w1鄰 接但還沒有訪問過的頂點 w2；然后再從 w2 出發(fā)，進行類似的訪問， 如此進行下去，直至到達所有的鄰接頂點都被訪問過的頂點 u 為止。 接著，退回一步，退到前一次剛訪問過的頂點，看是否還有其它沒有被訪問的鄰接頂點。如果有，則訪問此頂點，之后再從此頂點出發(fā)，進行與前述類似的訪問；如果沒有，就再退回一步進行搜索。重復(fù)上述過程，直到連通圖中所有頂點都被訪問過為止。,2020/9/9,43,深度優(yōu)先搜索的示例,圖中可能存在回路，且圖的任一頂點都可能與其它頂點相通，在訪問完某個頂點之后可能會沿著某些邊又回到了曾經(jīng)訪問過的頂點。 為了避免重復(fù)訪問，可設(shè)置一個標志頂點是否被訪問過的輔

17、助數(shù)組 visited ，它的初始狀態(tài)為 0，在圖的遍歷過程中，一旦某一個頂點 i 被訪問，就立即讓 visited i 為 1，防止它被多次訪問。,2020/9/9,44,對上圖，深度優(yōu)先搜索遍歷的順序（之一）為： v1 v2v4 v8 v5v6v3v7。,圖7-10 深度優(yōu)先搜索,2020/9/9,45,深度優(yōu)先搜索算法： int visitedMAX_VERTEX_NUM; void DFS(ALGraph G, int v) ArcNode *p; printf(%c,G.verticesv.data); visitedv=1; p=G.verticesv.firstarc; whil

18、e (p) if (!visitedp-adjvex) DFS(G,p-adjvex); p=p-nextarc; /從第v個頂點出發(fā)DFS,2020/9/9,46,整個圖的DFS遍歷 void DFSTraverse(ALGraph G) for (int v=0;vG.vexnum;+v) visitedv=0; for (v=0;vG.vexnum;+v) if (!visitedv) DFS(G,v); 對于連通圖，從一個頂點出發(fā)，調(diào)用DFS函數(shù)即可將所有頂點都遍歷到。,2020/9/9,47,7.3.2 廣度優(yōu)先搜索（BFS） 1 廣度優(yōu)先搜索思想 廣度優(yōu)先搜索遍歷類似于樹的按層次遍

19、歷。 對于無向連通圖，廣度優(yōu)先搜索是從圖的某個頂點v0出發(fā)，在訪問v0之后，依次搜索訪問v0的各個未被訪問過的鄰接點w1，w2，。然后順序搜索訪問w1的各未被訪問過的鄰接點，w2的各未被訪問過的鄰接點，。即從v0開始，由近至遠，按層次依次訪問與v0有路徑相通且路徑長度分別為1，2，的頂點，直至連通圖中所有頂點都被訪問一次。 廣度優(yōu)先搜索的順序不是唯一的，例如圖7-10 (a) 連通圖的廣度優(yōu)先搜索遍歷順序可為v1，v2，v3，v4，v5，v6，v7，v8 也可為v1，v3，v2，v7，v6，v5，v4，v8。,2020/9/9,48,1 廣度優(yōu)先搜索思想 設(shè)圖G的初態(tài)是所有頂點均未訪問，在G

20、中任選一頂點i作為初始點，則廣度優(yōu)先搜索的基本思想是： （1）從圖中的某個頂點V出發(fā)，訪問之；并將其訪問標志置為已被訪問，即visitedi=1； （2）依次訪問頂點V的各個未被訪問過的鄰接 點，將V的全部鄰接點都訪問到； （3）分別從這些鄰接點出發(fā)，依次訪問它們的未被訪問過的鄰接點，并使“先被訪問的頂 點的鄰接點”先于“后被訪問的頂點的鄰接 點”被訪問，直到圖中所有已被訪問過的頂 點的鄰接點都被訪問到。 依此類推，直到圖中所有頂點都被訪問完為止 。,2020/9/9,49,廣度優(yōu)先搜索在搜索訪問一層時，需要記住已被訪問的頂點，以便在訪問下層頂點時，從已被訪問的頂點出發(fā)搜索訪問其鄰接點。所以在

21、廣度優(yōu)先搜索中需要設(shè)置一個隊列Queue，使已被訪問的頂點順序由隊尾進入隊列。在搜索訪問下層頂點時，先從隊首取出一個已被訪問的上層頂點，再從該頂點出發(fā)搜索訪問它的各個鄰接點。,廣度優(yōu)先搜索過程 廣度優(yōu)先生成樹,廣度優(yōu)先搜索的示例,2020/9/9,50,廣度優(yōu)先搜索過程可描述為： （1）f=0;r=0; /隊列初始化，空隊列；f-隊首指針，r-隊尾指針 （2）訪問v0; （3）visitedv0=1; （4）insert(Queue,f,r,v0); /v0進入隊尾 （5）while f0 do (i)delete(Queue,f,r,x); /隊首元素出隊并賦于x (ii)對所有x的鄰接點w

22、 if visitedw=0 then （a）訪問w; （b）visitedw=1; （c）insert(Queue,f,r,w); /w進隊列,2020/9/9,51,以鄰接表為存儲結(jié)構(gòu)，廣度優(yōu)先搜索遍歷算法如下： #define MAXV void bfs(ALGraph *g,int v) ArcNode *p; int queueMAXV; /定義存放隊列的數(shù)組 int visitedMAXV； /定義存放結(jié)點的訪問標志的數(shù)組 int f=0,r=0,x,i; /隊列頭尾指針初始化，把隊列置空 for(i=0,in;i+) /訪問標志數(shù)組初始化 visitedi=0; printf(“

23、d”,v); /訪問初始頂點v visitedv=1; /置已訪問標記 r=(r+1)MAXV; queuer=v; /v進隊 while(f!=r) /若隊列不空時循環(huán) f=(f+1)MAXV; x=queuetf; /出隊并賦給x p=g-adjlistx.firstarc; /找與頂點x鄰接的第一個頂點,2020/9/9,52,p=g-adjlistx.firstarc; /找與頂點x鄰接的第一個頂點 while(p!=NULL) if (visitedp-adjvex=0) /若當前鄰接點未被訪問 visitedp-adjvex=l; /置該頂點已被訪問的標志 printf(“d”，p

24、-adjvex); /訪問該頂點 r=(r+1)MAXV; queuer=p-adjvex; /該頂點進隊 p=p-nextarc; /找下一個鄰接點 / w進隊列,2020/9/9,53,算法分析：,如果使用鄰接表表示圖，則循環(huán)的總時間代價為 d0 + d1 + + dn-1 = O(e)，其中的 di 是頂點 i 的度。 如果使用鄰接矩陣，則對于每一個被訪問過的頂點，循環(huán)要檢測矩陣中的 n 個元素，總的時間代價為O(n2)。,2020/9/9,54,7.4 最小生成樹,1. 生成樹 在一個無向連通圖G中，其所有頂點和遍歷該圖經(jīng)過的所有邊所構(gòu)成的子圖G 稱做圖G的生成樹。一個圖可以有多個生成

25、樹，從不同的頂點出發(fā)，采用不同的遍歷順序，遍歷時所經(jīng)過的邊也就不同，例如圖7-12的(b) 和(c) 為圖7-12 (a) 的兩棵生成樹。其中 (b) 是通過DFS得到的，稱為深度優(yōu)先生成樹；(c) 是通過BFS得到的，稱為廣度優(yōu)先生成樹。,圖7-12 生成樹,2020/9/9,55,按照生成樹的定義，n 個頂點的連通網(wǎng)絡(luò)的生成樹有 n 個頂點、n-1 條邊。而所有包含n-1 條邊及n個頂點的連通圖都是無回路的樹，所以生成樹是連通圖中的極小連通子圖. 由于使用不同的遍歷圖的方法，可以得到不同的生成樹；從不同的頂點出發(fā)，也可能得到不同的生成樹。如深度優(yōu)先生成樹、廣度優(yōu)先生成樹 在圖論中，常常將樹

26、定義為一個無回路連通圖。 對于一個帶權(quán)的無向連通圖，其每個生成樹所有邊上的權(quán)值之和可能不同，我們把所有邊上權(quán)值之和最小的生成樹稱為圖的最小生成樹。求圖的最小生成樹有很多實際應(yīng)用。例如，通訊線路鋪設(shè)造價最優(yōu)問題就是一個最小生成樹問題。,2020/9/9,56,假設(shè)把n個城市看作圖的n個頂點，邊表示兩個城市之間的線路，每條邊上的權(quán)值表示鋪設(shè)該線路所需造價。鋪設(shè)線路連接n個城市，但不形成回路，這實際上就是圖的生成樹，而以最少的線路鋪設(shè)造價連接各個城市，即求線路鋪設(shè)造價最優(yōu)問題，實際上就是在圖的生成樹中選擇權(quán)值之和最小的生成樹。構(gòu)造最小生成樹的算法有很多，下面分別介紹克魯斯卡爾(Kruskal)算法和

27、普里姆(Prim)算法。,7.4.1 克魯斯卡爾(Kruskal)算法 克魯斯卡爾算法是一種按權(quán)值遞增的次序選擇合適的邊來構(gòu)造最小生成樹的方法。,2020/9/9,57,算法的基本思想： 在圖中任取一個頂點K作為開始點，令U=k，W=V-U，其中V為圖中所有頂點集，然后找一個頂點在U中，另一個頂點在W中的邊中最短的一條，找到后，將該邊作為最小生成樹的樹邊保存起來，并將該邊頂點全部加入U集合中，并從W中刪去這些頂點，然后重新調(diào)整U中頂點到W中頂點的距離, 使之保持最小，再重復(fù)此過程，直到W為空集止。 假設(shè)G=（V，E）是一個具有n個頂點的帶權(quán)無向連通圖，T= (U，TE)是G的最小生成樹，其中U

28、是T的頂點集，TE是T的邊集，則構(gòu)造最小生成樹的過程如下： (1) 置U的初值等于V，TE的初值為空集； (2) 按權(quán)值從小到大的順序依次選取圖G中的邊，若選取的邊未使生成樹T形成回路，則加入TE；若選取的邊使生成樹T形成回路，則將其舍棄。循環(huán)執(zhí)行(2)，直到TE中包含(n-1)條邊為止。,2020/9/9,58,應(yīng)用克魯斯卡爾算法構(gòu)造最小生成樹的過程:,2020/9/9,59,為實現(xiàn)克魯斯卡爾算法需要設(shè)置一維輔助數(shù)組E，按權(quán)值從小到大的順序存放圖的邊，數(shù)組的下標取值從0到e-1（e為圖G邊的數(shù)目）。 假設(shè)數(shù)組E存放圖G中的所有邊，且邊已按權(quán)值從小到大的順序排列。n為圖G的頂點個數(shù)，e為圖G的

29、邊數(shù)?？唆斔箍査惴ㄈ缦拢?#define MAXE #define MAXV typedef struct int vex1; /邊的起始頂點 int vex2; /邊的終止頂點 int weight; /邊的權(quán)值 Edge;,2020/9/9,60,Void kruskal(Edge E,int n,int e) int i,j,m1,m2,sn1,sn2,k; int vsetMAXV; for(i=0;in;i+) /初始化輔助數(shù)組 for(i=0;in;i+) /初始化輔助數(shù)組 vseti=i; k=1; /表示當前構(gòu)造最小生成樹的第k條邊，初值為1 j=0; /E中邊的下標，初值為

30、0 while(ke) /生成的邊數(shù)小于e時繼續(xù)循環(huán) ml=Ej.vex1;m2=Ej.vex2;/取一條邊的兩個鄰接點 sn1=vsetm1;sn2=vsetm2; /分別得到兩個頂點所屬的集合編號 if(sn1!=sn2) /兩頂點分屬于不同的集合，該邊是最小生成樹的一條邊,2020/9/9,61, printf(“(m1，m2)：dn”,Ej.weight); k+; /生成邊數(shù)增l for(i=0;in;i+) /兩個集合統(tǒng)一編號 if (vseti= /集合編號為sn2的改為sn1 vseti=sn1; j+; /掃描下一條邊 ,如果給定帶權(quán)無向連通圖G有e條邊，且邊已經(jīng)按權(quán)值遞增的

31、次序存放在數(shù)組E中，則用克魯斯卡爾算法構(gòu)造最小生成樹的時間復(fù)雜度為O (e)?？唆斔箍査惴ǖ臅r間復(fù)雜度與邊數(shù)e有關(guān)，該算法適合于求邊數(shù)較少的帶權(quán)無向連通圖的最小生成樹。,2020/9/9,62,7.4.2 普里姆(Prim)算法 普里姆算法的基本思想：普里姆算法是另一種構(gòu)造最小生成樹的算法，它是按逐個將頂點連通的方式來構(gòu)造最小生成樹的。 從連通網(wǎng)絡(luò) N = V, E 中的某一頂點 u0 出發(fā)，選擇與它關(guān)聯(lián)的具有最小權(quán)值的邊(u0, v)，將其頂點加入到生成樹的頂點集合U中。以后每一步從一個頂點在U中，而另一個頂點不在U中的各條邊中選擇權(quán)值最小的邊(u, v),把該邊加入到生成樹的邊集TE中，

32、把它的頂點加入到集合U中。如此重復(fù)執(zhí)行，直到網(wǎng)絡(luò)中的所有頂點都加入到生成樹頂點集合U中為止。,2020/9/9,63,假設(shè)G=(V，E)是一個具有n個頂點的帶權(quán)無向連通圖，T(U，TE)是G的最小生成樹，其中U是T的頂點集，TE是T的邊集，則構(gòu)造G的最小生成樹T的步驟如下： （1）初始狀態(tài)，TE為空，U=v0，v0V； （2）在所有uU，vV-U的邊(u，v) E中找一條代價最小的邊(u，v)并入TE，同時將v并入U； 重復(fù)執(zhí)行步驟（2）n-1次，直到U=V為止。 在普里姆算法中，為了便于在集合U和(V-U)之間選取權(quán)值最小的邊，需要設(shè)置兩個輔助數(shù)組closest和lowcost，分別用于存放

33、頂點的序號和邊的權(quán)值。 對于每一個頂點vV-U，closestv為U中距離v最近的一個鄰接點，即邊 (v，closestv) 是在所有與頂點v相鄰、且其另一頂點jU的邊中具有最小權(quán)值的邊，其最小權(quán)值為lowcostv，即lowcostv=costvclosestv，,2020/9/9,64,采用鄰接表作為存儲結(jié)構(gòu)： 設(shè)置一個輔助數(shù)組closedge： lowcost域 存放生成樹頂點集合內(nèi)頂點到生成樹外各頂點的各邊上的當前最小權(quán)值； adjvex域 記錄生成樹頂點集合外各頂點距離集合內(nèi)哪個頂點最近(即權(quán)值最小)。,設(shè)置一個輔助數(shù)組closedge： lowcost域：存放在V-U中各個頂點到集

34、合U中的當前最小權(quán)值； adjvex域： 記錄該邊所依附的在U中的頂點,2020/9/9,65,若選擇從頂點0出發(fā)，即u0 = 0，則輔助數(shù)組的兩個域的初始狀態(tài)為： 然后反復(fù)做以下工作： 在 closedge i中選擇 adjvex 0 struct VertexType adjvex; VRType lowcost; closedgeMAX_VERTEX_NUM; void MiniSpanTree_PRIM(MGraph G,VertexType u) int k,j,i,minCost; k=LocateVex(G,u); for (j=0;jG.vexnum;+j) if (j!=k)

35、 closedgej.adjvex=u; closedgej.lowcost=G.arcskj; ,2020/9/9,68,closedgek.lowcost=0; for (i=1;iG.vexnum;+i) k=minimum(closedge); minCost=INFINITY; for (j=0;jG.vexnum;+j) if (closedgej.lowcost minCost ,2020/9/9,69,普里姆算法中的第二個for循環(huán)語句頻度為n-1，其中包含的兩個內(nèi)循環(huán)頻度也都為n-1，因此普里姆算法的時間復(fù)雜度為O(n2)。普里姆算法的時間復(fù)雜度與邊數(shù)e無關(guān)，該算法更適合于求

36、邊數(shù)較多的帶權(quán)無向連通圖的最小生成樹。,2020/9/9,70,7.5 最短路徑,交通網(wǎng)絡(luò)中常常提出這樣的問題：從甲地到乙地之間是否有公路連通? 在有多條通路的情況下，哪一條路最短? 交通網(wǎng)絡(luò)可用帶權(quán)圖來表示。頂點表示城市名稱，邊表示兩個城市有路連通，邊上權(quán)值可表示兩城市之間的距離、交通費或途中所花費的時間等。求兩個頂點之間的最短路徑，不是指路徑上邊數(shù)之和最少，而是指路徑上各邊的權(quán)值之和最小。 另外，若兩個頂點之間沒有邊，則認為兩個頂點無通路，但有可能有間接通路(從其它頂點達到)。 路徑上的開始頂點(出發(fā)點)稱為源點，路徑上的最后一個頂點稱為終點，并假定討論的權(quán)值不能為負數(shù)。,2020/9/9

37、,71,最短路徑： 如果從圖中某一頂點(稱為源點)到達另一頂點(稱為終點)的路徑可能不止一條，如何找到一條路徑使得沿此路徑上各邊上的權(quán)值總和達到最小。 對于帶權(quán)的圖，通常把一條路徑上所經(jīng)過邊或弧上的權(quán)值之和定義為該路徑的路徑長度。從一個頂點到另一個頂點可能存在著多條路徑，把路徑長度最短的那條路徑稱為最短路徑，其路徑長度稱為最短路徑長度。無權(quán)圖實際上是有權(quán)圖的一種特例，我們可以把無權(quán)圖的每條邊或弧的權(quán)值看成是l，每條路徑上所經(jīng)過的邊或弧數(shù)即為路徑長度。本章討論兩種最常見的最短路徑問題。,2020/9/9,72,問題解法 邊上權(quán)值非負情形的單源最短路徑問題 Dijkstra算法 所有頂點之間的最短

38、路徑 Floyd算法 邊上權(quán)值非負情形的單源最短路徑問題 問題的提法： 給定一個帶權(quán)有向圖D與源點v，求從v到D中其它頂點的最短路徑。限定各邊上的權(quán)值大于或等于0。 為求得這些最短路徑，Dijkstra提出按路徑長度的遞增次序，逐步產(chǎn)生最短路徑的算法。首先求出長度最短的一條最短路徑，再參照它求出長度次短的一條最短路徑，依次類推，直到從頂點v到其它各頂點的最短路徑全部求出為止。,2020/9/9,73,7.5.1 求一頂點（單源點）到其余頂點的最短路徑 單源點最短路徑是指：給定一個出發(fā)點(單源點)和一個有向網(wǎng)G=(V，E),求出源點到其它各頂點之間的最短路徑。 迪杰斯特拉(Dijkstra)在做

39、了大量觀察后,首先提出了按路徑長度遞增產(chǎn)生各頂點的最短路徑算法,我們稱之為迪杰斯特拉算法。 算法的基本思想是:設(shè)置并逐步擴充一個集合S，存放已求出其最短路徑的頂點，則尚未確定最短路徑的頂點集合是V-S，其中V為網(wǎng)中所有頂點集合。按最短路徑長度遞增的順序逐個以V-S中的頂點加到S中，直到S中包含全部頂點，而V-S為空。,2020/9/9,74,具體做法是:設(shè)源點為Vl,則S中只包含頂點Vl，令W=V-S，則W中包含除Vl外圖中所有頂點，Vl對應(yīng)的距離值為0，W中頂點對應(yīng)的距離值是這樣規(guī)定的：若圖中有弧則Vj頂點的距離為此弧權(quán)值，否則為(一個很大的數(shù))，然后每次從W中的頂點中選一個其距離值為最小的

40、頂點Vm加入到S中，每往S中加入一個頂點Vm，就要對W中的各個頂點的距離值進行一次修改。若加進Vm做中間頂點，使+的值小于值，則用+代替原來Vj的距離，修改后再在W中選距離值最小的頂點加入到S中，如此進行下去，直到S中包含了圖中所有頂點為止。,2020/9/9,75,圖7-16 帶權(quán)有向圖,設(shè)G=(V，E)是一個帶權(quán)有向圖，指定的頂點v0為源點，求v0到圖的其余各頂點的最短路徑。如圖7-16所示，若以頂點0為v0，它到其余各頂點的最短路徑分別為： 頂點0 頂點1：無路徑 頂點0 頂點2：最短路徑為（0，2），最短路徑長度為10 頂點0 頂點4：最短路徑為（0，4），最短路徑長度為30 頂點0

41、頂點3：最短路徑為（0，4，3），最短路徑長度為50 頂點0 頂點5：最短路徑為（0，4，3，5），最短路徑長度為60,2020/9/9,76,從以上圖7-16的最短路徑可以看出： (1) 最短路徑并不一定是經(jīng)過邊或弧數(shù)最少的路徑。如從頂點0到頂點5的路徑（0，5）長度為100，路徑（0，4，5）長度為90，路徑（0，2，3，5）長度為70，路徑（0，4，3，5）長度為60，其中最短路徑為（0，4，3，5），最短路徑長度為60。 (2) 這些最短路徑中，長度最短的路徑上只有一條弧，且它的權(quán)值在從源點出發(fā)的所有弧的權(quán)值中最小。如從源點0出發(fā)有3條弧，其中以弧的權(quán)值為最小。此時（0，2）不僅是頂點

42、 0到頂點2 的一條最短路徑，而且它在從源點0到其它各頂點的最短路徑中長度最短。 (3)按照路徑長度遞增的次序產(chǎn)生最短路徑。求得第二條最短路徑（0，4）；之后求得第三條最短路徑（0，4，3），它經(jīng)過已求出的第二條最短路徑（0，4）到達頂點3；求得的第四條最短路徑（0，4，3，5），經(jīng)過已求出的第三條最短路徑（0，4，3）到達頂點5。,2020/9/9,77,迪杰斯特拉算法的求解過程：,2020/9/9,78,圖7-17 迪杰斯特拉算法求最短路徑過程及結(jié)果,2020/9/9,79,Dijkstra算法可描述如下：,初始化： S v0 ; Dj arcs0j, j = 1, 2, , n-1; /

43、 n為圖中頂點個數(shù) 求出最短路徑的長度： Dk min Di , i V- S ; S S U k ; 修改： Di min Di, Dk + arcski , 對于每一個 i V- S ; 判斷： 若S = V, 則算法結(jié)束，否則轉(zhuǎn)。,2020/9/9,80,狄杰斯特拉算法dijkstra，其中n為圖G的頂點數(shù)，v0為源點。 #define INF 32767 /INF表示 #define MAXV void dijkstra(int costMAXV，int n，int vO) int distMAXV，pathMAXV； int sMAXV； int mindis； int i，j，k；

44、 for(i=0;in;i+) disti=costvOi; /距離初始化 si=0; /s初始化 if (costvOiINF) /路徑初始化 pathi=vO; else pathi=-1; svO=1; /源點v0放入S中 for(i=1;in;i+) /重復(fù)，直到求出v0到其余所有頂點的最短路徑,2020/9/9,81,for(i=1;in;i+) /重復(fù)，直到求出v0到其余所有頂點的最短路徑 mindis=INF; k=vO; for(j=1;jn;j+) /從V-S中選取具有最小距離的頂點v k if(sj=0 /輸出最短路徑,2020/9/9,82,通過pathi向前回推直到v0

45、為止，可以找出從v 0到頂點v i的最短路徑。輸出最短路徑的算法dispath如下： void dispath(int dist,int path,int s,int n,int vO) int i,k; for(i=0;in;i+) if(si=1) /S中頂點 k=i; printf(“d 到 d的最短路徑為:”, v0,i); while(k!=v0) printf(“d-”,k); k=pathk; printf(“d 路徑長度為:dn”,v0,disti); else printf(“d-d不存在路徑n”,i,v0); ,2020/9/9,83,在狄克斯特拉算法中，求一條最短路徑所花

46、費的時間：從V-S中選取具有最小距離的頂點v k花費時間O(n)；修改V-S中頂點的距離花費時間O(n)；輸出最短路徑花費時間O(n)。因此求出n-1條最短路徑的時間復(fù)雜度為O(n2)。,2020/9/9,84,7.5.2 每對頂點之間的最短路徑 頂點對之間的最短路徑是指：對于給定的有向網(wǎng)G=(V,E),要對G中任意一對頂點有序?qū)、W(VW),找出V到W的最短距離和W到V的最短距離。 解決此問題的一個有效方法是:輪流以每一個頂點為源點,重復(fù)執(zhí)行迪杰斯特拉算法n次,即可求得每一對頂點之間的最短路徑,總的時間復(fù)雜度為O(n3)。 弗洛伊德提出了另外一個求圖中任意兩頂點之間最短路徑的算法，雖然其時

47、間復(fù)雜度也是 O(n3)，但其算法的形式更簡單，易于理解和編程。,2020/9/9,85,弗洛伊德算法仍然使用前面定義的圖的鄰接矩陣arcsn+1n+1來存儲帶權(quán)有向圖。算法的基本思想是:設(shè)置一個nxn的矩陣A(k)，其中除對角線的元素都等于0外，其它元素a(k)ij表示頂點i到頂點j的路徑長度，K表示運算步驟。開始時，以任意兩個頂點之間的有向邊的權(quán)值作為路徑長度，沒有有向邊時，路徑長度為，當K=O時, A (0)ij=arcsij 以后逐步嘗試在原路徑中加入其它頂點作為中間頂點，如果增加中間頂點后，得到的路徑比原來的路徑長度減少了，則以此新路徑代替原路徑，修改矩陣元素。具體做法為：,2020

48、/9/9,86,第一步，讓所有邊上加入中間頂點1，取Aij與Ai1+A1j中較小的值作Aij的值，完成后得到A(1)， 第二步，讓所有邊上加入中間頂點2，取Aij與Ai2+A2j中較小的值，完成后得到A(2)，如此進行下去，當?shù)趎步完成后，得到A(n)，A(n)即為我們所求結(jié)果,A(n)ij表示頂點i到頂點j的最短距離。,因此，弗洛伊德算法可以描述為: A(0)ij=arcsij; /arcs為圖的鄰接矩陣 A(k)ij=minA(k-1) ij,A(k-1) ik+A(k-1) kj 其中 k=1,2,n,2020/9/9,87,Floyd算法的基本思想： 定義一個n階方陣序列： D(-1)

49、, D(0), , D(n-1). 其中 D(-1) ij = G.arcsij； D(k) ij = min D(k-1)ij， D(k-1)ik + D(k-1)kj , k = 0,1, n-1 D(0) ij是從頂點vi 到vj , 中間頂點是v0的最短路徑的長度, D(k) ij是從頂點vi 到vj , 中間頂點的序號不大于k的最短路徑長度, D(n-1)ij是從頂點vi 到vj 的最短路徑長度。,2020/9/9,88,Floyd算法允許圖中有帶負權(quán)值的邊，但不許有包含帶負權(quán)值的邊組成的回路。 本章給出的求解最短路徑的算法不僅適用于帶權(quán)有向圖，對帶權(quán)無向圖也可以適用。因為帶權(quán)無向圖

50、可以看作是有往返二重邊的有向圖，只要在頂點vi 與vj 之間存在無向邊(vi , vj )，就可以看成是在這兩個頂點之間存在權(quán)值相同的兩條有向邊和。,2020/9/9,89,弗洛伊德算法floyd如下： #define INF 32767 /INF表示 #define MAXV void floyd(int costMAXV，int n) int AMAXVMAXV,pathMAXVMAXV; int i,j,k; for(i=0;i(Aik+Akj),2020/9/9,90,if(Aij(Aik+Akj) Aij=Aik+Akj; pathij=k; dispath(A,path,n); /

51、輸出最短路徑 以下是輸出最短路徑的算法dispath，其中ppath（）函數(shù)在path中遞歸輸出從頂點vi到vj的最短路徑。 void ppath(int pathMAXV,int i,int j) int k; k=pathij; if(k=-1) /pathij=-1時,頂點vi和vj之間無中間頂點 return; ppath(path,i,k); printf(“d,”,k); ppath(path,k,j); ,2020/9/9,91,void dispath(int AMAXV,int pathMAXV,int n) int i,j; for(i=0;in;i+) for(j=0;j

52、n;j+) if(Aij=INF) if(i!=j) printf(“從頂點d到頂點d沒有路徑n”,i,j); else printf(“從頂點d到頂點d路徑為:”,i,j);； printf(“d ,”,i); ppath(path,i,j); printf(“d”,j); printf(“路徑長度為:dn”,Aij); 弗洛伊德算法包含一個三重循環(huán)，其時間復(fù)雜度為O(n3)。,2020/9/9,92,1.拓撲排序 通常我們把計劃、施工過程、生產(chǎn)流程、程序流程等都當成一個工程，一個大的工程常常被劃分成許多較小的子工程，這些子工程稱為活動。這些活動完成時，整個工程也就完成了。 例如，計算機專業(yè)

53、學(xué)生的課程開設(shè)可看成是一個工程，每一門課程就是工程中的活動，圖7-21給出了若干門所開設(shè)的課程，其中有些課程的開設(shè)有先后關(guān)系，有些則沒有先后關(guān)系，有先后關(guān)系的課程必須按先后關(guān)系開設(shè)，如開設(shè)數(shù)據(jù)結(jié)構(gòu)課程之前必須先學(xué)完程序設(shè)計基礎(chǔ)及離散數(shù)學(xué)，而開設(shè)離散數(shù)學(xué)則必須先并行學(xué)完高等數(shù)學(xué)、程序設(shè)計基礎(chǔ)課程。,7.6 拓撲排序,2020/9/9,93,圖7-21 課程名稱及相應(yīng)的課程安排次序,圖7-22 課程安排的AOV網(wǎng),在圖7-22中，我們用一種有向圖來表示課程開設(shè)，在這種有向圖中，頂點表示活動，有向邊表示活動的優(yōu)先關(guān)系，這有向圖叫做頂點表示活動的網(wǎng)絡(luò)(Actire On Vertices)簡稱為AOV

54、網(wǎng)。,2020/9/9,94,AOV網(wǎng)Activity On Vertex Network 用頂點表示活動，用弧表示活動間 的優(yōu)先關(guān)系的有向圖，稱為頂點表 示活動的網(wǎng)。 AOV 網(wǎng)中不能有回路 拓撲排序： 假設(shè)G=(V，E)是一個具有n個頂點的有向圖，V中頂點序列vl，v2，vn稱做一個拓撲序列(Topological Order)，當且僅當該頂點序列滿足下列條件：若在有向圖G中存在從頂點vi到vj的一條路徑，則在頂點序列中頂點vi必須排在頂點vj之前。通常，在AOV網(wǎng)中，將所有活動排列成一個拓撲序列的過程叫做拓撲排序(Topological Sort)。,2020/9/9,95,由于AOV網(wǎng)

55、中有些活動之間沒有次序要求，它們在拓撲序列的位置可以是任意的，因此拓撲排序的結(jié)果不唯一。 對圖7-22進行拓撲排序，可得一個拓撲序列： C1，C3，C2，C4，C7，C6，C5 也可得到另一個拓撲序列： C2，C7，C1，C3，C4，C5，C6 還可以得到其它的拓撲序列。學(xué)生按照任何一個拓撲序列都可以完成所要求的全部課程學(xué)習(xí)。 在AOV網(wǎng)中不應(yīng)該出現(xiàn)有向環(huán)。因為環(huán)的存在意味著某項活動將以自己為先決條件，顯然無法形成拓撲序列。 判定網(wǎng)中是否存在環(huán)的方法：對有向圖構(gòu)造其頂點的拓撲有序序列，若網(wǎng)中所有頂點都出現(xiàn)在它的拓撲有序序列中，則該AOV網(wǎng)中一定不存在環(huán)。,2020/9/9,96,進行拓撲排序的

56、方法： 輸入AOV網(wǎng)絡(luò)。令 n 為頂點個數(shù)。 在AOV網(wǎng)絡(luò)中選一個沒有直接前驅(qū)的頂點, 并輸出之; 從圖中刪去該頂點, 同時刪去所有它發(fā)出的有向邊; 重復(fù)以上 、 步, 直到全部頂點均已輸出，拓撲有序序列形成，拓撲排序完成；或圖中還有未輸出的頂點，但已跳出處理循環(huán)。這說明圖中還剩下一些頂點，它們都有直接前驅(qū)，再也找不到?jīng)]有前驅(qū)的頂點了。這時AOV網(wǎng)絡(luò)中必定存在有向環(huán)。,2020/9/9,97,拓撲排序的過程,2020/9/9,98,最后得到的拓撲有序序列為 C4 , C0 , C3 , C2 , C1 , C5 。它滿足圖中給出的所有前驅(qū)和后繼關(guān)系，對于本來沒有這種關(guān)系的頂點，如C4和C2，也

57、排出了先后次序關(guān)系。,2020/9/9,99,在實現(xiàn)拓撲排序的算法中，采用鄰接表作為有向圖的存儲結(jié)構(gòu)，每個頂點設(shè)置一個單鏈表，每個單鏈表有一個表頭結(jié)點，在表頭結(jié)點中增加一個存放頂點入度的域count，這些表頭結(jié)點構(gòu)成一個數(shù)組，表頭結(jié)點定義如下： typedef struct /表頭結(jié)點 Vertex data; /頂點信息 int count; /存放頂點入度 ArcNode *firstarc; /指向第一條弧 Vnode;,在執(zhí)行拓撲排序的過程中，當某個頂點的入度為零(沒有前驅(qū)頂點)時，就將此頂點輸出，同時將該頂點的所有后繼頂點的入度減1，相當于刪除所有以該頂點為尾的弧。為了避免重復(fù)檢測頂點的入度是否為零，需要設(shè)立一個棧來存放入度為零的頂點。執(zhí)行拓撲排序的算法如下：,2020/9/9,100,void topsort(VNode adj,int n) int i,j; int stackMAXV,top=0; /棧stack的指針為top ArcNode *p; for(i=0;i0) /棧不為空 i=stacktop; top-; /頂點vi出棧 printf(“d”,i); /輸出vi p=adji.firstarc; /指向以vi為弧尾的第一條弧 while(p!=