“鄰接矩陣表示的帶權(quán)有向圖”演示程序

“鄰接矩陣表示的帶權(quán)有向圖”演示程序班級(jí):信息1102姓名：賈孟濤

========實(shí)習(xí)報(bào)告十四“鄰接矩陣表示的帶權(quán)有向圖（網(wǎng)）”演示程序==========

（一）、程序的功能和特點(diǎn)

該程序可以建立有向圖的帶權(quán)鄰接矩陣，能夠?qū)⒌泥徑泳仃囘M(jìn)行添加頂點(diǎn)，添加邊和刪除頂點(diǎn)，刪除邊的操作，并能顯示輸出鄰接矩陣。該程序的特點(diǎn)是采納java面對(duì)對(duì)象語言，對(duì)邊，頂點(diǎn)和鄰接矩陣用類進(jìn)行封裝。采納鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

（二）、程序的算法設(shè)計(jì)

算法一：“插入一個(gè)頂點(diǎn)”算法：

1.

規(guī)律結(jié)構(gòu)：線性結(jié)構(gòu)。

存儲(chǔ)結(jié)構(gòu)：挨次存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)結(jié)合。

2.

文字說明：

創(chuàng)建新結(jié)點(diǎn)，找到結(jié)點(diǎn)L位置，在L后插入新結(jié)點(diǎn)。

3.

文字說明：

（1）.首先推斷頂點(diǎn)表是否滿。

（2）.若滿則插入失敗，放回false。

（3）.頂點(diǎn)表若不滿，創(chuàng)建新頂點(diǎn)，將新頂點(diǎn)加入頂點(diǎn)表。

（4）.插入頂點(diǎn)勝利，返回true。

4.

//插入一個(gè)頂點(diǎn)

publicintInsertVertex(charvertex){

if(IsGraphFull())return-1;//插入失敗

//頂點(diǎn)表增加一個(gè)元素

VerticesList=vertex;

//鄰接矩陣增加一行一列

for(intj=0;j<=CurrentVertices;j++){

Edge=MaxValue;

Edge=MaxValue;

}

Edge=0;

CurrentVertices++;

returnCurrentVertices;//插入位置

}

算法二：“插入一條邊”算法：

1.

規(guī)律結(jié)構(gòu)：線性結(jié)構(gòu)。

存儲(chǔ)結(jié)構(gòu)：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

3.

文字說明：

創(chuàng)建新邊結(jié)點(diǎn)，再將新創(chuàng)建的邊結(jié)點(diǎn)插入圖中。

4.

文字說明：

（1）.首先推斷插入邊上的兩個(gè)頂點(diǎn)編號(hào)是否越界。

if(v1CurrentVertices-1)returnfalse;if(v2CurrentVertices-1)returnfalse;（2）.假如越界則插入失敗，返回false。

（3）.否則創(chuàng)建新邊結(jié)點(diǎn)

（4）.再將新創(chuàng)建的邊結(jié)點(diǎn)插入圖中

（5).插入勝利返回true。

4.

//插入一個(gè)邊

publicbooleanInsertEdge(intv1,intv2,doubleweight){if(v1CurrentVertices-1)

returnfalse;//出錯(cuò)

if(v2CurrentVertices-1)

returnfalse;

Edge=weight;//網(wǎng),有向邊

returntrue;

}

（三）、程序中類的設(shè)計(jì)

“Graph”類：

1.

規(guī)律結(jié)構(gòu)：網(wǎng)狀結(jié)構(gòu)。

存儲(chǔ)結(jié)構(gòu)：挨次存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)結(jié)合。

2.

staticintMaxEdges=50;

staticintMaxVertices=10;

staticdoubleMaxValue=9999.9;//無窮大

//存放頂點(diǎn)的數(shù)組

privatecharVerticesList=newchar;

//鄰接矩陣（存放兩個(gè)頂點(diǎn)權(quán)值）

privatedoubleEdge=newdouble;

privateintCurrentEdges;//現(xiàn)有邊數(shù)

privateintCurrentVertices;//現(xiàn)有頂點(diǎn)數(shù)

//構(gòu)造函數(shù)：建立空的鄰接矩陣

3.

publicGraph()：為定義的構(gòu)造函數(shù)，建立空的鄰接矩陣。

publicintFindVertex(charvertex)：查找指定的頂點(diǎn)的序號(hào)

publicbooleanIsGraphEmpty()：推斷圖是否為空。

publicbooleanIsGraphFull()：推斷圖是否為滿。

publiccharGetValue(inti)：按頂點(diǎn)序號(hào)返回頂點(diǎn)數(shù)據(jù)。

publicintNumberOfVertices()：返回圖的頂點(diǎn)數(shù)。

publicintNumberOfEdges()：返回圖的邊數(shù)。

publicdoubleGetWeight(intv1,intv2)：取得一條邊的權(quán)值。

publicintGetFirstNeighbor(intv)：取得第一個(gè)鄰接點(diǎn)的序號(hào)

publicintInsertVertex(charvertex)：插入一個(gè)頂點(diǎn)。

publicbooleanRemoveVertex(intv)：刪除一個(gè)頂點(diǎn)。

publicbooleanInsertEdge(intv1,intv2,doubleweight)：插入一條邊。

publicbooleanRemoveEdge(intv1,intv2)：刪除一條邊。

publicvoiddisplay()：顯示鄰接矩陣。

4.

//“鄰接矩陣”類

classGraph{

staticintMaxEdges=50;

staticintMaxVertices=10;

staticdoubleMaxValue=9999.9;//無窮大

//存放頂點(diǎn)的數(shù)組

privatecharVerticesList=newchar;

//鄰接矩陣（存放兩個(gè)頂點(diǎn)權(quán)值）

privatedoubleEdge=newdouble;

privateintCurrentEdges;//現(xiàn)有邊數(shù)

privateintCurrentVertices;//現(xiàn)有頂點(diǎn)數(shù)

//構(gòu)造函數(shù)：建立空的鄰接矩陣

publicGraph(){

for(inti=0;i<MaxVertices;i++)

for(intj=0;j<MaxVertices;j++)

if(i==j)

Edge=0;//對(duì)角線

else//非對(duì)角線上無窮大

Edge=MaxValue;

CurrentEdges=0;//現(xiàn)有邊數(shù)

CurrentVertices=0;//現(xiàn)有頂點(diǎn)數(shù)

}

//查找指定的頂點(diǎn)的序號(hào)

publicintFindVertex(charvertex){

//在頂點(diǎn)數(shù)組里面查找

for(inti=0;iCurrentVertices-1)return-1.0;//用-1表示出錯(cuò)

if(v2CurrentVertices-1)return-1.0;

returnEdge;

}

//取得第一個(gè)鄰接點(diǎn)的序號(hào)

publicintGetFirstNeighbor(intv){

if(vCurrentVertices-1)

return-1;//用-1表示出錯(cuò)

//鄰接矩陣的行號(hào)和列號(hào)是兩個(gè)鄰接點(diǎn)的序號(hào)

for(intcol=0;col0

return-1;//無鄰接點(diǎn)

}

//插入一個(gè)頂點(diǎn)

publicintInsertVertex(charvertex){

if(IsGraphFull())return-1;//插入失敗

//頂點(diǎn)表增加一個(gè)元素

VerticesList=vertex;

//鄰接矩陣增加一行一列

for(intj=0;jCurrentVertices-1)

returnfalse;//出錯(cuò)

if(v2CurrentVertices-1)

returnfalse;

Edge=weight;//網(wǎng),有向邊

returntrue;

}

//刪除一個(gè)頂點(diǎn)

publicbooleanRemoveVertex(intv){

if(vCurrentVertices-1)

returnfalse;//出錯(cuò)

//修改頂點(diǎn)表

for(inti=v+1;i0//第v行

for(inti=0;i0//第v列

//掩蓋第v行

intj;

for(inti=v+1;iCurrentVertices-1)

returnfalse;//用-1表示出錯(cuò)

if(v2CurrentVertices-1)

returnfalse;

if(v1==v2)returnfalse;

Edge=MaxValue;//網(wǎng),無路徑

returntrue;

}

//打印鄰接矩陣

publicvoiddisplay(){

inti,j;

System.out.println("頂點(diǎn)表");

for(i=0;i<CurrentVertices;i++)

System.out.print(VerticesList+"");

System.out.println('\n'+"鄰接矩陣");

for(i=0;i<CurrentVertices;i++){

for(j=0;j<CurrentVertices;j++)

if(Edge==MaxValue)

System.out.print('@'+"");

else

System.out.print(Edge+"");

System.out.println();

}

}

//主函數(shù)

publicstaticvoidmain(Stringargs){

GraphG=newGraph();//鄰接矩陣

//預(yù)備有向圖（網(wǎng)）數(shù)據(jù)

charc={'A','B','C','D','E','F'};//頂點(diǎn)

intv={//弧

{0,1},{0,3},{1,2},{2,3},{4,5},

{1,3},{2,4},{3,5},{4,3},{2,5}

};

doublee={2.3,3.6,6.5,2.5,1.7,

0.8,7.2,9.1,5.2,1.3};//權(quán)

//插入頂點(diǎn)

for(inti=0;i<6;i++)

G.InsertVertex(c);

//插入弧

for(inti=0;i<