图的邻接矩阵实现问题 (2)幻灯片.ppt

《图的邻接矩阵实现问题 (2)幻灯片.ppt》由会员分享，可在线阅读，更多相关《图的邻接矩阵实现问题 (2)幻灯片.ppt（16页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、图的邻接矩阵实现问题2023/4/8第1页，共16页，编辑于2022年，星期五设计目的 通过对图遍历的程序编写，掌握邻接矩阵的定义，并对其进行深度优先搜索和广度优先搜索。1.测试图的手工表示结果。测试图的手工表示结果。第2页，共16页，编辑于2022年，星期五2.测试图的数据表示，邻接矩阵特点。测试图的数据表示，邻接矩阵特点。邻接矩阵，对与图G，可用一个方阵A=(aij)n*n表示，其中aij=1，表示vi和vj之间有边，为0表示无边。邻接矩阵可表示自环和重边，在有向图中，aij表示定点vi和vj之间边的条数。无向图的邻接矩阵一定是对称的，而有向图的邻接矩阵不一定对称。因此，用邻接矩阵来表示一

2、个具有n个顶点的有向图时需要n2个单元来存储邻接矩阵；对有n个顶点的无向图则只存入上（下）三角阵中剔除了左上右下对角线上的0元素后剩余的元素，故只需1+2+.+(n-1)=n(n-1)/2个单元。无向图邻接矩阵的第i行（或第i列）非零元素的个数正好是第i个顶点的度。有向图邻接矩阵中第i行非零元素的个数为第i个顶点的出度，第i列非零元素的个数为第i个顶点的入度，第i个顶点的度为第i行与第i列非零元素个数之和。用邻接矩阵表示图，很容易确定图中任意两个顶点是否有边相连。第3页，共16页，编辑于2022年，星期五3.图的类设计方法。图的类设计方法。对于深度优先搜索我们采用递归操作；广度优先搜索采用非递

3、归操作，在此过对于深度优先搜索我们采用递归操作；广度优先搜索采用非递归操作，在此过程中引用栈消除递归。程中引用栈消除递归。类类DFS用于深度优先搜索，栈用于深度优先搜索，栈g1为其边赋值。为其边赋值。类类BFS用于广度优先搜索，栈用于广度优先搜索，栈g2为其边赋值。为其边赋值。图类图类Graphm用于定义图中顶点和边的相关信息。用于定义图中顶点和边的相关信息。第4页，共16页，编辑于2022年，星期五第5页，共16页，编辑于2022年，星期五源程序：public class BFS/*param args*/public static void main(String args)/TODO A

4、uto-generated method stubchar m=a,b,c,d,e,f,g,h;Graphm g1=new Graphm(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);2023/4/8第6页，共16页，编辑于2022年，星期五/深度优先搜索方法/System.out.println(深

5、度优先输出：);/DFS(g1,0,m);/System.out.println();/Graphm g2=new Graphm(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);2023/4/8第

6、7页，共16页，编辑于2022年，星期五for(int i=0;i8;i+)for(int j=0;j8;j+)System.out.print(g1.matrixij+);System.out.println();/深度优先搜索方法static void DFS(Graphm G,int v,char m)System.out.print(mv+);G.setmark(v,1);for(int w=G.first(v);wG.n();w=G.next(v,w)if(G.getmark(w)=0)DFS(G,w,m);/广度优先搜索方法2023/4/8第8页，共16页，编辑于2022年，星期五

7、static void BFS(Graphm G,int start,char m,int v1)int v,w;int vn=v1+1;int qu=new intvn;int front,rear;front=rear=0;rear+;qurear=mstart;G.setmark(start,1);while(front!=rear)front=(front+1)%vn;v=qufront-97;System.out.print(mv+);for(w=G.first(v);wG.n();w=G.next(v,w)if(G.getmark(w)=0)G.setmark(w,1);qu+re

8、ar=mw;2023/4/8第9页，共16页，编辑于2022年，星期五/*图类*author Administrator*/class Graphm int numvertex,numedge;/图中顶点的个数numvertex，与边的个数numedgepublic int matrix=new int88;/二维矩阵，用于存储边的信息int mark=new int8;/数组，用于存储图中的顶点是否被访问public Graphm(int numvert)/图的构造函数int i,j;numvertex=numvert;numedge=0;2023/4/8第10页，共16页，编辑于2022年

9、，星期五for(i=0;inumvertex;i+)for(j=0;jnumvertex;j+)matrixij=0;/赋初值没被访问0int n()/返回图中顶点的个数return numvertex;int e()/返回图中边的个数return numedge;int first(int v)/寻找与顶点v相邻最近的元素int i;for(i=0;inumvertex;i+)if(matrixvi!=0)return i;return i;2023/4/8第11页，共16页，编辑于2022年，星期五int next(int v1,int v2)/寻找在顶点v2后与顶点v1相邻最近的元素in

10、t i;for(i=v2+1;inumvertex;i+)if(matrixv1i!=0)return i;return i;void setedge(int v1,int v2,int wgt)/设置由顶点v1与v2构成的边的权重if(matrixv1v2=0)numedge+;matrixv1v2=wgt;void deledge(int v1,int v2)/删除由顶点v1与v2构成的边2023/4/8第12页，共16页，编辑于2022年，星期五if(matrixv1v2!=0)numedge-;matrixv1v2=0;int weight(int v1,int v2)/返回由顶点v1

11、与v2构成的边的权重return matrixv1v2;int getmark(int v)/返回顶点v的标识信息return markv;void setmark(int v,int val)/设置顶点v的标识信息markv=val;void clear()/清除图的顶点的标识信息2023/4/8第13页，共16页，编辑于2022年，星期五void clear()/清除图的顶点的标识信息for(int i=0;inumvertex;i+)marki=0;2023/4/8第14页，共16页，编辑于2022年，星期五4.测试结果测试结果第15页，共16页，编辑于2022年，星期五5.遇到的问题初次使用eclipse，很多功能都不是很熟悉。小组分工不明确，导致实验进度缓慢。刚开始接触java，很多语句用法和C、C+不相同，需要慢慢摸索。2023/4/8第16页，共16页，编辑于2022年，星期五