“邻接矩阵表示的带权有向图(网)”演示程序

《“邻接矩阵表示的带权有向图(网)”演示程序》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、班级:信息1102姓名：贾孟涛========实习报告十四“邻接矩阵表示的带权有向图（网）”演示程序==========（一）、程序的功能和特点该程序可以建立有向图的带权邻接矩阵，能够对建立的邻接矩阵进行添加顶点，添加边和删除顶点，删除边的操作，并能显示输出邻接矩阵。该程序的特点是采用java面向对象语言，对边，顶点和邻接矩阵用类进行封装。采用链式存储结构。（二）、程序的算法设计算法一：“插入一个顶点”算法：1.【逻辑结构与存储结构设计】    逻辑结构：线性结构。存储结构：顺序存储与链式存储结合。2.【基本

2、操作设计】文字说明：创建新结点，找到结点L位置，在 L后插入新结点。3.【算法设计】文字说明：    （1）.首先判断顶点表是否满。    （2）.若满则插入失败，放回false。    （3）.顶点表若不满，创建新顶点，将新顶点加入顶点表。    （4）.插入顶点成功，返回true。4.【高级语言代码】//插入一个顶点publicintInsertVertex(charvertex){if(IsGraphFull())return-1;//插入失败//顶点表增加一个元素VerticesList[Curren

3、tVertices]=vertex;//邻接矩阵增加一行一列for(intj=0;j<=CurrentVertices;j++){Edge[CurrentEdges][j]=MaxValue;Edge[j][CurrentEdges]=MaxValue;}Edge[CurrentEdges][CurrentEdges]=0;CurrentVertices++;returnCurrentVertices;//插入位置}算法二：“插入一条边”算法：1.【逻辑结构与存储结构设计】    逻辑结构：线性结构。存储结构

4、：链式存储结构。2.【基本操作设计】文字说明：创建新边结点，再将新创建的边结点插入图中。3.【算法设计】文字说明：   （1）.首先判断插入边上的两个顶点编号是否越界。     if(v1<0

5、

6、v1>CurrentVertices-1)     return false;  if(v2<0

7、

8、v2>CurrentVertices-1)     return false;   （2）.如果越界则插入失败，返回false。  （3）.否则创建新边结点   （4）.再将新创建的边结点插入图中    （5).插入成

9、功返回true。4.【高级语言代码】//插入一个边publicbooleanInsertEdge(intv1,intv2,doubleweight){if(v1<0

10、

11、v1>CurrentVertices-1)returnfalse;//出错if(v2<0

12、

13、v2>CurrentVertices-1)returnfalse;Edge[v1][v2]=weight;//网,有向边returntrue;}（三）、程序中类的设计“Graph”类：1.【逻辑结构与存储结构】逻辑结构：网状结构。存储结构：顺序存储与链式

14、存储结合。2.【主要成员变量说明】staticintMaxEdges=50;staticintMaxVertices=10;staticdoubleMaxValue=9999.9;//无穷大//存放顶点的数组privatecharVerticesList[]=newchar[MaxVertices];//邻接矩阵（存放两个顶点权值）privatedoubleEdge[][]=newdouble[MaxVertices][MaxVertices];privateintCurrentEdges;//现有边数pri

15、vateintCurrentVertices;//现有顶点数//构造函数：建立空的邻接矩阵2.【主要成员方法说明】publicGraph()：为定义的构造函数，建立空的邻接矩阵。publicintFindVertex(charvertex)：查找指定的顶点的序号publicbooleanIsGraphEmpty()：判断图是否为空。    public boolean IsGraphFull ( )：判断图是否为满。 public char GetValue ( int i )：按顶点序号返回顶点数据。   

16、 public int NumberOfVertices ( )：返回图的顶点数。    public int NumberOfEdges ( )：返回图的边数。 publicdoubleGetWeight(intv1,intv2)：取得一条边的权值。publicintGetFirstNeighbor(intv)：取得第一个邻接点的序号public int InsertVertex ( char v