图的邻接矩阵实现问题

《图的邻接矩阵实现问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图的邻接矩阵实现问题讨论组成员：设计目的通过对图遍历的程序编写，掌握邻接矩阵的定义，并对其进行深度优先搜索和广度优先搜索。1.测试图的手工表示结果。2.测试图的数据表示，邻接矩阵特点。邻接矩阵，对与图G，可用一个方阵A=(aij)n*n表示，其中aij=1，表示vi和vj之间有边，为0表示无边。邻接矩阵可表示自环和重边，在有向图中，aij表示定点vi和vj之间边的条数。无向图的邻接矩阵一定是对称的，而有向图的邻接矩阵不一定对称。因此，用邻接矩阵来表示一个具有n个顶点的有向图时需要n^2个单元来存储邻接矩阵；对有n个顶点的无向图则只存入上（下）三角阵中剔除了左上右

2、下对角线上的0元素后剩余的元素，故只需1+2+...+(n-1)=n(n-1)/2个单元。无向图邻接矩阵的第i行（或第i列）非零元素的个数正好是第i个顶点的度。有向图邻接矩阵中第i行非零元素的个数为第i个顶点的出度，第i列非零元素的个数为第i个顶点的入度，第i个顶点的度为第i行与第i列非零元素个数之和。用邻接矩阵表示图，很容易确定图中任意两个顶点是否有边相连。3.图的类设计方法。对于深度优先搜索我们采用递归操作；广度优先搜索采用非递归操作，在此过程中引用栈消除递归。类DFS用于深度优先搜索，栈g1为其边赋值。类BFS用于广度优先搜索，栈g2为其边赋值。图类Gra

3、phm用于定义图中顶点和边的相关信息。源程序：publicclassBFS{/***@paramargs*/publicstaticvoidmain(String[]args){//TODOAuto-generatedmethodstubcharm[]={'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.

4、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);

5、//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);for(inti=0;i<8;i++){for(intj=0;j<8;j++){System.out.print(g1.matrix[i][j]+"");}System.out.println();}}//深度优先搜索方法staticvoidDFS(GraphmG,intv,charm[]){System.o

6、ut.print(m[v]+"");G.setmark(v,1);for(intw=G.first(v);w

7、ear){front=(front+1)%vn;v=qu[front]-97;System.out.print(m[v]+"");for(w=G.first(v);w

8、];//二维矩阵，用于存