数据结构之图的存储方式
图的基本概念
图是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：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; //记录图的种类
};
