5.2 图的存储及基本操作

图的存储必须要完整、准确地反映顶点集和边集的信息。根据不同图的结构和算法,可以用不同的存储方式,但不同的存储方式将对程序的效率产生很大的影响,因此,所选的存储结构应适合于欲求解的问题。无论是有向图还是无向图,主要的存储方式都有两种:邻接矩阵和邻接表。前者属于图的顺序存储结构,后者属于图的链接存储结构。

5.2.1邻接矩阵表。

所谓邻接矩阵存储,就是用一个一维数组存储图中顶点的信息,用一个二维数组存储图中边的信息(即各顶点之间的邻接关系),存储顶点之间邻接关系的二维数组称为邻接矩阵。结点树为n的图G=(V,E)的邻接矩阵A是n*n的。将G的顶点编号为v1,V2,……,Vn。若(vi,vj)属于E,则A[i][j]=1,否则A[i][j]=0。对于带权图而言,若顶点vi和vj之间有边相连,则邻接矩阵中对应项存放着该边对应的权值,若顶点vi和vj不相连,则用无穷来表示这两个顶点之间不存在边。图的邻接矩阵存储结构定义如下:

#define MaxVertexNum 100//顶点数目的最大值
typedef char VertexType;//顶点的数据类型
typedef int EdgeType;//带权图中边上权值的数据类型
typedef struct{ 
   VertextType Vex[MaxVertexNum];//顶点表 
   EdgeType Edge[MaxVertexNum][MaxVertexNum];//临界矩阵,边表 
   int vexnum,arcnum;//图的当前顶点数和弧数
}MGragh;

注意:

①在简单应用中,可以直接用二维数组作为图的邻接矩阵(顶点信息等均可省略)

②在邻接矩阵中的元素仅表示相应的边是否存在时,EdgeType可定义为值为0和1的枚举类型。

③无向图的邻接矩阵是对称矩阵,对规模特大的邻接矩阵可采用压缩存储。

④邻接矩阵表示法的空间复杂的为O(n^2),其中n为图的定点数|V|。

图的邻接矩阵存储表示法具有以下特点:

①无向图的邻接矩阵一定是 一个对称矩阵(并且唯一)。因此,在实际存储邻接矩阵时只需存储上(或下)三角矩阵的元素即可。

②对于无向图,邻接矩阵的第i行(或第i列)非零元素(或非无穷元素)的个数正好是第i个顶点的度TD(vi)。

③对于有向图,邻接矩阵的第i行(或第i列)非零元素(或非无穷元素)的个数正好是第i个顶点的出度OD(vi)(或入度ID(vi))。

④用邻接矩阵存储图,很容易确定图中任意两个顶点时间是否有边相连。但是,要确定图中有多少边,则必须按行、按列对每个元素进行检测,所花费的时间代价很大。这是用邻接矩阵存储图的局限性。

⑤稠密图适合使用邻接矩阵的存储表示。

⑥设图G的邻接矩阵为A,A^n的元素A^n[i][j]等于由顶点i到顶点j的长度为n的路径的数目。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

二分图相关定理

定义:若选择一个点说明选择与它相连的所有边,最小顶点覆盖就是选择最少的点来覆盖所有的边。

1193
来自专栏weixuqin 的专栏

数据结构学习笔记(图)

30410
来自专栏武培轩的专栏

剑指Offer-跳台阶

package Recursion; /** * 一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。 */ pub...

2694
来自专栏数据结构与算法

4768 跳石头

4768 跳石头 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 一年一度的“...

27810
来自专栏WD学习记录

Python数据结构与算法笔记(5)

邻接矩阵优点是简单,对于小图,很容易看到哪些节点连接到其他节点。但是大多数单元格是空的,即稀疏。

1313
来自专栏小樱的经验随笔

邻接矩阵存储有向图(详解)

邻接矩阵存储有向图 【输入描述】   输入文件包含多组测试数据,每组测试数据描述了一个无权有向图。每组测试数据第一行为两个正整数n和m,1<=n<=100,1<...

2959
来自专栏数据结构与算法

洛谷P2678 跳石头

题目背景 一年一度的“跳石头”比赛又要开始了! 题目描述 这项比赛将在一条笔直的河道中进行,河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终...

3435
来自专栏个人分享

邻接矩阵学习

邻接矩阵:是表示顶点之间相邻关系的矩阵。因此,用一个一维数组存放图中所有顶点数据;用一个二维数组存放顶点间的关系(边或弧)的数据,这个二维数组称为邻接矩阵。邻接...

1171
来自专栏猿人谷

斐波那契额数列及青蛙跳台阶问题

题目:写一个函数,输入n,求斐波那契(Fibonacci)数列的第n项。  斐波那契(Fibonacci)数列定义如下: ? 效率很低的解法:...

2428
来自专栏恰童鞋骚年

数据结构基础温故-5.图(中):最小生成树算法

图的“多对多”特性使得图在结构设计和算法实现上较为困难,这时就需要根据具体应用将图转换为不同的树来简化问题的求解。

1532

扫码关注云+社区

领取腾讯云代金券