图的存储结构——邻接矩阵与边集数组
专栏导读及目录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)。从空间复杂度上讲,边集数组也适合表示稀疏图。