赞
踩
般存储图的方式有两种:一是用邻接矩阵表示,二是用邻接链表。
所谓用邻接矩阵,是用一个二维数组存储,边使用矩阵来构建模型,这使得每一个顶点和其它顶点之间都有边的有无 的 表示的机会。若有边,则他们交点 为1 ,否则为0。当然,如果是一副边有权值的图,交点存储的是他们边的权值。
1、首先收一下无向图的存储:
无向图的边的矩阵一定是一个对称矩阵,因为无向图只关心边是否存在,而不关心方向,V0和V1有边,那么V1和V0也有边。
因为这里不研究有圈图,所以主对角线都是0,输入V0和V1边的关系后,就不必输入V1和V0的关系了。
图解如下:
使用邻接矩阵呢存储时,有向图和无向图的区别在与 边和弧矩阵的差别。因为弧是有方向的,所以我们 以对角线为界,将矩阵划分为2个区域:
左下区域表示出弧标记区域,坐上区域代表入弧标记区域
如 若代表弧的矩阵为arcArr
arcArr[V2][V3] 为1,且在出弧标记区域,则说明 V3<------V2
arcArr[V3][V2] 为0,且在入弧标记区域,则说明 V2---\--->V3
无向网的边是有权值的,这个值可以是任何一个合法的值,什么样的值是合法的呢?这需要根据图的具体用途来定。所以,我们不能用简单的0,1来代表边。
如果2个顶点无关联,他们也不能用0表示,因为0也可能是一个合法的wieght值。可有类比一下:如何地球上2个地方之间不可互通,那么他们之间的车程费是不是无穷大呢?
所以,我们来要根据图权值类型定义一个相应类型的最大值,来代表2个顶点之间不关联。
同样用一个例子。
V0 V1之间的权值为12
V0 V2之间的权值为1
V0 V3之间的权值为5
V2 V3之间的权值为7
代码实现如下:
有向网的实现与无向网思路一致,就不重复累赘了,直接上代码吧。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。