图的邻接矩阵实现问题

图的邻接矩阵实现问题

讨论组成员：

设计目的

通过对图遍历的程序编写，掌握邻接矩阵的定义，并对其进行深度优先搜索和广度优先搜索。1.测试图的手工表示结果。2.测试图的数据表示，邻接矩阵特点。邻接矩阵，对与图G，可用一个方阵A=(aij)n*n表示，其中aij=1，表示vi和vj之间有边，为0表示无边。邻接矩阵可表示自环和重边，在有向图中，aij表示定点vi和vj之间边的条数。无向图的邻接矩阵一定是对称的，而有向图的邻接矩阵不一定对称。因此，用邻接矩阵来表示一个具有n个顶点的有向图时需要n^2个单元来存储邻接矩阵；对有n个顶点的无向图则只存入上（下）三角阵中剔除了左上右下对角线上的0元素后剩余的元素，故只需1+2+...+(n-1)=n(n-1)/2个单元。无向图邻接矩阵的第i行（或第i列）非零元素的个数正好是第i个顶点的度。有向图邻接矩阵中第i行非零元素的个数为第i个顶点的出度，第i列非零元素的个数为第i个顶点的入度，第i个顶点的度为第i行与第i列非零元素个数之和。用邻接矩阵表示图，很容易确定图中任意两个顶点是否有边相连。源程序：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); //深度优先搜索方法// System.out.println("深度优先输出：");// 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("广度度优先输出：");// 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;//图中顶点的个数numvertex，与边的个数numedge publicintmatrix[][]=newint[8][8];//二维矩阵，用于存储边的信息 intmark[]=newint[8];//数组，用于存储图中的顶点是否被访问 publicGraphm(intnumvert)//图的构造函数 { inti,j; numvertex=numvert;numedge=0;for(i=0;i<numvertex;i++) for(j=0;j<numvertex;j++) matrix[i][j]=0;//赋初值没被访问0 } intn()//返回图中顶点的个数 { returnnumvertex; } inte()//返回图中边的个数 { 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构成的边的权重 { returnmatrix[v1][v2]; } intgetmark(intv)//返回顶点v的标识信息 { returnmark[v]; } voidsetmark(intv,intval)//设置顶点v的标识信息 { mark[v