L10(數(shù)據(jù)結(jié)構(gòu)：圖形結(jié)構(gòu))

1、Fundamentals of Software軟件技術(shù)基礎(chǔ) 自動(dòng)化學(xué)院儀器科學(xué)與技術(shù)系徐生林徐生林Email: Tel: 86919131(O)、 88915606(O) MP:QQ群群: 40048788周四上午3-5：12教302周四下午6-8：3教211Part 2: Data Structures 第10講: 圖形結(jié)構(gòu)o 基本內(nèi)容n 圖的定義及基本術(shù)語(yǔ)n 圖的存儲(chǔ)結(jié)構(gòu)n 圖的遍歷、圖的應(yīng)用o 要求n 掌握?qǐng)D的基本概念和存儲(chǔ)結(jié)構(gòu)n 掌握?qǐng)D的遍歷方法n 掌握常用圖的應(yīng)用一、圖的定義二、基本術(shù)語(yǔ)三、抽象數(shù)據(jù)類(lèi)型（略）第1節(jié) 圖的定義及基本術(shù)語(yǔ) 圖圖是一種復(fù)雜的非線

2、性結(jié)構(gòu)由兩個(gè)集合V和E組成，V是頂點(diǎn)的有窮非空集，E是V中頂點(diǎn)偶對(duì)(邊)的有窮集。 圖的邏輯結(jié)構(gòu)特征圖的邏輯結(jié)構(gòu)特征：就是其結(jié)點(diǎn)(頂點(diǎn))的前趨和后繼的個(gè)數(shù)都是沒(méi)有限制的，即任意兩個(gè)結(jié)點(diǎn)之間之間都可能相關(guān)。o無(wú)向圖:圖中頂點(diǎn)關(guān)系為無(wú)序?qū)Α?邊)o有向圖:圖中頂點(diǎn)關(guān)系為有序?qū)Α?弧)o網(wǎng)：圖中每一條邊附有一個(gè)對(duì)應(yīng)的數(shù)。(權(quán))o有向網(wǎng)：弧上帶權(quán)的有向圖。1.1 圖的定義1 12 23 34 45 51 14 43 32 2無(wú)向圖有向圖1.1 圖的定義o子圖：簡(jiǎn)單地說(shuō)，子圖就是原圖的一部分o度：無(wú)向圖中頂點(diǎn)的度就是關(guān)聯(lián)于該頂點(diǎn)的邊的數(shù)目o入度：頂點(diǎn)v的入度即是以該頂點(diǎn)為終點(diǎn)的邊的數(shù)目o出度：頂點(diǎn)v的出

3、度即是以該頂點(diǎn)為始點(diǎn)的邊的數(shù)目o權(quán)：與邊相關(guān)的數(shù)值稱(chēng)為權(quán)o網(wǎng)：帶權(quán)的圖稱(chēng)為網(wǎng)o有向網(wǎng)：弧上帶權(quán)的有向圖稱(chēng)為有向網(wǎng)1.2 基本術(shù)語(yǔ)o路徑：從頂點(diǎn)Vp到Vq的頂點(diǎn)序列o簡(jiǎn)單路徑：除起點(diǎn)和終點(diǎn)可以相同外，路徑上其余頂點(diǎn)均不相同o回路：起點(diǎn)和終點(diǎn)相同的簡(jiǎn)單路徑o連通：兩個(gè)不同頂點(diǎn)之間有路徑,該兩點(diǎn)連通o連通圖：圖中的任意兩個(gè)不同頂點(diǎn)之間都連通(即有路徑)，則此圖為連通圖o連通分量：無(wú)向圖的極大連通子圖稱(chēng)為它的連通分量o強(qiáng)連通分量：有向圖的極大強(qiáng)連通子圖稱(chēng)為強(qiáng)連通分量o強(qiáng)連通圖：有向圖中，若圖中任意兩個(gè)不同頂點(diǎn)都存在雙向的路徑，則稱(chēng)該圖為強(qiáng)連通圖1.2 基本術(shù)語(yǔ)例例1 12 23 35 54 41 12

4、 23 34 4無(wú)向圖無(wú)向圖結(jié)點(diǎn)結(jié)點(diǎn)1 1的度的度:3:3有向圖有向圖結(jié)點(diǎn)結(jié)點(diǎn)1 1的出度的出度:2:2結(jié)點(diǎn)結(jié)點(diǎn)1 1的入度的入度:1:11.2 基本術(shù)語(yǔ)例例(1)找出所有的簡(jiǎn)單回路。找出所有的簡(jiǎn)單回路。(a)123 (b)無(wú)無(wú)(c)123、234、1243(d)無(wú)無(wú)(2)哪些圖是連通圖哪些圖是連通圖?對(duì)非連通圖給出其連通分量。對(duì)非連通圖給出其連通分量。(a)、(c)、(d)是連通圖，是連通圖，(b)不是連通圖，因?yàn)閺牟皇沁B通圖，因?yàn)閺?到到2沒(méi)有路徑。沒(méi)有路徑。 1.2 基本術(shù)語(yǔ)一、鄰接矩陣一、鄰接矩陣二、鄰接表二、鄰接表第2節(jié) 圖的存儲(chǔ)結(jié)構(gòu). . 圖的鄰接矩陣表示圖的鄰接矩陣表示o用一個(gè)n

5、(n為頂點(diǎn)數(shù))階方陣來(lái)表示圖的結(jié)構(gòu)。以第i行第j列上的數(shù)來(lái)表示頂點(diǎn)vi和vj之間是否有邊或邊的權(quán)值。1 12 23 35 54 40 1 1 1 01 0 1 0 01 1 0 0 11 0 0 0 00 0 1 0 01 12 23 34 40 1 1 00 0 0 00 0 0 11 0 0 0有向圖，其矩陣不對(duì)稱(chēng)有向圖，其矩陣不對(duì)稱(chēng)無(wú)向圖，矩陣對(duì)稱(chēng)無(wú)向圖，矩陣對(duì)稱(chēng)2.1 鄰接矩陣2. 鄰接矩陣存儲(chǔ)的特點(diǎn)鄰接矩陣存儲(chǔ)的特點(diǎn)o對(duì)于無(wú)向圖而言，鄰接矩陣是對(duì)稱(chēng)的，用鄰接矩陣表示的空間復(fù)雜度為S(n)=O(n2).(方階)o建立鄰接矩陣算法的時(shí)間是O(n+n2+e),所以其時(shí)間復(fù)雜度為O(n2)假

6、設(shè)圖的頂點(diǎn)是假設(shè)圖的頂點(diǎn)是A,B.A,B.，請(qǐng)根據(jù)下述的鄰接矩陣畫(huà)出相應(yīng)的無(wú)向圖或有向圖。，請(qǐng)根據(jù)下述的鄰接矩陣畫(huà)出相應(yīng)的無(wú)向圖或有向圖。0 1 1 11 0 1 11 1 0 11 1 1 00 1 1 0 00 0 0 1 01 0 0 0 11 0 0 0 0 0 1 0 1 03.鄰接矩陣存儲(chǔ)的定義鄰接矩陣存儲(chǔ)的定義const int n=maxn; /圖中頂點(diǎn)數(shù)struct graph int vn+1; /存放頂點(diǎn)信息v1,v2int arcsn+1n+1; /鄰接矩陣;1.圖的鄰接表表示圖的鄰接表表示o這種表示法類(lèi)似于樹(shù)的孩子鏈表表示法，它首先對(duì)每個(gè)頂點(diǎn)vi建立一個(gè)單鏈表(即鄰接

7、表)，這個(gè)單鏈表由鄰接于vi的所有頂點(diǎn)的結(jié)點(diǎn)構(gòu)成。o第i個(gè)單鏈表中的結(jié)點(diǎn)表示依附于頂點(diǎn)vi的的邊（在有向圖中是以vi為尾的弧出邊表，否則為入邊表）給每個(gè)單鏈表設(shè)一頭結(jié)點(diǎn)，頭結(jié)點(diǎn)存放頂點(diǎn)vi的信息o把這些頭結(jié)點(diǎn)順序存于一個(gè)向量中構(gòu)成頂點(diǎn)表.2.2 鄰接表表結(jié)點(diǎn)表結(jié)點(diǎn)鄰接域鄰接域 數(shù)據(jù)域數(shù)據(jù)域鏈域鏈域Adjvex data nextarc與頂點(diǎn)與頂點(diǎn)vi鄰接鄰接的點(diǎn)的的點(diǎn)的序號(hào)序號(hào)存儲(chǔ)與存儲(chǔ)與邊或弧邊或弧相關(guān)的相關(guān)的信息信息如：權(quán)如：權(quán)值值指示下指示下一條邊一條邊或弧的或弧的結(jié)點(diǎn)結(jié)點(diǎn)頭結(jié)點(diǎn)頭結(jié)點(diǎn)數(shù)據(jù)域數(shù)據(jù)域鏈域鏈域vexdata firarc指示鏈指示鏈表中的表中的一個(gè)結(jié)一個(gè)結(jié)點(diǎn)點(diǎn)頂點(diǎn)頂點(diǎn)vi的信

8、息的信息如：頂如：頂點(diǎn)號(hào)點(diǎn)號(hào)1 12 23 35 54 41234 213 3215 41 53 1 12 23 34 4123 234 41 1 12 23 35 54 42479612342133125415322746799461 12 23 34 418541232344185412. 圖的鄰接表表示的定義圖的鄰接表表示的定義struct link /定義鏈表類(lèi)型(表結(jié)點(diǎn))int Adjvex; /鄰接域 elemtype data; /數(shù)據(jù)域，elemtype：/結(jié)點(diǎn)數(shù)據(jù)類(lèi)型link *nextarc; /鏈域;struct node /定義鄰接表的表頭類(lèi)型(頭結(jié)點(diǎn))elemtype

9、 vexdata; /數(shù)據(jù)域，elemtype：/頂點(diǎn)信息數(shù)據(jù)類(lèi)型link *firarc; /鏈域 an+1;3. 鄰接矩陣與鄰接表鄰接矩陣與鄰接表o建立鄰接矩陣算法的時(shí)間是O(n+n2+e),所以其時(shí)間復(fù)雜度為O(n2)。o建立鄰接表的算法時(shí)間復(fù)雜度為O(n+e)。鄰接表的空間復(fù)雜度為O(n+e)。o從存儲(chǔ)空間角度看，鄰接表更適合于表示稀疏圖而鄰接矩陣適合于表示稠密圖。o從求解相應(yīng)問(wèn)題來(lái)看，在有向圖中求頂點(diǎn)的度，采用鄰接矩陣比鄰接表表示更方便。一、深度優(yōu)先遍歷一、深度優(yōu)先遍歷二、廣度優(yōu)先遍歷二、廣度優(yōu)先遍歷第3節(jié) 圖的遍歷o圖的遍歷：是指從圖中任意一個(gè)頂點(diǎn)出發(fā)，對(duì)途中所有頂點(diǎn)訪問(wèn)一次且僅訪

10、問(wèn)一次。n深度優(yōu)先遍歷（DFS depth-first search）n廣度優(yōu)先遍歷（BFS breadth-first search）o類(lèi)似于樹(shù)的先根遍歷o從圖的某一頂點(diǎn)V0出發(fā)，首先訪問(wèn)起始點(diǎn)V0，然后選擇V0的一個(gè)尚未訪問(wèn)過(guò)的鄰接點(diǎn)W，從W出發(fā)繼續(xù)進(jìn)行深度優(yōu)先遍歷，即選擇W的一個(gè)尚未訪問(wèn)過(guò)的鄰接點(diǎn)出發(fā)繼續(xù)進(jìn)行深度優(yōu)先遍歷，直到被訪問(wèn)的頂點(diǎn)及其鄰接點(diǎn)均被訪問(wèn)過(guò)為止，o回溯到該頂點(diǎn)訪問(wèn)前的頂點(diǎn)，繼續(xù)訪問(wèn)其它尚未訪問(wèn)過(guò)的鄰接點(diǎn)o不斷回溯，直到起始點(diǎn)V03.1 深度優(yōu)先遍歷1 12 23 34 47 78 85 56 6從頂點(diǎn)從頂點(diǎn)1 1出發(fā)的深度優(yōu)先遍歷序列可出發(fā)的深度優(yōu)先遍歷序列可有多種有多

11、種, ,如如: :1,2,5,8,4,7,3,61,2,5,8,4,7,3,61,3,6,8,7,4,2,51,3,6,8,7,4,2,51 11 12 24 48 85 56 63 37 72 24 48 85 56 63 37 7o在深度優(yōu)先遍歷中要使用到棧來(lái)保存已訪問(wèn)的結(jié)點(diǎn)，或保存已訪問(wèn)頂點(diǎn)的所有尚未訪問(wèn)過(guò)的鄰接點(diǎn)。使用鄰接矩陣存儲(chǔ)struct graph /定義圖的數(shù)據(jù)結(jié)構(gòu)int vn+1; /存放頂點(diǎn)信息v1,v2,.不用v0int arcsn+1n+1;int visitedn+1; /訪問(wèn)標(biāo)志數(shù)組,0表示未訪問(wèn),1表示已訪問(wèn)void dfs(graph g,int n , int

12、 i) /從頂點(diǎn)i出發(fā)進(jìn)行深度優(yōu)先搜索遍歷int j;coutg.vi ; /輸出訪問(wèn)節(jié)點(diǎn)visitedi=1; /全局?jǐn)?shù)組標(biāo)記置1,表示已訪問(wèn)for(j=1;j=n;j+)if (g.arcsij=1)&(!visitedj) dfs(graph g,int n, int j);struct link /定義鏈表類(lèi)型(表結(jié)點(diǎn))int Adjvex;link *nextarc;struct node /定義鄰接表的表頭類(lèi)型(頭結(jié)點(diǎn))int vexdata; /頂點(diǎn)信息link *firarc; an+1;鄰接域鄰接域數(shù)據(jù)域數(shù)據(jù)域鏈域鏈域表結(jié)點(diǎn)表結(jié)點(diǎn)數(shù)據(jù)域數(shù)據(jù)域鏈域鏈域頭結(jié)點(diǎn)頭結(jié)點(diǎn)Adj

13、vex data nextarcvexdata firarc例：基于鄰接表的深度優(yōu)先遍歷void dfs(int i) /從頂點(diǎn)i出發(fā)進(jìn)行深度優(yōu)先遍歷link *p;coutai.vexdataAdjvex) /adjvex為表結(jié)點(diǎn)的鄰接域dfs1(p-Adjvex);p=p-nextarc;o類(lèi)似于樹(shù)的層次遍歷o在訪問(wèn)了起始點(diǎn)V0后，o首先依次訪問(wèn)V0的各個(gè)鄰接點(diǎn)，o再依次訪問(wèn)這些頂點(diǎn)中未被訪問(wèn)過(guò)的鄰接點(diǎn)，以此類(lèi)推o直到所有被訪問(wèn)到的頂點(diǎn)的鄰接點(diǎn)都被訪問(wèn)過(guò)為止3.2 廣度優(yōu)先遍歷例：廣度優(yōu)先遍歷例：廣度優(yōu)先遍歷1 12 23 34 47 78 85 56 6從頂點(diǎn)從頂點(diǎn)1出發(fā)的廣度優(yōu)先遍歷序

14、列可出發(fā)的廣度優(yōu)先遍歷序列可有多種有多種,如如:1,3,2,7,6,5,4,81,2,3,5,4,7,6,81 12 24 48 85 56 63 37 7o在廣度優(yōu)先遍歷中，使用到了隊(duì)列來(lái)保存已訪問(wèn)過(guò)的頂點(diǎn)。o廣度優(yōu)先遍歷算法(鄰接表存儲(chǔ))void bfs(int i) /從頂點(diǎn)i出發(fā)進(jìn)行廣度優(yōu)先遍歷int qn+1; /定義q為隊(duì)列int f,r;link *p; /p為搜索指針f=r=0; /隊(duì)列指針初始化coutai.vexdata ;visitedi=1; /訪問(wèn)頂點(diǎn)ir+;qr=i; /起始點(diǎn)入隊(duì)while(fAdjvex) /尚未訪問(wèn)過(guò)coutAdjvexAdjvex=1;r+;

15、qr=p-Adjvex; /訪問(wèn)后進(jìn)隊(duì) p=p-nextarc; /找下一個(gè)鄰接點(diǎn) /end of function1 12 23 34 47 78 85 56 6一、單元最短路徑一、單元最短路徑二、拓?fù)渑判蚨⑼負(fù)渑判蛉?、關(guān)鍵路徑三、關(guān)鍵路徑第4節(jié) 圖的應(yīng)用圖的應(yīng)用非常廣泛，例如：圖的應(yīng)用非常廣泛，例如：用圖可以表示一座城市的交通聯(lián)系的情況；用有值圖可以表示兩座城市之間的距離、車(chē)費(fèi)、或班次數(shù)目；表示城市之間建立的通訊網(wǎng)絡(luò)；可以描述化學(xué)結(jié)構(gòu)式；圖中兩點(diǎn)之間的最短距離問(wèn)題。北京北京常州常州上海上海800100350o從有向網(wǎng)的源點(diǎn)到其它各終點(diǎn)有否路徑？最短路徑是什么？最短路徑長(zhǎng)度是多少？o兩個(gè)頂

16、點(diǎn)間長(zhǎng)度最短的路徑，不是指路徑上邊數(shù)的總和，而是指路徑上各邊權(quán)值的總和。o注意：路徑是一個(gè)結(jié)點(diǎn)序列，路徑的長(zhǎng)度是其權(quán)值的和，稱(chēng)為距離，所以最短路徑長(zhǎng)度就是最短距離。o單源最短路徑:圖中某結(jié)點(diǎn)到其他各結(jié)點(diǎn)的最短路徑。4.1 單源最短路徑 設(shè)置并逐步擴(kuò)充一個(gè)集合S，存放已求出其最短路徑的頂點(diǎn)，則尚未確定最短路徑的頂點(diǎn)集合是V-S，其中V為網(wǎng)中所有頂點(diǎn)集合。按最短路徑長(zhǎng)度遞增的順序逐個(gè)將V-S中的頂點(diǎn)加S中。10101 12 23 35 54 44 42 220206 62 21212V=1,2 ,3,4,5S=1W=V-S=2 ,3,4,5求單源最短路徑的(dijkstra)思想 設(shè)源點(diǎn)為V1，

17、W中頂點(diǎn)對(duì)應(yīng)的距離值初值是這樣規(guī)定的:若圖中有弧,則Vj頂點(diǎn)的距離為此弧權(quán)值，否則為1 12 23 35 54 44 42 220206 610102 21212V=1,2 ,3,4,5S=1W=V-S=2 , 3, 4, 5到V1的距離 2 6 20到V1的距離 0p然后每次從W中的頂點(diǎn)中選一個(gè)其距離值為最小的頂點(diǎn)Vm加入到S中，每往S中加入一個(gè)頂點(diǎn)Vm，就要對(duì)W中的各個(gè)頂點(diǎn)的距離值進(jìn)行一次修改。到到V1的距離的距離 2 6 20W=V-S=2 , 3, 4, 5到到V1的距離的距離 0到到V1的距離的距離 12 6 20 W=V-S=3, 4, 5到到V1的距離的距離 0 2修改后再在修改

18、后再在W W中選距離值最小的頂點(diǎn)加入到中選距離值最小的頂點(diǎn)加入到S S中中, ,如此進(jìn)行下去如此進(jìn)行下去, ,直到直到S S中包中包含了圖中所有頂點(diǎn)含了圖中所有頂點(diǎn). .o若加進(jìn)Vm做中間頂點(diǎn)，使+的值小于值，則用+代替原來(lái)Vj的距離。1 12 23 35 54 44220610212V=1,2 ,3,4,5S=1S=1,2迪克斯特拉迪克斯特拉(dijkstra)算法算法1 12 23 35 54 442206102120262012345Distpath100000 2 6 20 0 10 0 2 4 0 12 0S1211 12 23 34 45 51 2 3 4 5AS5,512Dist

19、i= Distu+Asu,iDist3= Dist2+As2,3=2+10=12411018311251求單源最短路徑算法求單源最短路徑算法#include#define max 20#define up 10000 /模擬無(wú)窮大值int costmaxmax; / cost：鄰接矩陣int distancemax; /存放各頂點(diǎn)的當(dāng)前最短路徑長(zhǎng)度int pathmax; /path：存放各頂點(diǎn)的當(dāng)前最短路徑int n,v0;void creatgraph() /建立有向網(wǎng)的鄰接矩陣int i,j,s,e,len,contin=1;coutn;for(i=1;i=n;i+)for(j=1;j=

20、n;j+)costij=costji=up;costii=0;cout輸入各邊,以0,0,0 結(jié)束endl;i=1;while(contin=1)coutt第i頂點(diǎn),頂點(diǎn),邊長(zhǎng):;cinselen;if (s=0 & e=0 & len=0)contin=0;else if (s=0 & s=0 & e0)costse=len;i+;elsecouttt邊值錯(cuò)誤,重新輸入!endl;void shortdjs() / 求單源最短路徑int smax;int mindis,dis,i,j,u; coutv0;for(i=1;i=n;i+) /賦初值distance

21、i=costv0i;if (distanceiup) pathi=v0;si=0;sv0=1;for(i=1;i=n;i+)mindis=up;for (j=1;j=n;j+)su=1; /u為已找到最短路徑的結(jié)點(diǎn),將其加入S中for(j=1;jdis)distancej=dis;pathj=u;void dispath() /輸出最短路徑int i,j,k;if(sj=0 & distancejmindis)u=j;mindis=distancej; /j結(jié)點(diǎn)不在S中,并且它到V0的距離最短for (i=1;i=n;i+)coutt (vv0vi): ;if (distanceiup

22、) coutdistancei ;elsecout % ;/顯示無(wú)窮大k=i;while(k!=v0)coutvk;k=pathk;coutvv0n ;void main()creatgraph();shortdjs();dispath();coutn 從v1到各頂點(diǎn)的最短路徑長(zhǎng)度如下:endl;cout終點(diǎn)) 最短長(zhǎng)度 最短路徑n;coutt- - -n;021061212345Dist11413path5 3 4 13 4 111111S112 14 0210612二、二、拓?fù)渑判蛲負(fù)渑判蛘n程號(hào)課程名先修課程C1計(jì)算機(jī)基礎(chǔ)C2高等數(shù)學(xué)C3離散數(shù)學(xué)C2C4高級(jí)語(yǔ)言程序設(shè)計(jì)C1C5數(shù)據(jù)結(jié)構(gòu)C4,C3C6操作系統(tǒng)C1,C4,C5C1C1C4C4C5C5C2C2C3C3C6C6AOV網(wǎng)作業(yè)活動(dòng)網(wǎng)1 12 23 34 45 56 6子工程子工程( (活動(dòng)活動(dòng)) )活動(dòng)間的活動(dòng)間的優(yōu)先關(guān)系優(yōu)先關(guān)系對(duì)于一項(xiàng)工程而言，人們關(guān)心：對(duì)于一項(xiàng)工程而言，人們關(guān)心：工程能否順利進(jìn)行（工程能否順利進(jìn)行（AOVAOV網(wǎng)中沒(méi)有回路）網(wǎng)中沒(méi)有回路）可依怎樣的順序完成可依怎樣的順序完成o將G中所有頂點(diǎn)排成一個(gè)線性序列，使得對(duì)圖中任一對(duì)頂點(diǎn)u和v，若E(G)(該有向邊在