数据结构----图及其临接矩阵的实现

1.什么是图?

图(Graph)是由顶点的有穷非空集合和顶点之间边的集合组成的,通常表示为:G(V,E),其中,G表示一个图,V是图G中顶点的集合,E是图G中边的集合。

若顶点Vi到Vj之间的边没有方向,则称这条边为无向边,反之为有向边。
和边有关数字叫做权重(weight),举个例子:我家到公司8公里,那么我家到公司这就算一个边,8公里就是权重。

2.图的邻接矩阵

图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点的信息,一个二维数组存储图中的边或者弧的信息。
图2

上图就是含有v0,v1,v2,v3四格顶点,5条边的有向图。
那么该图的顶点数组是: [v0, v1, v2, v3]
边数组:
v0 -> v1
v0 -> v3
v0 -> v2
v1 -> v2
v3 -> v2

一共有五条有向边,假设每条边的权重是1,如果两点之间不连通,那么权重是Infinity.
那么,用二维数组可以这样表示:

我们可以看v0这个点, v0 -> v0 ,权重是0, 因为v0到v1,v2,v3都有有向边链接,所以权重都是1,而v2这个点,没有到其它任何点的有向边,所以都是无穷大。

3.代码层面的实现

图具有的属性和方法

属性:
1.顶点数:需要用户输入
2.边数: 需要用户输入
3.顶点表:vertexTable :Array
4.存储图信息的二维数据: matrix: Array

方法:
1.创建顶点表:createVertexTable, 需要用户输入顶点的名字,或者其它信息
2.初始化图的信息:initVertexWeight,默认两个不同顶点之间距离是无穷大Infinity,到自身是0
3.读入边的信息:initArcWeight,把对应边的权重给添加上去

详细代码及相应注释如下

4.结语

本人比较懒,最近也在追s8,所以一直没去发这个,希望ig在s8夺冠!

评论 ( 0 )
最新评论
暂无评论

赶紧努力消灭 0 回复