图的存储结构——邻接矩阵与边集数组

图的存储结构——邻接矩阵与边集数组

专栏导读及目录https://blog.csdn.net/createprogram/article/details/86741044

用计算机处理图论问题,首先要用某种表达方式将图存放在计算机中,这里介绍两种最常用的存储结构,即邻接矩阵和边集数组。

邻接矩阵

(1)矩阵定义

用邻接矩阵表表示顶点之间相邻关系的矩阵。在图的邻接矩阵表示法中:

  • 用邻接矩阵表示顶点之间的相邻关系。
  • 用一个顺序表来存储顶点信息。

设图G的阶为n,则用A(G)来表示具有如下性质的n阶方阵:

A[i][j]=1,(Vi,Vj)或< Vi,Vj >是E(G)中的边。

A[i][j]=0 ,(Vi,Vj)或< Vi,Vj >不是E(G)中的边。

则a,b两图的邻接矩阵可以表示为:

Aa=|0 1 1 1|          Ab=|0 1 1|

      |1 0 1 1|                 |0 0 1|

      |1 1 0 0|                 |0 1 0|

      |1 1 0 0|

 

 

在无向图中,邻接矩阵是对称的。而在有向图中,邻接矩阵通常是不对称的。

由于邻接矩阵表示了两个顶点之间的连接情况,因此,还可以用它来表示带权图。此时邻接矩阵定义为:

A[i][j]=Wij,(Vi,Vj)或< Vi,Vj >是E(G)中的边。

A[i][j]=0 或无穷大,(Vi,Vj)或< Vi,Vj >不是E(G)中的边。

如图:

A1=|0  5  8  0  3 |     或     A2=|MAX   5      8    MAX     3|

      |5  0  2  0  6 |                    |5      MAX    2    MAX    6|

      |8  2  0 10 4 |                    |8         2   MAX    10      4|

      |0  0 10 0 11|                    |MAX  MAX 10  MAX    11|

      |3  6  4 11 0 |                    |3          6      4      11 MAX|

(2)需要特别说明的是:

  • 在简单应用中,可直接用二维数组存放图的邻接矩阵。
  • 无向图的邻接矩阵是对称矩阵,对数据规模特大的邻接矩阵可压缩存储。
  • 邻接矩阵表示法的空间复杂度S(n)=O(n^2)

 

 

边集数组

(1)边集数组定义

边集数组是利用一维数组存储图中所有边的一种图的表示方法。该数组中所含元边的个数要等于图中的边的条数,每个元素用来存储一条边的起点、终点和权(若含有权的话)。每个元素包含三个属性,因此建议先定义为结构体,再定义结构体数组。对于无向图,可选定变得任一端为起点或终点。各边在数组中的次序可以任意安排,也可以根据具体要求而定。

struct bian{
    int qidian;
    int zhongdian;
    int bianchang;
}bian[100];

(2)边集数组的特征

在边集数组中查找一条边或一个顶点的都需要扫描整个数组,所以其时间复杂度为O(e)。边集数组适合那些对边依次进行处理的运算,不适合对顶点的运算和对任一条边的运算。边集数组的表示通常包括一个边集数组和一个顶点 数组,所以其空间复杂度为O(n+e)。从空间复杂度上讲,边集数组也适合表示稀疏图。

评论
添加红包

请填写红包祝福语或标题

红包个数最小为10个

红包金额最低5元

当前余额3.43前往充值 >
需支付:10.00
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明:

1.余额是钱包充值的虚拟货币,按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载,可以购买VIP、付费专栏及课程。

余额充值