1、圖和圖的存儲結構圖和圖的存儲結構 圖的定義和術語圖的定義和術語 圖的存儲表示圖的存儲表示 小結小結用用java語言描述圖的存儲結構語言描述圖的存儲結構 課堂練習課堂練習1. 圖的定義圖的定義2. 圖的名詞和術語圖的名詞和術語3. 圖的基本操作圖的基本操作圖和圖的存儲結構圖和圖的存儲結構圖的定義圖的定義 圖(graph)是由一個頂點(vertex)集 v 和一個邊(edge|弧arc)集 e構成的數據結構。 graph = (v, e ) e(v,w| v,wv)每條邊(edge)是一副點對(v,w)，其中v,w v。表示從 v 到 w 的一條邊(弧)，稱 v 為弧尾(tail)，w 為弧頭(h

2、ead)。圖的定義圖的定義有向圖有向圖 如果“弧”是有方向的，則稱由頂點集和弧集構成的圖為有向圖有向圖(digraph)。eacbd例如例如: : g1 = (v1, e1)v1=a, b, c, d, ee1=, , , , , , 圖的定義圖的定義無向圖無向圖若若 e 必有必有 e,則以無序對則以無序對(v,w) 代替這兩個有序對，稱代替這兩個有序對，稱 (v,w) 為頂點為頂點 v 和頂和頂點點 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弧除了有向和無向的含義之外，有時候還具有弧除了有向和無向的含義之外，有時候還具有第三種成分，稱為權第三種成分，稱為權(weight)或值或值(cost)。名詞和術語名詞和術語1 1）子圖、網子圖、網 2 2）完全圖、稀疏圖、稠密圖完全圖、稀疏圖、稠密圖3 3）鄰接點、度、入度、出度鄰接點、度、入度、出度4 4）路徑、路徑長度、簡單路徑、簡單回路路徑、路徑長度、簡單路徑、簡單回路5 5）連通圖、強連通圖、弱連通圖連通圖、強連通圖、弱連通圖1）子圖、網

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

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

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

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

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

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

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

11、陣1 2 3 4 5 6 7 1325674tttttttttttt1234567圖的存儲表示圖的存儲表示-鄰接矩陣bacdfe無向圖：對稱矩陣無向圖：對稱矩陣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對于稠密(dense)圖合適。圖的存儲表示圖的存儲表示-鄰接表鄰接表(adjacency list)表示法：對每一個頂點，使用一個表存放所有鄰接的頂點。如果邊有權，那么這個附加信息也可以存儲在鄰接表中。1325674圖的存儲表示圖的存儲表示-鄰接表12345672,3,

12、44,563,6,74,7(empty)6l對于稀疏(sparse)圖合適。這種鄰接表本身可以被保存在任何種類的list中。arraylist和linkedlist。1325674圖的存儲表示圖的存儲表示-鄰接表鄰接表：圖的鏈式存儲結構鄰接表：圖的鏈式存儲結構對圖中每個頂點建立一個單鏈表，第對圖中每個頂點建立一個單鏈表，第i個單鏈個單鏈表中的節點表示依附頂點表中的節點表示依附頂點vi的邊。的邊。對有向圖來說，是指以頂點對有向圖來說，是指以頂點vi為弧尾的弧。為弧尾的弧。圖的存儲表示圖的存儲表示-鄰接表012345abcdef14043525011253bacdfe1）無向圖的鄰接表）無向圖的鄰

13、接表圖的存儲表示圖的存儲表示-鄰接表abecd01234abcde14301222）有向圖的鄰接表）有向圖的鄰接表-每個頂點鏈接的是以該頂點為每個頂點鏈接的是以該頂點為弧尾的弧弧尾的弧但，在有向圖的鄰接表中不易找到指向該頂點的弧。但，在有向圖的鄰接表中不易找到指向該頂點的弧。圖的存儲表示圖的存儲表示-鄰接表abecd3）有向圖的逆鄰接表）有向圖的逆鄰接表-每個頂點鏈接的是指向該每個頂點鏈接的是指向該頂點的弧頂點的弧0101234abcde32034圖的存儲表示圖的存儲表示-鄰接表鄰接表：圖的鏈式存儲結構鄰接表：圖的鏈式存儲結構adjvex nextarcinfo鄰接點域鄰接點域鏈域鏈域數據域（

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

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

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

17、v, w); / 返回 v 的（相對于 w 的） “下一個鄰接下一個鄰接 點點”。若 w 是 v 的最后一個鄰接點，則返回-1。存儲結構的比較存儲結構的比較鄰接矩陣：第v行鄰接表：第v個鏈表5、鄰接邊課堂練習課堂練習v1v2v3v4v51、鄰接矩陣2、鄰接表v2v1v4v31、鄰接矩陣2、鄰接表課堂練習課堂練習下面關于圖的存儲的敘述中正確的是（ ） a）用相鄰矩陣法存儲圖，占用的存儲空間大小只與圖中節點個數有關，而與邊數無關 b）用相鄰矩陣法存儲圖，占用的存儲空間大小只與圖中邊數有關，而與節點個數無關 c）用鄰接表法存儲圖，占用的存儲空間大小只與圖中節點個數有關，而與邊數無關 d）用鄰接表法存

18、儲圖，占用的存儲空間大小只與圖中邊數有關，而與節點個數無關 課堂練習課堂練習用用javajava語言描述存儲結構語言描述存儲結構1 1、鄰接點函數的實現鄰接點函數的實現2 2、創建圖創建圖3 3、圖的存儲方式的轉換圖的存儲方式的轉換( (自學自學) )鄰接點函數的實現鄰接點函數的實現012345abcdef14043525011253firstadjvex(a)firstadjvex(b)nextadjvex(a, 1);nextadjvex(b, 4);鄰接點函數的實現鄰接點函數的實現int firstadjvex(int v) arc p; p=vertexsv.firstarc; /v的

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

20、 1、圖的兩個個參數：頂點個數邊數（弧數）vertex(vertices)，vexnumedge(arc)，arcnum，edgenum2、圖的第三個參數：圖的類型graphkind=dg, udg, dn, udn創建圖創建圖1、輸入參數:vexnum, arcnum, graghkind2、輸入頂點信息3、根據graghkind，決定邊是否要帶權重4、采用某種形式逐條輸入邊，將它插入到存儲結構中建立存儲結構的一般步驟：創建圖創建圖void creategragh( ) /建立鄰接表/輸入頂點數vexnum，邊的條數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; 創建圖創建圖void createdg( ) for(i=0;ivexnum;i+) /輸入頂點信息,data為輸入的頂點數據verticesi.data = data for(i=0;iarcnum;i+) /輸入邊的信息,為輸入的弧信息p= new arcnode; /建立節點if(!p) return err

22、or;p.adjvex=w;p.nextarc=verticesv.firstarc; /頂點v的鏈表verticesv.firstarc=p; /添加到最左邊 創建圖創建圖void createudg( ) for(i=0;ivexnum;i+) /輸入頂點信息,data為輸入的頂點數據verticesi.data = data 創建圖創建圖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