（新编）图的表示和操作(邻接矩阵)

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

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〉booleanremo

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

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

5、=(i==j)?0:MAX_WEIGHT;}publicAdjMatrixGraph(E[]vertices,Edge[]edges){this(vertices.length);for(inti=0;ilist,Edge[]edges){this(list.length());this.verte

6、xlist=list;for(intj=0;j

7、if(i>=0&&i=0&&j

8、r="顶点集合："+vertexlist.toString()+"";str