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

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

討論組成員：

設(shè)計(jì)目的

通過對(duì)圖遍歷的程序編寫，掌握鄰接矩陣的定義，并對(duì)其進(jìn)行深度優(yōu)先搜索和廣度優(yōu)先搜索。1.測(cè)試圖的手工表示結(jié)果。2.測(cè)試圖的數(shù)據(jù)表示，鄰接矩陣特點(diǎn)。鄰接矩陣，對(duì)與圖G，可用一個(gè)方陣A=(aij)n*n表示，其中aij=1，表示vi和vj之間有邊，為0表示無邊。鄰接矩陣可表示自環(huán)和重邊，在有向圖中，aij表示定點(diǎn)vi和vj之間邊的條數(shù)。無向圖的鄰接矩陣一定是對(duì)稱的，而有向圖的鄰接矩陣不一定對(duì)稱。因此，用鄰接矩陣來表示一個(gè)具有n個(gè)頂點(diǎn)的有向圖時(shí)需要n^2個(gè)單元來存儲(chǔ)鄰接矩陣；對(duì)有n個(gè)頂點(diǎn)的無向圖則只存入上（下）三角陣中剔除了左上右下對(duì)角線上的0元素后剩余的元素，故只需1+2+...+(n-1)=n(n-1)/2個(gè)單元。無向圖鄰接矩陣的第i行（或第i列）非零元素的個(gè)數(shù)正好是第i個(gè)頂點(diǎn)的度。有向圖鄰接矩陣中第i行非零元素的個(gè)數(shù)為第i個(gè)頂點(diǎn)的出度，第i列非零元素的個(gè)數(shù)為第i個(gè)頂點(diǎn)的入度，第i個(gè)頂點(diǎn)的度為第i行與第i列非零元素個(gè)數(shù)之和。用鄰接矩陣表示圖，很容易確定圖中任意兩個(gè)頂點(diǎn)是否有邊相連。源程序：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;//圖中頂點(diǎn)的個(gè)數(shù)numvertex，與邊的個(gè)數(shù)numedge publicintmatrix[][]=newint[8][8];//二維矩陣，用于存儲(chǔ)邊的信息 intmark[]=newint[8];//數(shù)組，用于存儲(chǔ)圖中的頂點(diǎn)是否被訪問 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()//返回圖中頂點(diǎn)的個(gè)數(shù) { returnnumvertex; } inte()//返回圖中邊的個(gè)數(shù) { returnnumedge; } intfirst(intv)//尋找與頂點(diǎn)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)//返回由頂點(diǎn)v1與v2構(gòu)成的邊的權(quán)重 { returnmatrix[v1][v2]; } intgetmark(intv)//返回頂點(diǎn)v的標(biāo)識(shí)信息 { returnmark[v]; } voidsetmark(intv,intval)//設(shè)置頂點(diǎn)v的標(biāo)識(shí)信息 { mark[v