欢迎来到军工软件开发人才培养基地——学到牛牛

数据结构之图的存储方式

时间:2024-05-06 07:01:10 来源:学到牛牛

 

图的基本概念

图是由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为: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;  //记录图的种类

 

};