“鄰接矩陣表示的帶權有向圖”演示程序

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

========實習報告十四“鄰接矩陣表示的帶權有向圖（網）”演示程序==========

（一）、程序的功能和特點

該程序可以建立有向圖的帶權鄰接矩陣，能夠對建立的鄰接矩陣進行添加頂點，添加邊和刪除頂點，刪除邊的操作，并能顯示輸出鄰接矩陣。該程序的特點是采納java面對對象語言，對邊，頂點和鄰接矩陣用類進行封裝。采納鏈式存儲結構。

（二）、程序的算法設計

算法一：“插入一個頂點”算法：

1.

規(guī)律結構：線性結構。

存儲結構：挨次存儲與鏈式存儲結合。

2.

文字說明：

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

3.

文字說明：

（1）.首先推斷頂點表是否滿。

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

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

（4）.插入頂點勝利，返回true。

4.

//插入一個頂點

publicintInsertVertex(charvertex){

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

//頂點表增加一個元素

VerticesList=vertex;

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

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

Edge=MaxValue;

Edge=MaxValue;

}

Edge=0;

CurrentVertices++;

returnCurrentVertices;//插入位置

}

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

1.

規(guī)律結構：線性結構。

存儲結構：鏈式存儲結構。

3.

文字說明：

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

4.

文字說明：

（1）.首先推斷插入邊上的兩個頂點編號是否越界。

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

（3）.否則創(chuàng)建新邊結點

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

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

4.

//插入一個邊

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

returnfalse;//出錯

if(v2CurrentVertices-1)

returnfalse;

Edge=weight;//網,有向邊

returntrue;

}

（三）、程序中類的設計

“Graph”類：

1.

規(guī)律結構：網狀結構。

存儲結構：挨次存儲與鏈式存儲結合。

2.

staticintMaxEdges=50;

staticintMaxVertices=10;

staticdoubleMaxValue=9999.9;//無窮大

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

privatecharVerticesList=newchar;

//鄰接矩陣（存放兩個頂點權值）

privatedoubleEdge=newdouble;

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

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

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

3.

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

publicintFindVertex(charvertex)：查找指定的頂點的序號

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

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

publiccharGetValue(inti)：按頂點序號返回頂點數(shù)據。

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

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

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

publicintGetFirstNeighbor(intv)：取得第一個鄰接點的序號

publicintInsertVertex(charvertex)：插入一個頂點。

publicbooleanRemoveVertex(intv)：刪除一個頂點。

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

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

publicvoiddisplay()：顯示鄰接矩陣。

4.

//“鄰接矩陣”類

classGraph{

staticintMaxEdges=50;

staticintMaxVertices=10;

staticdoubleMaxValue=9999.9;//無窮大

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

privatecharVerticesList=newchar;

//鄰接矩陣（存放兩個頂點權值）

privatedoubleEdge=newdouble;

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

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

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

publicGraph(){

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

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

if(i==j)

Edge=0;//對角線

else//非對角線上無窮大

Edge=MaxValue;

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

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

}

//查找指定的頂點的序號

publicintFindVertex(charvertex){

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

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

if(v2CurrentVertices-1)return-1.0;

returnEdge;

}

//取得第一個鄰接點的序號

publicintGetFirstNeighbor(intv){

if(vCurrentVertices-1)

return-1;//用-1表示出錯

//鄰接矩陣的行號和列號是兩個鄰接點的序號

for(intcol=0;col0

return-1;//無鄰接點

}

//插入一個頂點

publicintInsertVertex(charvertex){

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

//頂點表增加一個元素

VerticesList=vertex;

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

for(intj=0;jCurrentVertices-1)

returnfalse;//出錯

if(v2CurrentVertices-1)

returnfalse;

Edge=weight;//網,有向邊

returntrue;

}

//刪除一個頂點

publicbooleanRemoveVertex(intv){

if(vCurrentVertices-1)

returnfalse;//出錯

//修改頂點表

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

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

//掩蓋第v行

intj;

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

returnfalse;//用-1表示出錯

if(v2CurrentVertices-1)

returnfalse;

if(v1==v2)returnfalse;

Edge=MaxValue;//網,無路徑

returntrue;

}

//打印鄰接矩陣

publicvoiddisplay(){

inti,j;

System.out.println("頂點表");

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();//鄰接矩陣

//預備有向圖（網）數(shù)據

charc={'A','B','C','D','E','F'};//頂點

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};//權

//插入頂點

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

G.InsertVertex(c);

//插入弧

for(inti=0;i<