-
班级
:
信息
1102
姓名：贾孟涛
===
=====
实习报告十四
“邻接矩阵表示的带权有向图
（网）
”
演示程序
==========
（一）、程序的功能和特点
该程序可以建立有向图的带权邻接矩阵，能够对建立的邻接矩阵进行添加
顶点，添加边和删除顶点，删除边的操作，并能显示输出邻接矩阵。该程序的特
点是
采用
java
面向对象语言，对边，顶点和邻接矩阵用类进行封
装。采用链式
存储结构。
（二）
、程序的算法设计
算法一：
“插入一个顶点”算法：
1.
【逻辑结构与存储结构设计】
逻辑结构：线性结构。
存储结构：顺序存储与链式存储结合。
2.
【基本操作设计】
文字说明：
创建新结点，找到结点
L
位置，在
L
后插入新结点。
3.
【算法设计】
文字说明：
（
1
）
.
首先判断顶点表是否满。
（
2
）
.
若
满则插入失败，放回
false
。
（
3
）
.
顶点表若不满，创建新顶点，将新顶点加入顶点表。
（
4
）
.
插入顶点成功，返回
true
。
4.
【高级语言代码】
//
插入一个顶点
public int InsertVertex ( char
vertex ){
if(IsGraphFull()) return -1;
//
插入失败
//
顶点表增加一个元素
VerticesList[CurrentVertices]=vertex;
//
邻接矩阵增加一行一列
for ( int j =
0;j <=CurrentVertices;j++ ) {
Edge[CurrentEdges][j]=MaxValue;
Edge[j][CurrentEdges]=MaxValue;
}
Edge[CurrentEdges][CurrentEdges]=0;
CurrentVertices++;
return CurrentVertices;
//
插入位置
}
算法二：
“插入一条边”算法：
1.
【逻辑结构与存储结构设计】
逻辑结构：线性结构。
存储结构：链式存储结构。
3.
【基本操作设计】
文字说明：
创建新边结点，再将新创建的边结点插入图中。
4.
【算法设计】
文字说明：
< br>（
1
）
.
首先判断插入边上的两个顶点编号是否越界。
if (v1 < 0 || v1 > CurrentVertices - 1)
return false;
if (v2 < 0 || v2 >
CurrentVertices - 1) return false;
（
2
）<
/p>
.
如果越界则插入失败，返回
false
。
（
3
）
.
否则
创建新边结点
（
4
）
.
再将新创建的边结点
插入图中
（
5) .
插入成功返回
true
。
4.
【高级语言代码】
//
插入一个边
public boolean InsertEdge( int v1,
int v2, double weight){
if (v1 < 0 || v1 > CurrentVertices - 1)
return false;
//
出错
if (v2 < 0 || v2 > CurrentVertices - 1)
return false;
Edge[v1][v2]=weight; //
网
,
有向边
return true;
}
（三）
、程序中类的设计
“
Graph
”类
：
1.
【逻辑结构与存储结构】
逻辑结构：网状结构。
存储结构：顺序存储与链式存储结合。
2.
【主要成员变量说明】
static int MaxEdges =
50;
static int
MaxVertices = 10;
static
double MaxValue=9999.9;
//
无穷大
//
存放顶点的数组
private char VerticesList[]=new
char[MaxVertices];
//
邻接矩阵（存放两个顶点权值）
private double Edge[][]=new
double[MaxVertices][MaxVertices];
private int CurrentEdges;
//
现有边数
private int CurrentVertices;
//
现有顶点数
//
构造函数：建立空的邻接矩阵
3.
【主要成员方法说明】
public Graph (
)
：为定义的构造函数，建立空的邻接矩阵。
public int FindVertex (char
vertex)
：查找指定的顶点的序号
public boolean IsGraphEmpty (
)
：判断图是否为空。
public boolean IsGraphFull (
)
：判断图是否为满。
public char GetValue ( int i
)
：按顶点序号返回顶点数据。
public int NumberOfVertices (
)
：返回图的顶点数。
public int NumberOfEdges (
)
：返回图的边数。
public
double GetWeight ( int v1, int v2
)
：取得一条边的权值。
public int GetFirstNeighbor ( int v
)
：取得第一个邻接点的序号
public int InsertVertex ( char vertex
)
：插入一个顶点。
public
boolean RemoveVertex ( int v
)
：删除一个顶点。
public
boolean InsertEdge ( int v1,int v2,double weight )
：
插
入
一
条
边。
public boolean RemoveEdge ( int v1,
int v2 )
：删除一条边。
public void
display()
：显示邻接矩阵。
4.
【高级语言代码】
//
“邻接矩阵”类
class Graph {
static int MaxEdges = 50;
static int MaxVertices =
10;
static double
MaxValue=9999.9; //
无穷大
//
存放顶点的数组
private char VerticesList[]=new
char[MaxVertices];
//
邻接矩阵（存放两个顶点权值）
private double Edge[][]=new
double[MaxVertices][MaxVertices];
private int CurrentEdges;
//
现有边数
private int CurrentVertices;
//
现有顶点数
//
构造函数：建立空的邻接矩阵
public Graph ( ){
for ( int i = 0; i < MaxVertices; i++ )
for ( int j = 0; j < MaxVertices; j++ )
if(i==j)
Edge[i][j] = 0;
//
对角线
else
//
非对角线上无穷大
Edge[i][j] =MaxValue;
CurrentEdges =
0; //
现有边数
CurrentVertices = 0;
//
现有顶点数
}
//
查找指定的顶点的序号
public int FindVertex (char
vertex){
//
在顶点数组里面查找
for(int
i=0;i
if(VerticesList[i]==vertex)
return i; //
返回下标
return -1;
//
没有找到
}
//
图空否？
public boolean IsGraphEmpty ( ){
return
CurrentVertices==0;
}
//
图满否？
public boolean IsGraphFull ( ){
return
CurrentVertices==MaxVertices ||
CurrentEdges==MaxEdges;
}
//
取得顶点数
public int NumberOfVertices ( ){
return CurrentVertices;
}
//
取得边数
public int NumberOfEdges ( ){
return CurrentEdges;
}
//
按序号取得顶点值
public char GetValue ( int i ){
return i >= 0 && i <=
CurrentVertices-1
? VerticesList[i] : ' ';
}
//
取得一条边的权值
public double GetWeight (
int v1, int v2 ){
if (v1 < 0 || v1 > CurrentVertices - 1)
return -1.0; //
用
-
1
表示出错
if (v2 < 0 || v2 >
CurrentVertices - 1)
return -1.0;
return Edge[v1][v2];
}
//
取得第一个邻接点的序号
public int GetFirstNeighbor ( int v
){
if (v< 0 || v >
CurrentVertices - 1)
-
-
-
-
-
-
-
-
-
上一篇：grasshopper词汇
下一篇：小学英语阅读100篇翻译(67-100)钱丽英