1、數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（Java版）版）葉核亞葉核亞數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（Java版）版） 第1章 緒論 第2章 線性表 第3章 排序 第4章 棧與隊列 第5章 數(shù)組和廣義表 第6章 樹和二叉樹 第7章 查找第8章 圖 第9章 綜合應(yīng)用設(shè)計第8章 圖 8.1 圖的基本知識 8.2 圖的存儲結(jié)構(gòu) 8.3 圖的遍歷 8.4 最小代價生成樹 8.5 最短路徑數(shù)據(jù)結(jié)構(gòu)（Java版）葉核亞8.1 圖的基本知識n8.1.1 圖的定義n8.1.2 結(jié)點的度n8.1.3 子圖n8.1.4 路徑、回路及連通性數(shù)據(jù)結(jié)構(gòu)（Java版）葉核亞8.1.1 圖的定義n圖（graph）是由結(jié)點集合及結(jié)點間的關(guān)系集合組成的一種數(shù)據(jù)

2、結(jié)構(gòu)。圖中的結(jié)點又稱為頂點，結(jié)點之間的關(guān)系稱為邊（edge）。一個圖G記作G=(V, E)n其中，V是結(jié)點x的有限集合，E是邊的有限集合。即V=x|x某個數(shù)據(jù)元素集合E=(x,y)|x,yV 或 E=x,y|x,yV n其中，(x,y)表示從結(jié)點x到y(tǒng)的一條雙向通路，即(x,y)沒有方向；x,y表示從結(jié)點x到y(tǒng)的一條單向通路，即x,y是有方向的。 數(shù)據(jù)結(jié)構(gòu)（Java版）葉核亞數(shù)據(jù)結(jié)構(gòu)（Java版）葉核亞1無向圖G1V(G1)=A, B, C, DE(G1)=(C,A), (C,A), (A,D), (A,D), (A,B), (C,B), (B,D)2有向圖G2V(G3)=v1, v2, v3

3、E(G3)=v1, v2,v2, v1,v2, v3,v3, v3數(shù)據(jù)結(jié)構(gòu)（Java版）葉核亞3完全圖數(shù)據(jù)結(jié)構(gòu)（Java版）葉核亞4帶權(quán)圖5相鄰結(jié)點數(shù)據(jù)結(jié)構(gòu)（Java版）葉核亞8.1.2 結(jié)點的度1度、入度、出度n圖中與結(jié)點v相關(guān)聯(lián)的邊的數(shù)目稱為結(jié)點的度（degree），記作TD(v)。 2度與邊的關(guān)系niive1)(TD21evvvevvniiniiniiniinii2)(OD)(ID)(TD)(OD)(ID11111數(shù)據(jù)結(jié)構(gòu)（Java版）葉核亞8.1.3 子圖n1子圖、真子圖n2生成子圖n如果G是G的子圖，且V=V，稱圖G是G的生成子圖。數(shù)據(jù)結(jié)構(gòu)（Java版）葉核亞8.1.4 路徑、回路及

4、連通性n1路徑、路徑長度、回路n2有根的圖、圖的根n3連通圖n4強連通圖數(shù)據(jù)結(jié)構(gòu)（Java版）葉核亞8.2 圖的存儲結(jié)構(gòu)n8.2.1 鄰接矩陣n8.2.2 鄰接表數(shù)據(jù)結(jié)構(gòu)（Java版）葉核亞8.2.1 鄰接矩陣1鄰接矩陣的定義2鄰接矩陣與結(jié)點的度EvvEvvEvvEvvajijijijiij,),(0,),(1或若或若0101000011000010011110101101101021AA數(shù)據(jù)結(jié)構(gòu)（Java版）葉核亞3帶權(quán)圖的鄰接矩陣jijijijijijijijiijvvEvvEvvvvEvvEvvvvvvwa若或且若或且若0,),(,),(),(0320654009790382730686

5、0525054AA數(shù)據(jù)結(jié)構(gòu)（Java版）葉核亞4聲明以鄰接矩陣存儲的圖類public class Graph1 protected int n; /圖的結(jié)點個數(shù) protected int mat; /二維數(shù)組存儲圖的鄰接矩陣數(shù)據(jù)結(jié)構(gòu)（Java版）葉核亞8.2.2 鄰接表n1無向圖的鄰接表數(shù)據(jù)結(jié)構(gòu)（Java版）葉核亞2有向圖的鄰接表數(shù)據(jù)結(jié)構(gòu)（Java版）葉核亞3聲明以鄰接表存儲的圖類nimport ds_java.OnelinkNode; /單向鏈表的結(jié)點類npublic class Graph2 /以鄰接表存儲的圖類nn private OnelinkNode table; /圖的鄰接表n數(shù)

6、據(jù)結(jié)構(gòu)（Java版）葉核亞8.3 圖的遍歷n8.3.1 深度優(yōu)先遍歷n8.3.2 廣度優(yōu)先遍歷數(shù)據(jù)結(jié)構(gòu)（Java版）葉核亞8.3.1 深度優(yōu)先遍歷n1深度優(yōu)先遍歷算法描述數(shù)據(jù)結(jié)構(gòu)（Java版）葉核亞2以鄰接矩陣存儲的圖的深度優(yōu)先遍歷算法實現(xiàn)package ds_java;public class Graph1 /以鄰接矩陣存儲的圖類 protected int n; /圖的結(jié)點個數(shù) protected int mat; /二維數(shù)組存儲圖的鄰接矩陣 protected int visited; /訪問標記數(shù)組 public Graph1(int m1) n=m1.length; mat=new

7、intnn; System.arraycopy(m1,0,mat,0,n); /System類方法，復(fù)制數(shù)組 visited=new int n; public Graph1() 數(shù)據(jù)結(jié)構(gòu)（Java版）葉核亞【例8.1】 以鄰接矩陣表示的圖的深度優(yōu)先遍歷算法測試。import ds_java.Tree1;public class Graph1_ex /圖類的測試 public static void main(String args) int mat1=0,1,0,1, /無向圖G6的鄰接矩陣 1,0,1,1, 0,1,0,1, 1,1,1,0; Graph1 g1=new Graph1(ma

8、t1); g1.depthFirstSearch(); 程序運行結(jié)果如下：深度優(yōu)先遍歷Depth first search:數(shù)據(jù)結(jié)構(gòu)（Java版）葉核亞3以鄰接表存儲的圖的深度優(yōu)先遍歷算法實現(xiàn)import ds_java.OnelinkNode; /單向鏈表的結(jié)點類public class Graph2 extends Graph1 /以鄰接表存儲的圖類 private OnelinkNode table; /圖的鄰接表 public Graph2(int mat) /以鄰接矩陣建立圖的鄰接表 n=mat.length; /繼承Graph1類的成員 table=new OnelinkNoden

9、+1; /建立結(jié)點表，多一個元素 OnelinkNode p=null,q; int i,j; for(i=1;i=n;i+) /table0不用， /結(jié)點序號i與table中的下標一致 tablei=new OnelinkNode(i); /創(chuàng)建i在結(jié)點表中的元素 p=tablei; /建立結(jié)點i的出邊表 for(j=1;j=n;j+) /查找與i相鄰的其他結(jié)點j數(shù)據(jù)結(jié)構(gòu)（Java版）葉核亞8.3.2 廣度優(yōu)先遍歷1廣度優(yōu)先遍歷算法描述數(shù)據(jù)結(jié)構(gòu)（Java版）葉核亞2以鄰接矩陣存儲的圖的廣度優(yōu)先遍歷算法實現(xiàn)import ds_java.Queue2; /鏈式隊列，元素類型為int public

10、 void breadthFirstSearch() /圖的廣度優(yōu)先遍歷 /k為起始結(jié)點序號 System.out.println(廣度優(yōu)先遍歷Breadth first search:); for(int k=1;k); /訪問起始結(jié)點 visitedi=1; /設(shè)置訪問標記 q2.enqueue(i); /訪問過的結(jié)點入隊 while(!q2.isEmpty() /隊列不空時 i=q2.dequeue(); /出隊 if(tablei!=null) /查找有邊相連的另一結(jié)點 數(shù)據(jù)結(jié)構(gòu)（Java版）葉核亞8.4 最小代價生成樹n8.4.1 樹與圖n8.4.2 生成樹n8.4.3 最小代價生成

11、樹數(shù)據(jù)結(jié)構(gòu)（Java版）葉核亞8.4.1 樹與圖圖8.11 樹、森林與圖數(shù)據(jù)結(jié)構(gòu)（Java版）葉核亞【例8.2】 以樹結(jié)構(gòu)描述測試假幣的稱重策略。數(shù)據(jù)結(jié)構(gòu)（Java版）葉核亞8.4.2 生成樹n1生成樹的定義n如果圖T是無向圖G的生成子圖且T是樹，則圖T稱為圖G的生成樹。數(shù)據(jù)結(jié)構(gòu)（Java版）葉核亞n2生成森林n3帶權(quán)圖的生成樹數(shù)據(jù)結(jié)構(gòu)（Java版）葉核亞8.4.3 最小代價生成樹n設(shè)G是一個連通的帶權(quán)圖，w(e)為邊e上的權(quán)，T為G的生成樹，那么T中各邊權(quán)之和為n上式稱為生成樹T的權(quán)，也稱為生成樹的代價（cost）。權(quán)最小的生成樹稱為最小生成樹或最小代價生成樹。TeewTw)()(數(shù)據(jù)結(jié)構(gòu)（Java版）葉核亞1克魯斯卡爾算法數(shù)據(jù)結(jié)構(gòu)（Java版）葉核亞2普里姆算法數(shù)據(jù)結(jié)構(gòu)（Java版）葉核亞8.5 最短路徑n1單源最短路徑源 點終 點路 徑路徑長度最短路徑v1v2(v1, v2)2(v1, v3, v2)12v 3(v1, v3)4(v1, v2, v3)10v 4(v1, v4)5(v1, v3, v4)10v 5(v1, v2, v5)11(v1, v3, v5)7(v1, v4, v5)12數(shù)據(jù)結(jié)構(gòu)（Java版）葉核亞2所有結(jié)點之間的最短路徑表8.2 最短路徑表源 點終 點最短路徑路徑長度v1v