鄰接表表示的帶權(quán)有向圖(網(wǎng))

1、=實(shí)習(xí)報(bào)告一“鄰接表表示的帶權(quán)有向圖（網(wǎng)）”演示程序 =（1） 、程序的功能和特點(diǎn)1. 程序功能：建立有向圖的帶權(quán)鄰接表，能夠?qū)⒌泥徑颖磉M(jìn)行添加頂點(diǎn)，添加邊和刪除頂點(diǎn)，刪除邊的操作，并能顯示輸出鄰接表。2. 程序特點(diǎn)：采用java面向?qū)ο笳Z(yǔ)言，對(duì)邊，頂點(diǎn)和鄰接表用類進(jìn)行封裝。采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。（二）、程序的算法設(shè)計(jì)算法一：“插入一個(gè)頂點(diǎn)”算法：1. 【邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)】 邏輯結(jié)構(gòu)：線性結(jié)構(gòu)。 存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)結(jié)合。 鄰接表(Adjacency List)是圖的一種順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)結(jié)合的存儲(chǔ)方法。鄰接表表示法類似于樹的孩子鏈表表示法。就是對(duì)于圖G中的每個(gè)頂點(diǎn)vi，將所有鄰

2、接于vi的頂點(diǎn)vj鏈成一個(gè)單鏈表，這個(gè)單鏈表就稱為頂點(diǎn)vi的鄰接表，再將所有點(diǎn)的鄰接表表頭放到數(shù)組中，就構(gòu)成了圖的鄰接表。如下圖就是一個(gè)臨界表的存儲(chǔ)圖。序號(hào) vertex firstedge0V0 1 3 V11 0 2 3 112V2 V3 3 0 1 圖的鄰接表表示在鄰接表表示中有兩種結(jié)點(diǎn)結(jié)構(gòu)，如圖所示。 頂點(diǎn)域 邊表頭指針 鄰接點(diǎn)域 指針域 next adjvexfirstedgevertex 頂點(diǎn)表 邊表 鄰接矩陣表示的結(jié)點(diǎn)結(jié)構(gòu)V0V1V2 頂點(diǎn)數(shù)組表的順序存儲(chǔ)： . 頂點(diǎn)域 邊指針2.【基本操作設(shè)計(jì)】 創(chuàng)建新結(jié)點(diǎn)，找到結(jié)點(diǎn)L位置，在 L后插入新結(jié)點(diǎn)。開始判斷頂點(diǎn)表滿否？ Y N插入失

3、敗Vertex t=new Vertex();創(chuàng)建頂點(diǎn)將創(chuàng)建的頂點(diǎn)加入頂點(diǎn)表返回true返回false插入失敗結(jié)束2. 【算法設(shè)計(jì)】 文字說(shuō)明： （1）.首先判斷頂點(diǎn)表是否滿。 （2）.若滿則插入失敗，放回false。 （3）.頂點(diǎn)表若不滿，創(chuàng)建新頂點(diǎn)，將新頂點(diǎn)加入頂點(diǎn)表。 （4）.插入頂點(diǎn)成功，返回true。 流程示意圖：頂點(diǎn)數(shù)據(jù)組成的數(shù)組。添加頂點(diǎn)前狀態(tài) 添加頂點(diǎn)v2后V0V1V0V1V24.【高級(jí)語(yǔ)言代碼】 /插入一個(gè)頂點(diǎn) public boolean InsertVertex ( char vertex ) if(NumVertices=MaxVertices)return false

4、; /頂點(diǎn)表滿Vertex t=new Vertex();t.data=vertex;t.adj=null;NodeTableNumVertices=t;NumVertices+;/注明：企圖以下賦值不合Java語(yǔ)法/NodeTableNumVertices.data=vertex;/NodeTableNumVertices.adj=null;return true;算法二：“插入一條邊”算法：1.【邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)】 邏輯結(jié)構(gòu)：線性結(jié)構(gòu)。 存儲(chǔ)結(jié)構(gòu)：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。 網(wǎng)圖的邊表結(jié)構(gòu)如圖所示。 鄰接點(diǎn)域 邊上信息 指針域 next info adjvex 網(wǎng)圖的邊表結(jié)構(gòu)2. 【基本操作設(shè)計(jì)

5、】 基本操作：開始判斷插入邊頂點(diǎn)v1，v2是否越界生成一個(gè)邊結(jié)點(diǎn)Edge E=new Edge(v2,weight);插入失敗返回false將生成的邊結(jié)點(diǎn)連接到v1結(jié)點(diǎn)為起點(diǎn)的最后Edge p=NodeTablev1.adj;循環(huán)插入邊結(jié)點(diǎn)NumEdges+，且邊數(shù)增加插入成功放回true結(jié)束3. 【算法設(shè)計(jì)】 文字說(shuō)明： （1）.首先判斷插入邊上的兩個(gè)頂點(diǎn)編號(hào)是否越界。 if(v1>=NumVertices |v1<0) return false;if(v2>=NumVertices |v2<0) return false; （2）.如果越界則插入失敗，返回false

6、。 （3）.否則創(chuàng)建新邊結(jié)點(diǎn)，以v2頂點(diǎn)和該邊上的權(quán)創(chuàng)建新邊結(jié)點(diǎn)。 （4）.再將新創(chuàng)建的邊結(jié)點(diǎn)連接到v1頂點(diǎn)的單鏈表后面。 （5).插入成功返回true。4.【高級(jí)語(yǔ)言代碼】/插入一條邊 public boolean InsertEdge ( int v1,int v2,double weight ) if(v1>=NumVertices |v1<0) return false;if(v2>=NumVertices |v2<0) return false;/生成一個(gè)邊結(jié)點(diǎn)，并賦值Edge E=new Edge(v2,weight); /鏈接在以v1為起點(diǎn)的單鏈表的最后E

7、dge p=NodeTablev1.adj;/插入第一個(gè)邊結(jié)點(diǎn)if( p=null ) NodeTablev1.adj=E;else /插入其它邊結(jié)點(diǎn)while(p.link!=null) p=p.link;p.link=E;NumEdges+; /當(dāng)前頂點(diǎn)數(shù) return true; return true; （三）、程序中類的設(shè)計(jì) “Edge”類：1. 【邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)】 邏輯結(jié)構(gòu)：線性結(jié)構(gòu)。 存儲(chǔ)結(jié)構(gòu)：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。 在鄰接表表示中邊結(jié)點(diǎn)結(jié)構(gòu)，如圖所示。 next cost dest 鄰接點(diǎn)域 邊上權(quán)值 指針域 邊表 鄰接矩陣表示的邊的結(jié)構(gòu)2. 【主要成員變量說(shuō)明】 主要成員變量有：

8、 int dest;表示鄰接點(diǎn)下標(biāo)。 double cost;表示邊上的權(quán)值 Edge link; 表示下一邊鏈接指針3. 【主要成員方法說(shuō)明】 link(int iD,double fD) 為結(jié)點(diǎn)類有兩個(gè)參數(shù)的構(gòu)造函數(shù)。 void linkDisplay()顯示結(jié)點(diǎn)自身的數(shù)據(jù)域。4.【高級(jí)語(yǔ)言代碼】 /邊結(jié)點(diǎn)類class Edge int dest;/鄰接點(diǎn)下標(biāo)double cost;/邊上的權(quán)值/下一邊鏈接指針Edge link; /構(gòu)造函數(shù):生成邊結(jié)點(diǎn)Edge ( int D, double C ) dest =D; cost =C; link =null; ; “Vertex”類：1.

9、 【邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)】 邏輯結(jié)構(gòu)：線性結(jié)構(gòu)。 存儲(chǔ)結(jié)構(gòu)：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。在鄰接表表示中頂點(diǎn)結(jié)構(gòu)，如圖所示。 頂點(diǎn)域 邊表頭指針 adjdata2. 【主要成員變量說(shuō)明】 主要成員變量為： char data;頂點(diǎn)的數(shù)據(jù)域。 Edge adj; 邊鏈表頭指針。3. 【主要成員方法說(shuō)明】 該類有默認(rèn)的構(gòu)造方法。4.【高級(jí)語(yǔ)言代碼】 /頂點(diǎn)類class Vertex char data;/頂點(diǎn)數(shù)據(jù) Edge adj; /邊鏈表頭指針;“GraphAdj ”類：4. 【邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)】 邏輯結(jié)構(gòu)：線性結(jié)構(gòu)。 存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)結(jié)合。 鄰接表(Adjacency List)是圖的一種順序存

10、儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)結(jié)合的存儲(chǔ)方法。序號(hào) vertex firstedge0V0 1 3 V11 0 2 3 112V2 V3 3 0 1 圖的鄰接表表示5. 【主要成員變量說(shuō)明】 主要成員變量為: static int DefaultSize = 20; 靜態(tài)缺省數(shù)據(jù)大小。 private Vertex NodeTable;頂點(diǎn)表數(shù)組。private int NumVertices;當(dāng)前頂點(diǎn)個(gè)數(shù)。private int MaxVertices;最大頂點(diǎn)個(gè)數(shù)。private int NumEdges; 當(dāng)前邊數(shù) 。 6. 【主要成員方法說(shuō)明】 public GraphAdj (int vn,char

11、v,int en,int e, double w)：為定義的構(gòu)造函數(shù)，建立圖的鄰接表。 public boolean GraphEmpty ( )：判斷圖是否為空。 public boolean GraphFull ( )：判斷圖是否為滿。 public char GetValue ( int i )：按頂點(diǎn)序號(hào)返回頂點(diǎn)數(shù)據(jù)。 public int NumberOfVertices ( )：返回圖的頂點(diǎn)數(shù)。 public int NumberOfEdges ( )：返回圖的邊數(shù)。 public boolean InsertVertex ( char vertex )：插入一個(gè)頂點(diǎn)。public

12、 boolean RemoveVertex ( int v )：刪除一個(gè)頂點(diǎn)。public boolean InsertEdge ( int v1,int v2,double weight )：插入一條邊。public boolean RemoveEdge ( int v1, int v2 )：刪除一條邊。public void display()：顯示鄰接表。4.【高級(jí)語(yǔ)言代碼】 /定義鄰接表類class GraphAdj static int DefaultSize = 20; private Vertex NodeTable; /頂點(diǎn)表private int NumVertices; /

13、當(dāng)前頂點(diǎn)個(gè)數(shù)private int MaxVertices; /最大頂點(diǎn)個(gè)數(shù)private int NumEdges; /當(dāng)前邊數(shù)/構(gòu)造函數(shù)：建立圖的鄰接表 public GraphAdj (int vn,char v,int en,int e, double w)/形參：頂點(diǎn)數(shù) 頂點(diǎn)數(shù)組 邊數(shù) 邊結(jié)點(diǎn)數(shù)組 權(quán)數(shù)組 int i; NumVertices=0; /當(dāng)前頂點(diǎn)數(shù)NumEdges=0; /當(dāng)前邊數(shù)/確定頂點(diǎn)表空間MaxVertices=vn>DefaultSize?vn:DefaultSize;NodeTable = /創(chuàng)建頂點(diǎn)表new VertexMaxVertices; /輸

14、入頂點(diǎn)for ( i = 0; i < vn; i+) InsertVertex ( vi ); /輸入邊。e為en行2列的數(shù)組een2 for ( i = 0; i < en; i+) InsertEdge ( ei0, ei1, wi ); public boolean GraphEmpty ( ) /圖空否? return NumVertices = 0; public boolean GraphFull ( ) /圖滿否?return NumVertices = MaxVertices; /按頂點(diǎn)序號(hào)返回頂點(diǎn)數(shù)據(jù)public char GetValue ( int i )

15、return i >= 0 && i < NumVertices ? NodeTablei.data :' ' /返回圖的頂點(diǎn)數(shù) public int NumberOfVertices ( ) return NumVertices; /返回圖的邊數(shù) public int NumberOfEdges ( ) return NumEdges; /插入一個(gè)頂點(diǎn) public boolean InsertVertex ( char vertex ) if(NumVertices=MaxVertices)return false; /頂點(diǎn)表滿Vertex t=

16、new Vertex();t.data=vertex;t.adj=null;NodeTableNumVertices=t;NumVertices+;/注明：企圖以下賦值不合Java語(yǔ)法/NodeTableNumVertices.data=vertex;/NodeTableNumVertices.adj=null;return true; /刪除一個(gè)頂點(diǎn) public boolean RemoveVertex ( int v ) /當(dāng)前頂點(diǎn)數(shù) NumVerticesif(v>=NumVertices |v<0) return false;/刪除邊鏈表NodeTablev.adj=nu

17、ll;for(int k=0;k<NumVertices;k+) /如果有指向V的邊，則需刪除Edge p=NodeTablek.adj;Edge q=p;while(p!=null) if(p.dest=v)if(q=p) /刪第一個(gè)邊結(jié)點(diǎn)NodeTablek.adj=p.link;else /刪后面的邊結(jié)點(diǎn)q.link=p.link;q=p;p=p.link; /從頂點(diǎn)表中刪除for(int i=v+1;i<NumVertices;i+)NodeTablei-1=NodeTablei;NumVertices-;for(int j=0;j<NumVertices-1;j+)

18、 /如果有以V以后的點(diǎn)為終點(diǎn)的點(diǎn)，則Edge p=NodeTablej.adj; /鄰接表中的dest屬性應(yīng)減1if(p!=null) /防止在添加頂點(diǎn)之后由于NumVertices加1 /而導(dǎo)致空指針異常 if(p.dest>v)p.dest=p.dest-1; while(p.link!=null) p=p.link; if(p.dest>v)p.dest=p.dest-1; /結(jié)束循環(huán)for jreturn true; /插入一條邊 public boolean InsertEdge ( int v1,int v2,double weight ) if(v1>=NumV

19、ertices |v1<0) return false;if(v2>=NumVertices |v2<0) return false;/生成一個(gè)邊結(jié)點(diǎn)，并賦值Edge E=new Edge(v2,weight); /鏈接在以v1為起點(diǎn)的單鏈表的最后Edge p=NodeTablev1.adj;/插入第一個(gè)邊結(jié)點(diǎn)if( p=null ) NodeTablev1.adj=E;else /插入其它邊結(jié)點(diǎn)while(p.link!=null) p=p.link;p.link=E;NumEdges+; /當(dāng)前頂點(diǎn)數(shù) return true; /刪除一條邊 public boolean

20、RemoveEdge ( int v1, int v2 ) if(v1>=NumVertices |v1<0) return false;if(v2>=NumVertices |v2<0) return false;/從第v1條單鏈表向后查找Edge p=NodeTablev1.adj;Edge q=p;while(p!=null) if(p.dest=v2)if(q=p) /刪第一個(gè)邊結(jié)點(diǎn)NodeTablev1.adj=p.link;else /刪后面的邊結(jié)點(diǎn)q.link=p.link;return true;q=p;p=p.link;return false; /顯示鄰接表public void display()Edge p;System.ou