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

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

討論組成員：

設(shè)計目的

通過對圖遍歷的程序編寫，掌握鄰接矩陣的定義，并對其進行深度優(yōu)先搜索和廣度優(yōu)先搜索。1.測試圖的手工表示結(jié)果。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ù)之和。用鄰接矩陣表示圖，很容易確定圖中任意兩個頂點是否有邊相連。源程序：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); //深度優(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);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]; } } }}/***圖類*@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;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; }{ 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的標識信息 { returnmark[v]; } voidsetmark(intv,intval)//設(shè)置頂點v的標識信息 { mark[v