圖的鄰接矩陣實現(xiàn)問題

圖的鄰接矩陣實現(xiàn)問題第一頁，共十六頁，2022年，8月28日設(shè)計目的

通過對圖遍歷的程序編寫，掌握鄰接矩陣的定義，并對其進行深度優(yōu)先搜索和廣度優(yōu)先搜索。1.測試圖的手工表示結(jié)果。第二頁，共十六頁，2022年，8月28日2.測試圖的數(shù)據(jù)表示，鄰接矩陣特點。鄰接矩陣，對與圖G，可用一個方陣A=(aij)n*n表示，其中aij=1，表示vi和vj之間有邊，為0表示無邊。鄰接矩陣可表示自環(huán)和重邊，在有向圖中，aij表示定點vi和vj之間邊的條數(shù)。無向圖的鄰接矩陣一定是對稱的，而有向圖的鄰接矩陣不一定對稱。因此，用鄰接矩陣來表示一個具有n個頂點的有向圖時需要n^2個單元來存儲鄰接矩陣；對有n個頂點的無向圖則只存入上（下）三角陣中剔除了左上右下對角線上的0元素后剩余的元素，故只需1+2+...+(n-1)=n(n-1)/2個單元。無向圖鄰接矩陣的第i行（或第i列）非零元素的個數(shù)正好是第i個頂點的度。有向圖鄰接矩陣中第i行非零元素的個數(shù)為第i個頂點的出度，第i列非零元素的個數(shù)為第i個頂點的入度，第i個頂點的度為第i行與第i列非零元素個數(shù)之和。用鄰接矩陣表示圖，很容易確定圖中任意兩個頂點是否有邊相連。第三頁，共十六頁，2022年，8月28日3.圖的類設(shè)計方法。對于深度優(yōu)先搜索我們采用遞歸操作；廣度優(yōu)先搜索采用非遞歸操作，在此過程中引用棧消除遞歸。類DFS用于深度優(yōu)先搜索，棧g1為其邊賦值。類BFS用于廣度優(yōu)先搜索，棧g2為其邊賦值。圖類Graphm用于定義圖中頂點和邊的相關(guān)信息。第四頁，共十六頁，2022年，8月28日第五頁，共十六頁，2022年，8月28日源程序：publicclassBFS{ /** *@paramargs */ publicstaticvoidmain(String[]args){ //TODOAuto-generatedmethodstub charm[]={'a','b','c','d','e','f','g','h'}; Graphmg1=newGraphm(8); //給圖的邊賦值

g1.setedge(0,1,1); g1.setedge(1,3,1); g1.setedge(1,4,1); g1.setedge(3,7,1); g1.setedge(4,7,1); g1.setedge(0,2,1); g1.setedge(2,5,1); g1.setedge(2,6,1); g1.setedge(5,6,1);第六頁，共十六頁，2022年，8月28日

//深度優(yōu)先搜索方法// System.out.println("深度優(yōu)先輸出：");// DFS(g1,0,m);// System.out.println();// // Graphmg2=newGraphm(8);// //給圖的邊賦值// g2.setedge(0,1,1);// g2.setedge(1,3,1);// g2.setedge(1,4,1);// g2.setedge(3,7,1);// g2.setedge(4,7,1);// g2.setedge(0,2,1);// g2.setedge(2,5,1);// g2.setedge(2,6,1);// g2.setedge(5,6,1);// System.out.println("廣度度優(yōu)先輸出：");// BFS(g2,0,m,8);第七頁，共十六頁，2022年，8月28日

for(inti=0;i<8;i++){ for(intj=0;j<8;j++){ System.out.print(g1.matrix[i][j]+""); } System.out.println(); } } //深度優(yōu)先搜索方法

staticvoidDFS(GraphmG,intv,charm[]) { System.out.print(m[v]+""); G.setmark(v,1); for(intw=G.first(v);w<G.n();w=G.next(v,w)) if(G.getmark(w)==0) DFS(G,w,m); } //廣度優(yōu)先搜索方法第八頁，共十六頁，2022年，8月28日staticvoidBFS(GraphmG,intstart,charm[],intv1) { intv,w; intvn=v1+1; intqu[]=newint[vn]; intfront,rear; front=rear=0; rear++; qu[rear]=m[start]; G.setmark(start,1); while(front!=rear) { front=(front+1)%vn; v=qu[front]-97; System.out.print(m[v]+""); for(w=G.first(v);w<G.n();w=G.next(v,w)) if(G.getmark(w)==0) { G.setmark(w,1); qu[++rear]=m[w]; } } }}第九頁，共十六頁，2022年，8月28日/***圖類*@authorAdministrator**/classGraphm{

intnumvertex,numedge;//圖中頂點的個數(shù)numvertex，與邊的個數(shù)numedge publicintmatrix[][]=newint[8][8];//二維矩陣，用于存儲邊的信息

intmark[]=newint[8];//數(shù)組，用于存儲圖中的頂點是否被訪問

publicGraphm(intnumvert)//圖的構(gòu)造函數(shù)

{ inti,j; numvertex=numvert;numedge=0;第十頁，共十六頁，2022年，8月28日for(i=0;i<numvertex;i++) for(j=0;j<numvertex;j++) matrix[i][j]=0;//賦初值沒被訪問0 } intn()//返回圖中頂點的個數(shù)

{ returnnumvertex; } inte()//返回圖中邊的個數(shù)

{ returnnumedge; } intfirst(intv)//尋找與頂點v相鄰最近的元素

{ inti; for(i=0;i<numvertex;i++) { if(matrix[v][i]!=0) returni; } returni; }第十一頁，共十六頁，2022年，8月28日intnext(intv1,intv2)//尋找在頂點v2后與頂點v1相鄰最近的元素

{ inti; for(i=v2+1;i<numvertex;i++) { if(matrix[v1][i]!=0) returni; } returni; } voidsetedge(intv1,intv2,intwgt)//設(shè)置由頂點v1與v2構(gòu)成的邊的權(quán)重

{ if(matrix[v1][v2]==0) numedge++; matrix[v1][v2]=wgt; } voiddeledge(intv1,intv2)//刪除由頂點v1與v2構(gòu)成的邊第十二頁，共十六頁，2022年，8月28日{(diào) if(matrix[v1][v2]!=0) numedge--; matrix[v1][v2]=0; } intweight(intv1,intv2)//返回由頂點v1與v2構(gòu)成的邊的權(quán)重

{ returnmatrix[v1][v2]; } intgetmark(intv)//返回頂點v的標(biāo)識信息

{ returnmark[v]; } voidsetmark(intv,intval)//設(shè)置頂點v的標(biāo)識信息

{ mark[v]=val; } voidclear()//清除圖的頂點的標(biāo)識信息第十三頁，共十六頁，2022年，8月28日voidclear()//清除圖的頂點的標(biāo)識信息

{ f