-
实习报告——
“邻接矩阵表示的带权有向图”
演示程序
（一）、程序的功能和特点
主要实
现的功能：
1.
使用邻接矩阵表示带权有向图；
2.
查找指定顶点序号；
3.
判断图是否为空；
4.
判断图是否满；
5.
取得
顶点数、边数、一条边的权值；
6.
插入一个顶点、边；
7.
删除一个顶点、边；
（二）、程序的算法设计
“邻接矩阵的表示”算法：
1.
【逻辑结构与存储结构设计】
逻辑结构：非线性结构——网状结构
B
A
F
C
E
D
存储结构
:
内存中连续的存储结构，邻接矩
阵
2.
【基本操作设计】
按指定输入，生成图并打印该图
删除一个顶点并打印
删除一条边并打印
3.
【算法设计】
插入一个顶点的算法：
首先判断该图是否已满，若已满：插入失败；
否则进行插入：
1.
顶点表增加一个元素
2.
邻接矩阵增加一行一列
删除一个顶点的算法：
判断要删除顶点的存在性，若不存在：出错；
否则：
1.
修改顶点表，
即在顶点数组
中删除
该点；
2.
修改邻接矩阵，
即需要统计与该顶
点相关联的边，
并将这些边也删除
4.
【高级语言代码】
public
class
Graph {
static
int
MaxEdges
=50;
static
int
MaxVertices
=10;
static
int
MaxValue
=9999;
//
无穷大
//
存放顶点的数组
private
char
VerticesList
[]=
new
char
[
MaxVertices
];
//
邻接矩阵（存放两个顶点的权值）
private
int
Edge
[][]=
new
int
[
MaxVertices
][
MaxVertices
];
private
int
CurrentEdges<
/p>
;
//
现有边数
private
int
CurrentVertic
es
;
//
现有顶点数
//
构造函数：建立空的邻接矩阵
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
GetWeigh(
int
v1,
int
v2){
if
(v1<0||v1>
CurrentVertices
-1)
return
-1;
//
用
-1
表示出错
if
(v
2<0||v2>
CurrentVertices
-1)
return
-1;
//
用
-1
表示出错
return
Edge
[v1][v2];
}
//
取得第一个邻接点的序号
public
int
GetFirstNeighbor(
int
v){
if
(v
<0||v>
CurrentVertices
-1)
return
-1;
//
邻接矩阵的行号和列号是两个邻
接点的序号
for
(
int
col=0;c
ol<
CurrentVertices
;col++)
if<
/p>
(
Edge
[v][col]>0&&<
/p>
Edge
[v][col]<
MaxVa
lue
)
return
col;
return
-1;
}
//
插入一个顶点
public
int
InsertVertex(
char
vertex){
if
(IsGraphFull())
return
-1;
//
插入失败
//
顶点表增加一个元素
VerticesList
[
CurrentVertices
]=ve
rtex;
//
邻接矩阵增加一行一列
for
(
int
j=0;j<=
CurrentVertices
;j++){
Edg
e
[
CurrentEdges
][j
]=
MaxValue
;
Edge
[j][
CurrentEdges
]=
MaxValue
;
}
Ed
ge
[
CurrentEdges
][
CurrentEdges
]=0;
CurrentVertices
++;
return
CurrentVer
tices
;
//
插入位置
}
//
插入一个边
public
boolean
InsertEdge(
int
v1,
int
v2,
int
weight){
if
(v1<0||v1>
CurrentVertices
-1)
return
false
;
//
出错
if
(v
2<0||v2>
CurrentVertices
-1)
return
false
;
//
出错
Edge
[v1][v2]=weight;
return
true
;
}
//
删除一个顶点
public
boolean
RemoveVertex(
int
v){
if
(v
<0||v>
CurrentVertices
-1)
return
false
;
//
出错
//
修改顶点表
for
(
int
i=v+1;i<
CurrentVertices
;i++)
Ver
ticesList
[i-1]=
VerticesList<
/p>
[i];
//
修改邻接矩阵
int
k=0;
//
累计将要删去的边数
for
(
int
i=0;i<
CurrentVertices
;i++)
if<
/p>
(
Edge
[v][i]>0&&
Edge
[v][i]<
MaxValue<
/p>
)
k++;
//
第
v
行
for
(
i
nt
i=0;i<
CurrentVertices
;i++)
if<
/p>
(
Edge
[i][v]>0&&
Edge
[i][v]<
MaxValue<
/p>
)
k++;
//
第
v
列
//
覆盖第
v
行
int
j;
for
(
i
nt
i=v+1;i<
CurrentVertices
;i++)
for
(j=0;j<
CurrentVertices
;j++)
Edge
[i-1][j]=
Edge
[i][j];
//
覆盖第
v
列
for
(
j=v+1;j<
CurrentVertices
;j++)
for
(
int
i=0;i<
CurrentVertices
;i++)
Edge
[i][j-1]=
Edge
[i][j];
CurrentVertices
--;
//
修改顶点数
CurrentEdges
-=k;
//
修改边数
return
true
;
}
//
删除一个边
public
boolean
RemoveEdge(
int
v1,
int
v2){
if
(v1<0||v1>
CurrentVertices
-1)
return
false
;
//
出错
if
(v
2<0||v2>
CurrentVertices
-1)
return
false
;
//
出错
if
(v1==v2)
return
false
;
Edge
[v1][v2]=
MaxValue
;
return
true
;
}
（三）
、程序中类的设计
“
Graph
”类
：
1.
【主要成员变量说明】
static
int
MaxEdges
=50;
static
int
MaxVertices
=10;
static
int
MaxValue
=9999;
//
无穷大
//
存放顶点的数组
private
char
VerticesList
[]=
new
char
[
MaxVertices
];
private
int
CurrentEdges<
/p>
;
//
现有边数
private
int
CurrentVertic
es
;
//
现有顶点数
//
邻接矩阵（存放两个顶点的权值）
private
int
Edge
[][]=
new
int
[
MaxVertices
][
MaxVertices
];
2.
【主要成员方法说明】
//
查找指定的顶点序号
public
int
FindVertex(
char
vertex){
}
//
判断图是否为空
public
boolean
IsGraphEmpty(){
}
//
判断图是否满
public
boolean
IsGraphFull(){
}
//
取得顶点数
public
int
NumberOfVertices(){
}
//
取得边数
public
int
NumberOfEdges(){
}
//
按序号取得顶点值
public
char
GetValue(
int
i){
}
//
取得一条边的权值
public
int
GetWeigh(
int
v1,
int
v2){
}
//
取得第一个邻接点的序号
public
int
GetFirstNeighbor(
int
v){
}
//
插入一个顶点
public
int
InsertVertex(
char
vertex){
-
-
-
-
-
-
-
-
-
上一篇：高中数学词汇英文
下一篇：grasshopper词汇