數(shù)據(jù)結(jié)構(gòu)java第07章圖

1、葉核亞葉核亞數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)（java版版）（第（第2版版）數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)（java版版）（第（第2版）版）第0章 java程序設(shè)計基礎(chǔ)第1章 緒論第2章 線性表第3章 棧與隊列第4章 串第5章 數(shù)組和廣義表第6章 樹和二叉樹第7章 圖第8章 查找第9章 排序第10章 綜合應(yīng)用設(shè)計第11章 java開發(fā)運行環(huán)境數(shù)據(jù)結(jié)構(gòu)（java版）（第2版）第第7章章 圖圖l7.1 圖及其抽象數(shù)據(jù)類型圖及其抽象數(shù)據(jù)類型l7.2 圖的表示和實現(xiàn)圖的表示和實現(xiàn)l7.3 圖的遍歷圖的遍歷l7.4 最小生成樹最小生成樹l7.5 最短路徑最短路徑 目的：目的：理解圖結(jié)構(gòu)。理解圖結(jié)構(gòu)。 要求：要求：掌握圖的存儲結(jié)構(gòu)和操

2、作實現(xiàn)。掌握圖的存儲結(jié)構(gòu)和操作實現(xiàn)。 重點：重點：圖的兩種存儲結(jié)構(gòu)，遍歷算法，最小生成圖的兩種存儲結(jié)構(gòu)，遍歷算法，最小生成 樹，最短路徑。樹，最短路徑。 難點：難點：圖的存儲和操作實現(xiàn)，最小生成樹，最短圖的存儲和操作實現(xiàn)，最小生成樹，最短 路徑。路徑。數(shù)據(jù)結(jié)構(gòu)（java版）（第2版）7.1 圖及其抽象數(shù)據(jù)類型圖及其抽象數(shù)據(jù)類型 7.1.1 圖的基本概念圖的基本概念1.圖的定義和術(shù)語圖的定義和術(shù)語 g=(v, e) v=a | a某個數(shù)據(jù)元素集合某個數(shù)據(jù)元素集合 e=(a, b) | a, bv 無向圖無向圖 有向圖有向圖 數(shù)據(jù)結(jié)構(gòu)（java版）（第2版）完全圖完全圖帶權(quán)圖帶權(quán)圖 鄰接頂點鄰接頂

3、點 數(shù)據(jù)結(jié)構(gòu)（java版）（第2版）2.頂點的度頂點的度 deg(a)=indeg(a)outdeg(a)3.子圖子圖數(shù)據(jù)結(jié)構(gòu)（java版）（第2版）4.路徑路徑 5.連通性連通性數(shù)據(jù)結(jié)構(gòu)（java版）（第2版）7.1.2 圖抽象數(shù)據(jù)類型圖抽象數(shù)據(jù)類型public interface ggraph /圖接口圖接口 int vertexcount(); /返回頂點數(shù)返回頂點數(shù) e get(int i); /返回頂點返回頂點vi元素元素 boolean insertvertex(e vertex); /插入頂點插入頂點 boolean insertedge(int i, int j, int we

4、ight); /插入邊插入邊 boolean removevertex(int v); /刪除頂點刪除頂點 boolean removeedge(int i, int j); /刪除邊刪除邊 int getfirstneighbor(int v); /返回鄰接頂點序號返回鄰接頂點序號 int getnextneighbor(int v, int w); /返回下一個鄰接頂點返回下一個鄰接頂點數(shù)據(jù)結(jié)構(gòu)（java版）（第2版）7.2 圖的表示和實現(xiàn)圖的表示和實現(xiàn)7.2.1 圖的鄰接矩陣表示圖的鄰接矩陣表示7.2.2 圖的鄰接表表示圖的鄰接表表示數(shù)據(jù)結(jié)構(gòu)（java版）（第2版）7.2.1 圖的鄰接矩

5、陣表示圖的鄰接矩陣表示1.鄰接矩陣鄰接矩陣 不帶權(quán)圖的鄰接矩陣不帶權(quán)圖的鄰接矩陣帶權(quán)圖的鄰接矩陣帶權(quán)圖的鄰接矩陣 1若(v ,v )或v ,v0若(v ,v )或v ,vijijijijijeeaee數(shù)據(jù)結(jié)構(gòu)（java版）（第2版）2.鄰接矩陣表示的帶權(quán)圖類鄰接矩陣表示的帶權(quán)圖類 鄰接矩陣表示的帶權(quán)圖類的聲明及構(gòu)造方法鄰接矩陣表示的帶權(quán)圖類的聲明及構(gòu)造方法 n頂點集合a,b,c,d,e; n邊集合 (0,1,5), (0,3,2), (1,0,5), (1,2,7), (1,3,6), (2,1,7), (2,3,8), (2,4,3), (3,0,2),(3,1,6), (3,2,8), (

6、3,4,9), (4,2,3), (4,3,9);圖的插入操作圖的插入操作數(shù)據(jù)結(jié)構(gòu)（java版）（第2版）圖的刪除操作圖的刪除操作 帶權(quán)值的邊類帶權(quán)值的邊類 鄰接矩陣表示的帶權(quán)圖類鄰接矩陣表示的帶權(quán)圖類 數(shù)據(jù)結(jié)構(gòu)（java版）（第2版）7.2.2 圖的鄰接表表示圖的鄰接表表示1.鄰接表鄰接表無向圖的鄰接表表示無向圖的鄰接表表示 數(shù)據(jù)結(jié)構(gòu)（java版）（第2版）有向圖的鄰接表表示有向圖的鄰接表表示 數(shù)據(jù)結(jié)構(gòu)（java版）（第2版）2.鄰接表表示的帶權(quán)圖類鄰接表表示的帶權(quán)圖類 頂點表元素類頂點表元素類鄰接表表示的帶權(quán)圖類的聲明及構(gòu)造方法鄰接表表示的帶權(quán)圖類的聲明及構(gòu)造方法圖的插入操作圖的插入操作

7、數(shù)據(jù)結(jié)構(gòu)（java版）（第2版）圖的刪除操作圖的刪除操作 鄰接表表示的圖類鄰接表表示的圖類cadebc2567893(a) 在g3的鄰接表存儲結(jié)構(gòu)中刪除頂點c刪除頂點及邊單鏈表adeb2569(b) 刪除頂點c之后未刪除的邊結(jié)點更改某些頂點序號adbe01234052717380216233936432849111222333344153200daeb0123050216292639112223152200數(shù)據(jù)結(jié)構(gòu)（java版）（第2版）7.3 圖的遍歷圖的遍歷7.3.1 圖的深度優(yōu)先搜索遍歷圖的深度優(yōu)先搜索遍歷7.3.2 圖的廣度優(yōu)先搜索遍歷圖的廣度優(yōu)先搜索遍歷數(shù)據(jù)結(jié)構(gòu)（java版）（第2版）7.3.1 圖的深度優(yōu)先搜索遍歷圖的深度優(yōu)先搜索遍歷數(shù)據(jù)結(jié)構(gòu)（java版）（第2版）7.3.2 圖的廣度優(yōu)先搜索遍歷圖的廣度優(yōu)先搜索遍歷數(shù)據(jù)結(jié)構(gòu)（java版）（第2版）7.4 最小生成樹最小生成樹7.4.1 生成樹生成樹1.樹樹2.生成樹和生成森林生成樹和生成森林 3.最小生成樹最小生成樹 數(shù)據(jù)結(jié)構(gòu)（java版）（第2版）7.4.2 最小