图的邻接矩阵实现问题.ppt

图的邻接矩阵实现问题讨论组成员:设计目的通过对图遍历的程序编写,掌握邻接矩阵的定义,并对其进行深度优先搜索和广度优先搜索。。,邻接矩阵特点。邻接矩阵,对与图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列非零元素个数之和。用邻接矩阵表示图,很容易确定图中任意两个顶点是否有边相连。。对于深度优先搜索我们采用递归操作;广度优先搜索采用非递归操作,在此过程中引用栈消除递归。类DFS用于深度优先搜索,栈g1为其边赋值。类BFS用于广度优先搜索,栈g2为其边赋值。图类Graphm用于定义图中顶点和边的相关信息。源程序:lassBFS{ /** ****@paramargs */ publicstaticvoidmain(String[]args){ //TODOAuto-generatedmethodstub charm[]={'a','b','c','d','e','f','g','h'}; Graphmg1=newGraphm(8); //给图的边赋值 (0,1,1); (1,3,1); (1,4,1); (3,7,1); (4,7,1); (0,2,1); (2,5,1); (2,6,1); (5,6,1);//深度优先搜索方法// ("深度优先输出:");// DFS(g1,0,m);// ();// // Graphmg2=newGraphm(8);// //给图的边赋值// (0,1,1);// (1,3,1);// (1,4,1);// (3,7,1);// (4,7,1);// (0,2,1);// (2,5,1);// (2,6,1);// (5,6,1);// ("广度度优先输出:");// BFS(g2,0,m,8);for(inti=0;i<8;i++){ for(intj=0;j<8;j++){ ([i][j]+""); } (); } } //深度优先搜索方法 staticvoidDFS(GraphmG,intv,charm[]) { (m[v]+""); (v,1); for(intw=(v);w<();w=(v,w)) if((w)==0) DFS(G,w,m); } //广度优先搜索方法staticvoidBFS(GraphmG,intstart,charm[],intv1) { intv,w; intvn=v1+1; intqu[]=newint[vn]; intfront,rear; front=rear=0; rear++; qu[rear]=m[start]; (start,1); while(front!=rear) { front=(front+1)%vn; v=qu[front]-97; (m[v]+""); for(w=(v);w<();w=(v,w)) if((w)==0) { (w,1); qu[++rear]=m[w]; } } }}/***图类****@authorAdministrator**/classGraphm{ intnumvertex,numedge;//图中顶点的个