1、圖和圖的存儲(chǔ)結(jié)構(gòu)圖和圖的存儲(chǔ)結(jié)構(gòu) 圖的定義和術(shù)語(yǔ)圖的定義和術(shù)語(yǔ) 圖的存儲(chǔ)表示圖的存儲(chǔ)表示 小結(jié)小結(jié)用用java語(yǔ)言描述圖的存儲(chǔ)結(jié)構(gòu)語(yǔ)言描述圖的存儲(chǔ)結(jié)構(gòu) 課堂練習(xí)課堂練習(xí)1. 圖的定義圖的定義2. 圖的名詞和術(shù)語(yǔ)圖的名詞和術(shù)語(yǔ)3. 圖的基本操作圖的基本操作圖和圖的存儲(chǔ)結(jié)構(gòu)圖和圖的存儲(chǔ)結(jié)構(gòu)圖的定義圖的定義 圖(graph)是由一個(gè)頂點(diǎn)(vertex)集 v 和一個(gè)邊(edge|弧arc)集 e構(gòu)成的數(shù)據(jù)結(jié)構(gòu)。 graph = (v, e ) e(v,w| v,wv)每條邊(edge)是一副點(diǎn)對(duì)(v,w)，其中v,w v。表示從 v 到 w 的一條邊(弧)，稱 v 為弧尾(tail)，w 為弧頭(h

2、ead)。圖的定義圖的定義有向圖有向圖 如果“弧”是有方向的，則稱由頂點(diǎn)集和弧集構(gòu)成的圖為有向圖有向圖(digraph)。eacbd例如例如: : g1 = (v1, e1)v1=a, b, c, d, ee1=, , , , , , 圖的定義圖的定義無(wú)向圖無(wú)向圖若若 e 必有必有 e,則以無(wú)序?qū)t以無(wú)序?qū)?v,w) 代替這兩個(gè)有序?qū)ΓQ代替這兩個(gè)有序?qū)ΓQ (v,w) 為頂點(diǎn)為頂點(diǎn) v 和頂和頂點(diǎn)點(diǎn) w 之間存在一條邊。之間存在一條邊。上述這種由頂點(diǎn)集和邊集構(gòu)成的圖稱作上述這種由頂點(diǎn)集和邊集構(gòu)成的圖稱作無(wú)向圖無(wú)向圖。圖的定義圖的定義無(wú)向圖無(wú)向圖例如例如: : g2=(v2,e2)bcafed

3、v2=a, b, c, d, e, fe2=(a, b), (a, e),(b, e), (b, f), (c, d), (c, f) (d, f弧除了有向和無(wú)向的含義之外，有時(shí)候還具有弧除了有向和無(wú)向的含義之外，有時(shí)候還具有第三種成分，稱為權(quán)第三種成分，稱為權(quán)(weight)或值或值(cost)。名詞和術(shù)語(yǔ)名詞和術(shù)語(yǔ)1 1）子圖、網(wǎng)子圖、網(wǎng) 2 2）完全圖、稀疏圖、稠密圖完全圖、稀疏圖、稠密圖3 3）鄰接點(diǎn)、度、入度、出度鄰接點(diǎn)、度、入度、出度4 4）路徑、路徑長(zhǎng)度、簡(jiǎn)單路徑、簡(jiǎn)單回路路徑、路徑長(zhǎng)度、簡(jiǎn)單路徑、簡(jiǎn)單回路5 5）連通圖、強(qiáng)連通圖、弱連通圖連通圖、強(qiáng)連通圖、弱連通圖1）子圖、網(wǎng)

4、設(shè)圖g=(v,e) 和圖 g=(v,e),且 vv, ee,則稱 g 為 g 的子圖。eacbdeacbdb名詞和術(shù)語(yǔ)名詞和術(shù)語(yǔ)弧或邊帶權(quán)的圖分別稱作有向網(wǎng)或無(wú)向網(wǎng)。abecd1597211132名詞和術(shù)語(yǔ)名詞和術(shù)語(yǔ)1）子圖、網(wǎng) 2）完全圖、稀疏圖、稠密圖假設(shè)圖中有 n 個(gè)頂點(diǎn)，e 條邊，則含有 e=n(n-1)/2 條邊的無(wú)向圖稱作完全圖;含有 e=n(n-1) 條弧的有向圖稱作有向完全圖;若邊或弧的個(gè)數(shù) enlogn，則稱作稀疏圖，否則稱作稠密圖。名詞和術(shù)語(yǔ)名詞和術(shù)語(yǔ)3）鄰接點(diǎn)、度、入度、出度鄰接點(diǎn)：假若頂點(diǎn)v和頂點(diǎn)w之間存在一條邊，則稱頂點(diǎn)v和w互為鄰接點(diǎn)，度：和頂點(diǎn)v關(guān)聯(lián)的邊的數(shù)目，記

5、為td（v）。邊(v,w)和頂點(diǎn)v和w相關(guān)聯(lián)。名詞和術(shù)語(yǔ)名詞和術(shù)語(yǔ)acdfebtd(b) = 3td(a) = 23）鄰接點(diǎn)、度、入度、出度abecd頂點(diǎn)的出度: 以頂點(diǎn)v 為弧尾的弧的數(shù)目;記為od（v）對(duì)于右圖所示的有向圖來(lái)說(shuō)，由于弧有方向性，則有入度和出度之分。名詞和術(shù)語(yǔ)名詞和術(shù)語(yǔ)3）鄰接點(diǎn)、度、入度、出度頂點(diǎn)的入度: 以頂點(diǎn)v為弧頭的弧的數(shù)目，記為id（v）頂點(diǎn)的度(td)=出度(od)+入度(id)id(b) = 2od(b) = 1td(b) = 3名詞和術(shù)語(yǔ)名詞和術(shù)語(yǔ)abecdid(a) = 1od(a) = 2td(a) = 33）鄰接點(diǎn)、度、入度、出度名詞和術(shù)語(yǔ)名詞和術(shù)語(yǔ)ab

6、ecd在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的（ ）倍。 a.1/2 b.1 c.2 d.4acdfeb思考思考abecd4）路徑、路徑長(zhǎng)度、簡(jiǎn)單路徑、簡(jiǎn)單回路、圈(環(huán))路徑：設(shè)圖g=(v,e)中的一個(gè)頂點(diǎn)序列u=v1,v2, , vn=w中，(vi,vi+1)e，0in，則稱從頂點(diǎn)u 到頂點(diǎn)w 之間存在一條路徑。如:從a到d長(zhǎng)度為 3 的路徑a,b,c,d名詞和術(shù)語(yǔ)名詞和術(shù)語(yǔ)路徑長(zhǎng)度：路徑上邊的數(shù)目。簡(jiǎn)單路徑:指序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑。簡(jiǎn)單回路:指序列中第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑。名詞和術(shù)語(yǔ)名詞和術(shù)語(yǔ)圈(cycle):是滿足v1=vn且長(zhǎng)至少為1的一條路徑。如果該路徑是簡(jiǎn)單路

7、徑，那么這個(gè)圈就是簡(jiǎn)單圈。一個(gè)有向無(wú)圈圖簡(jiǎn)稱為dag。abecd4）路徑、路徑長(zhǎng)度、簡(jiǎn)單路徑、簡(jiǎn)單回路、圈(環(huán))5）連通圖、強(qiáng)連通圖、弱連通圖連通圖：若無(wú)向圖g中任意兩個(gè)頂點(diǎn)之間都有路徑相通，則稱此圖為連通圖;bacdfe名詞和術(shù)語(yǔ)名詞和術(shù)語(yǔ)強(qiáng)連通圖：若有向圖任意兩個(gè)頂點(diǎn)之間都存在一條有向路徑，則稱為強(qiáng)連通圖。abecd名詞和術(shù)語(yǔ)名詞和術(shù)語(yǔ)若有向圖去掉弧的方向后是連通的，則稱為弱連通圖。5）連通圖、強(qiáng)連通圖、弱連通圖基本操作基本操作1.結(jié)構(gòu)的建立和銷毀結(jié)構(gòu)的建立和銷毀3.插入或刪除頂點(diǎn)插入或刪除頂點(diǎn)5.對(duì)鄰接點(diǎn)的操作對(duì)鄰接點(diǎn)的操作2.對(duì)頂點(diǎn)的訪問(wèn)操作對(duì)頂點(diǎn)的訪問(wèn)操作6.遍歷遍歷4.插入和刪除弧

8、插入和刪除弧creatgraph(v, e): / 按定義(v, e) 構(gòu)造圖destroygraph(g): / 銷毀圖1.結(jié)構(gòu)的建立和銷毀結(jié)構(gòu)的建立和銷毀基本操作基本操作2.對(duì)頂點(diǎn)的訪問(wèn)操作對(duì)頂點(diǎn)的訪問(wèn)操作locatevex(u); / 若g中存在頂點(diǎn)u，則返回該頂點(diǎn)在 / 圖中“位置位置” ；否則返回其它信息。getvex(v); / 返回 v 的值。putvex(v, value); / 對(duì) v 賦值value。基本操作基本操作3.插入或刪除頂點(diǎn)插入或刪除頂點(diǎn)insertvex(v); /在圖g中增添新頂點(diǎn)v。deletevex(v); / 刪除g中頂點(diǎn)v及其相關(guān)的弧。基本操作基本操作

9、4.插入和刪除弧插入和刪除弧insertarc(v, w); / 在g中增添弧，若g是無(wú)向的， /則還增添對(duì)稱弧。deletearc(v, w); /在g中刪除弧，若g是無(wú)向的， /則還刪除對(duì)稱弧。基本操作基本操作5.對(duì)鄰接點(diǎn)的操作對(duì)鄰接點(diǎn)的操作firstadjvex(v); / 返回 v 的“第一個(gè)鄰接點(diǎn)第一個(gè)鄰接點(diǎn)” 。若該頂點(diǎn)/在 g 中沒(méi)有鄰接點(diǎn)，則返回“空”。nextadjvex(v, w); / 返回 v 的（相對(duì)于 w 的） “下一個(gè)鄰接下一個(gè)鄰接 點(diǎn)點(diǎn)”。/ 若 w 是 v 的最后一個(gè)鄰接點(diǎn)，則返回“空”。基本操作基本操作6.6.遍歷遍歷dfstraverse(g, v); /

10、從頂點(diǎn)v起深度優(yōu)先深度優(yōu)先遍歷圖g。bfstraverse(g, v); /從頂點(diǎn)v起廣度優(yōu)先廣度優(yōu)先遍歷圖g。基本操作基本操作一、一、圖的數(shù)組圖的數(shù)組( (鄰接矩陣鄰接矩陣) )存儲(chǔ)表示存儲(chǔ)表示二、二、圖的鄰接表存儲(chǔ)表示圖的鄰接表存儲(chǔ)表示圖的存儲(chǔ)表示圖的存儲(chǔ)表示三、三、存儲(chǔ)結(jié)構(gòu)的比較存儲(chǔ)結(jié)構(gòu)的比較圖的存儲(chǔ)表示圖的存儲(chǔ)表示-鄰接矩陣1325674鄰接矩陣(adjacent matrix)表示法：使用一個(gè)二維數(shù)組，對(duì)于每一條邊(u,v)，置auv=true；否則，為false。如果邊有一個(gè)權(quán)，可以置auv等于該權(quán)，而使用一個(gè)很大或者很小的權(quán)作為標(biāo)記表示不存在的邊。圖的存儲(chǔ)表示圖的存儲(chǔ)表示-鄰接矩

11、陣1 2 3 4 5 6 7 1325674tttttttttttt1234567圖的存儲(chǔ)表示圖的存儲(chǔ)表示-鄰接矩陣bacdfe無(wú)向圖：對(duì)稱矩陣無(wú)向圖：對(duì)稱矩陣abcdefabcdef0 1 0 0 1 0 1 0 0 0 1 1 0 0 0 1 0 1 0 0 1 0 0 1 1 1 0 0 0 0 0 1 1 1 0 0 l對(duì)于稠密(dense)圖合適。圖的存儲(chǔ)表示圖的存儲(chǔ)表示-鄰接表鄰接表(adjacency list)表示法：對(duì)每一個(gè)頂點(diǎn)，使用一個(gè)表存放所有鄰接的頂點(diǎn)。如果邊有權(quán)，那么這個(gè)附加信息也可以存儲(chǔ)在鄰接表中。1325674圖的存儲(chǔ)表示圖的存儲(chǔ)表示-鄰接表12345672,3,

12、44,563,6,74,7(empty)6l對(duì)于稀疏(sparse)圖合適。這種鄰接表本身可以被保存在任何種類的list中。arraylist和linkedlist。1325674圖的存儲(chǔ)表示圖的存儲(chǔ)表示-鄰接表鄰接表：圖的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鄰接表：圖的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)對(duì)圖中每個(gè)頂點(diǎn)建立一個(gè)單鏈表，第對(duì)圖中每個(gè)頂點(diǎn)建立一個(gè)單鏈表，第i個(gè)單鏈個(gè)單鏈表中的節(jié)點(diǎn)表示依附頂點(diǎn)表中的節(jié)點(diǎn)表示依附頂點(diǎn)vi的邊。的邊。對(duì)有向圖來(lái)說(shuō)，是指以頂點(diǎn)對(duì)有向圖來(lái)說(shuō)，是指以頂點(diǎn)vi為弧尾的弧。為弧尾的弧。圖的存儲(chǔ)表示圖的存儲(chǔ)表示-鄰接表012345abcdef14043525011253bacdfe1）無(wú)向圖的鄰接表）無(wú)向圖的鄰

13、接表圖的存儲(chǔ)表示圖的存儲(chǔ)表示-鄰接表abecd01234abcde14301222）有向圖的鄰接表）有向圖的鄰接表-每個(gè)頂點(diǎn)鏈接的是以該頂點(diǎn)為每個(gè)頂點(diǎn)鏈接的是以該頂點(diǎn)為弧尾的弧弧尾的弧但，在有向圖的鄰接表中不易找到指向該頂點(diǎn)的弧。但，在有向圖的鄰接表中不易找到指向該頂點(diǎn)的弧。圖的存儲(chǔ)表示圖的存儲(chǔ)表示-鄰接表abecd3）有向圖的逆鄰接表）有向圖的逆鄰接表-每個(gè)頂點(diǎn)鏈接的是指向該每個(gè)頂點(diǎn)鏈接的是指向該頂點(diǎn)的弧頂點(diǎn)的弧0101234abcde32034圖的存儲(chǔ)表示圖的存儲(chǔ)表示-鄰接表鄰接表：圖的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鄰接表：圖的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)adjvex nextarcinfo鄰接點(diǎn)域鄰接點(diǎn)域鏈域鏈域數(shù)據(jù)域（

14、存放權(quán)值等）數(shù)據(jù)域（存放權(quán)值等）datafirstarc數(shù)據(jù)域數(shù)據(jù)域指向鏈表中第一個(gè)節(jié)點(diǎn)指向鏈表中第一個(gè)節(jié)點(diǎn)弧節(jié)點(diǎn)類弧節(jié)點(diǎn)類(鏈表節(jié)點(diǎn)類鏈表節(jié)點(diǎn)類)：頂點(diǎn)節(jié)點(diǎn)類頂點(diǎn)節(jié)點(diǎn)類：0101234abcde32034firstarc,弧節(jié)點(diǎn)類都屬于鏈表的node類。圖的存儲(chǔ)表示圖的存儲(chǔ)表示-鄰接表0101234abcde32034public class vertex anytype data;arc firstarc;/boolean visited;public class arcint adjvex;arc nextarc;/int weight;圖的存儲(chǔ)表示圖的存儲(chǔ)表示-鄰接表圖的鄰接表：1、容

15、易找到任意頂點(diǎn)的一個(gè)鄰接點(diǎn)2、但是要判定任意兩個(gè)頂點(diǎn)（vi，vj）之間是否有邊或者弧相連，需要搜索第i個(gè)或者第j個(gè)鏈表，不如鄰接矩陣方便。存儲(chǔ)結(jié)構(gòu)的比較存儲(chǔ)結(jié)構(gòu)的比較鄰接矩陣可用于dg、udg、dn、udn鄰接表可用于dg、udg、dn、udn一、應(yīng)用范圍存儲(chǔ)結(jié)構(gòu)的比較存儲(chǔ)結(jié)構(gòu)的比較鄰接矩陣: n + n2鄰接表用于dg和dn：n + e或者n + 2e；用于udg和udn：n + 2e二、存儲(chǔ)空間存儲(chǔ)結(jié)構(gòu)的比較存儲(chǔ)結(jié)構(gòu)的比較三、對(duì)操作的支持1、對(duì)頂點(diǎn)的訪問(wèn)locatevex(u); /返回u的位置getvex(v); / 返回 v 的值。putvex(u, value); / 對(duì) u 賦值v

16、alue。存儲(chǔ)結(jié)構(gòu)的比較存儲(chǔ)結(jié)構(gòu)的比較2、插入和刪除頂點(diǎn)都是對(duì)存放頂點(diǎn)數(shù)組元素的操作但是對(duì)鄰接矩陣，還要修改鄰接矩陣insertvex(v); /在圖g中增添新頂點(diǎn)v。deletevex(v); / 刪除g中頂點(diǎn)v及其相關(guān)的弧。存儲(chǔ)結(jié)構(gòu)的比較存儲(chǔ)結(jié)構(gòu)的比較3、插入和刪除弧insertarc(v, w); deletearc(v, w); 鄰接矩陣：修改邊（以及）鄰接表：無(wú)向圖，修改兩個(gè)頂點(diǎn)的鏈表；有向圖，修改一個(gè)（或兩個(gè)）頂點(diǎn)的鏈表存儲(chǔ)結(jié)構(gòu)的比較存儲(chǔ)結(jié)構(gòu)的比較4、鄰接點(diǎn)firstadjvex(v); / 返回 v 的“第一個(gè)鄰接點(diǎn)第一個(gè)鄰接點(diǎn)”。若沒(méi)有鄰接點(diǎn)，則返回-1。nextadjvex(

17、v, w); / 返回 v 的（相對(duì)于 w 的） “下一個(gè)鄰接下一個(gè)鄰接 點(diǎn)點(diǎn)”。若 w 是 v 的最后一個(gè)鄰接點(diǎn)，則返回-1。存儲(chǔ)結(jié)構(gòu)的比較存儲(chǔ)結(jié)構(gòu)的比較鄰接矩陣：第v行鄰接表：第v個(gè)鏈表5、鄰接邊課堂練習(xí)課堂練習(xí)v1v2v3v4v51、鄰接矩陣2、鄰接表v2v1v4v31、鄰接矩陣2、鄰接表課堂練習(xí)課堂練習(xí)下面關(guān)于圖的存儲(chǔ)的敘述中正確的是（ ） a）用相鄰矩陣法存儲(chǔ)圖，占用的存儲(chǔ)空間大小只與圖中節(jié)點(diǎn)個(gè)數(shù)有關(guān)，而與邊數(shù)無(wú)關(guān) b）用相鄰矩陣法存儲(chǔ)圖，占用的存儲(chǔ)空間大小只與圖中邊數(shù)有關(guān)，而與節(jié)點(diǎn)個(gè)數(shù)無(wú)關(guān) c）用鄰接表法存儲(chǔ)圖，占用的存儲(chǔ)空間大小只與圖中節(jié)點(diǎn)個(gè)數(shù)有關(guān)，而與邊數(shù)無(wú)關(guān) d）用鄰接表法存

18、儲(chǔ)圖，占用的存儲(chǔ)空間大小只與圖中邊數(shù)有關(guān)，而與節(jié)點(diǎn)個(gè)數(shù)無(wú)關(guān) 課堂練習(xí)課堂練習(xí)用用javajava語(yǔ)言描述存儲(chǔ)結(jié)構(gòu)語(yǔ)言描述存儲(chǔ)結(jié)構(gòu)1 1、鄰接點(diǎn)函數(shù)的實(shí)現(xiàn)鄰接點(diǎn)函數(shù)的實(shí)現(xiàn)2 2、創(chuàng)建圖創(chuàng)建圖3 3、圖的存儲(chǔ)方式的轉(zhuǎn)換圖的存儲(chǔ)方式的轉(zhuǎn)換( (自學(xué)自學(xué)) )鄰接點(diǎn)函數(shù)的實(shí)現(xiàn)鄰接點(diǎn)函數(shù)的實(shí)現(xiàn)012345abcdef14043525011253firstadjvex(a)firstadjvex(b)nextadjvex(a, 1);nextadjvex(b, 4);鄰接點(diǎn)函數(shù)的實(shí)現(xiàn)鄰接點(diǎn)函數(shù)的實(shí)現(xiàn)int firstadjvex(int v) arc p; p=vertexsv.firstarc; /v的

19、第1個(gè)鄰接點(diǎn) if(p=null) return -1; /無(wú)鄰接點(diǎn) return p.adjvex;鄰接點(diǎn)函數(shù)的實(shí)現(xiàn)鄰接點(diǎn)函數(shù)的實(shí)現(xiàn)int nextadjvex(int v, int w) arc p=vertexsv.firstarc; /v的第1個(gè)鄰接點(diǎn) while(p!=null & p.adjvex != w) p=p.nextarc; if(p!=null) p = p.nextarc; /w之后的下一個(gè)鄰接點(diǎn) if(p!=null) return p.adjvex; else return -1;創(chuàng)建圖創(chuàng)建圖bacdfe輸入邊形式1：.輸入邊形式2：.輸入頂點(diǎn)：a b c

20、 1、圖的兩個(gè)個(gè)參數(shù)：頂點(diǎn)個(gè)數(shù)邊數(shù)（弧數(shù)）vertex(vertices)，vexnumedge(arc)，arcnum，edgenum2、圖的第三個(gè)參數(shù)：圖的類型graphkind=dg, udg, dn, udn創(chuàng)建圖創(chuàng)建圖1、輸入?yún)?shù):vexnum, arcnum, graghkind2、輸入頂點(diǎn)信息3、根據(jù)graghkind，決定邊是否要帶權(quán)重4、采用某種形式逐條輸入邊，將它插入到存儲(chǔ)結(jié)構(gòu)中建立存儲(chǔ)結(jié)構(gòu)的一般步驟：創(chuàng)建圖創(chuàng)建圖void creategragh( ) /建立鄰接表/輸入頂點(diǎn)數(shù)vexnum，邊的條數(shù)arcnum，圖的類型graghkind。if switch(graghki

21、nd)case dg: return createdg( );case dn: return createdn( );case udg: return createudg( );case udn: return createudn( );default: return error; 創(chuàng)建圖創(chuàng)建圖void createdg( ) for(i=0;ivexnum;i+) /輸入頂點(diǎn)信息,data為輸入的頂點(diǎn)數(shù)據(jù)verticesi.data = data for(i=0;iarcnum;i+) /輸入邊的信息,為輸入的弧信息p= new arcnode; /建立節(jié)點(diǎn)if(!p) return err

22、or;p.adjvex=w;p.nextarc=verticesv.firstarc; /頂點(diǎn)v的鏈表verticesv.firstarc=p; /添加到最左邊 創(chuàng)建圖創(chuàng)建圖void createudg( ) for(i=0;ivexnum;i+) /輸入頂點(diǎn)信息,data為輸入的頂點(diǎn)數(shù)據(jù)verticesi.data = data 創(chuàng)建圖創(chuàng)建圖public void addedge(int start, int end) arc p=new arc(end); p.nextarc=vertexsstart.firstarc; vertexsstart.firstarc=p; arc q=new arc(start); q.next