数据结构之图的存储方式
图的基本概念
图是由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为:G(V,E),其中,G表示一个图,V是图G中顶点的集合,E是图G中边的集合。
在图中需要注意的是:
1.线性表中我们把数据元素称作元素,树中将数据元素称作结点,在图中数据元素我们称之为顶点
2.线性表可以没有元素,称为空表,树中可以没有节点,称为空树,但在图中不能没有顶点(有穷非空性)。
3.线性表中的各元素是线性关系,树中的各元素是层次关系,而图中各顶点的关系是用边来表示(边集可以为空)。
图的种类
1.无向图
如果图中任意两个顶点之间的边都是无向边(没有方向的边),则称该图为无向图。
2.有向图
如果图中任意两个顶点之间的边都是有向边(有方向的边),则称该图为有向图。
3.完全图
1)无向完全图:
在无向图中,任意两个顶点之间都存在边,该图就称为无向完全图。
2)有向完全图
在有向图中,如果任意两个顶点之间都存在方向互为相反的两条弧,则称该图为有向完全图。
图的存储方式
图的存储结构除了要存储图中的各个顶点本身的信息之外,还要存储顶点与顶点之间的关系,因此,图的结构也比较复杂。常用的图的存储结构有邻接矩阵和邻接表等。
邻接矩阵法
用一个一维数组存储图中的顶点信息,用一个二维数组存储图中边的信息,存储顶点之间邻接关系的二维数组称为邻接数组。
结点数为n的图G=(V,E)的邻接矩阵A是n*n,将G的顶点编号为,若(v1,v2...vn)∈E,则A[i][j]=1,否则A[i][j] = 0;
对于带权图来说,若顶点Vi和Vj之间有边相连,则邻接矩阵中对应项存放着改变对应的权值,若顶点Vi和Vj不相连,则用∞ 来代表这两个顶点之间不存在边。
有向图和无向图对应的邻接矩阵举例如下:
图的邻接矩阵存储结构定义如下
#define MAX 50 //顶点最大值为50
typedef char VertexType; //顶点的数据类型
typedef int EdgeType; //带权图中边上权值的数据类型
struct mmap
{
VertexType vex[MAX]; //顶点表
EdgeType Edge[MAX][MAX]; //邻接矩阵,边表
int vexnum,arcnum; //图的当前顶点数和弧数
};
邻接表法
邻接表既适用于存储无向图,也适用于存储有向图。
在讲解邻接表之前,先了解一下“邻接点”的概念,在图中,如果两个点相互连通,即通过其中一个顶点,可直接找到另一个顶点,则称他们互为邻接点。
邻接图是指图中顶点之间有边或弧的存在。
邻接表存储图的实现方式是,给图中的各个顶点单独建立一个链表,用节点存储该顶点,用其他节点存储各自的邻接点。
为了方便管理这些链表,通常会将所有链表的头节点存储到数组中,也正因为各个链表的头节点存储的是各个顶点,因此各链表在存储邻接点数据时,仅需存储该邻接点在数组中的下标即可。
例如,存储在图表1所示的有向图,其对应的邻接表如图表2所示。
图表 1
图表 2
拿顶点V1来说,与其相关的邻接点分别为V2和V3,因此存储V1的链表中存储的是V2和V3在数组中的下标1和2。
从图1中可以看出,存储各顶点的节点结构部分分为两部分,数据域和指针域。数据域用于存储各顶点数据信息,指针域用于链接下一节点,如图表3所示
图表 3
图表1中的链表结构转化为对应的C语言代码如下:
#define MAX_NUM 30 //最大顶点个数
struct V_node
{
int data; //顶点的数据域
int *next; //指向邻接点的指针
};
struct V_node list[MAX_NUM];// 存储各链表头结点的数组
struct ALGraph
{
struct V_node vertices[MAX_NUM]; //图中顶点的数组
int vexnum,arcnum; // 记录图中顶点数和边或弧数
int kind; //记录图的种类
};
![](https://www.xuedaoniu.com/wp-content/themes/xuedaoniu/assets//img/xuexi/qrs_rgzn2.jpg)