图的表示和操作(邻接矩阵)

《图的表示和操作(邻接矩阵)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验六图的表示和操作学号：200908204136姓名：熊军日期：第11周一、实验目的和要求理解图的基本概念，掌握图的邻接矩阵和邻接表储存结构，掌握对图进行插入、删除等操作的实现方法，掌握图的深度优先搜索额广度优先搜索遍历：理解最小生成树的概念，掌握构造最小树的Prim算法和Kruskal算法：掌握求单源最短路径问题的Dijkstra算法。二、实验内容1、【实验内容描述】分别对以邻接矩阵和邻接表存储的图，实现下列操作：（1）求图中的边数。（2）求有向图中各顶点的入度、出度。（3*）判断指定的一天路径是否为回路。2、逻辑结构设计【描述所用逻辑结构，给出逻辑操作接口】本实验采用的是逻辑设计结

2、构为图结构，图是一种元素之间具有多对多关系的非线性数据结构。图中的每个元素可有多个前驱元素和多个后继元素，任意两个元素都可以相邻。逻辑操作接口如下：publicinterfaceGGraph//图接口{intvertexCount();//返回顶点数Eget(inti);//返回顶点vi的数据元素booleaninsertVertex(Evertex);//插入一个顶点booleaninsertEdge(inti,intj,intweight);//插入一条权值为weight的边〈vi,vj〉booleanremoveVertex(intv);//删除序号为v的顶点及其关联的边bo

3、oleanremoveEdge(inti,intj);//删除边〈vi,vj〉intgetFirstNeighbor(intv);//返回顶点v的第一个邻接顶点的序号intgetNextNeighbor(intv,intw);//返回v在w后的下一个邻接顶点的序号}3、存储结构设计【描述物理结构设计，给出基础结构类设计】本实验的存储结构采用的是邻接矩阵表示，图的邻接矩阵是表示图中各顶点之间临街关系的矩阵。逻辑结构类设计如下：packagepictrue;importpicture.SeqList;publicclassAdjMatrixGraph{protectedSeqList<

4、E>vertexlist;protectedint[][]adjmatrix;privatefinalintMAX_WEIGHT=Integer.MAX_VALUE;publicAdjMatrixGraph(intn){this.vertexlist=newSeqList(n);this.adjmatrix=newint[n][n];for(inti=0;i

5、this(vertices.length);for(inti=0;ilist,Edge[]edges){this(list.length());this.vertexlist=list;for(intj=0;j

6、{returnthis.vertexlist.length();}publicEget(inti){returnthis.vertexlist.get(i);}publicbooleaninsertVertex(Evertex){returnthis.vertexlist.add(vertex);}publicbooleaninsertEdge(inti,intj,intweight){if(i>=0&&i=0&&j

7、j]=weight;returntrue;}returnfalse;}publicbooleaninsertEdge(Edgeedge){if(edge!=null)returninsertEdge(edge.start,edge.dest,edge.weight);returnfalse;}publicStringtoString(){Stringstr="顶点集合："+vertexlist.toString()+"";str