大家好，我是“Stephen·谢”，在图之前，已经有了线性表和树的数据结构，但是为什么还需要图结构呢？我们知道，线性表仅仅局限于一个直接前驱和一个直接后继的关系，而树虽说可以有多个后继（子节点），但还是仅有一个前驱（父节点），那么在需要处理多对多的关系时就会出现多个前驱和多个后继，这时，图结构便产生了。
图的概念：
无向图
有向图
网
上面就是图的结构，在线性表中我们把数据元素叫做“元素”，在树中叫做“节点”，在图中我们叫它为“顶点”。两个顶点间的连线叫做“边”，有方向的叫做“有向边”，无方向的叫做“无向边”，相应的图称为“有向图”和“无向图”。边上的数字代表边的“权值”，当图上有权值时图也叫做“网”。
以上便是图的简单概念。图的存储结构相比线性表与树而言，更加复杂。图不可能用简单的顺序存储结构来表示，这是一个很困难的问题。图一般有三种存储结构：邻接矩阵、邻接表和边集数组。
邻接矩阵：
邻接矩阵是表示顶点之间相邻关系的矩阵，下面展示的分别是无向图、有向图和网的邻接数组。（下面的边数组就是指的邻接矩阵，所谓顶点的“度”(degree),就是指和该顶点相关联的边数，在有向图中，度又分为“入度”和“出度”，入度 (in-degree) 指终止于某顶点的边的数目，出度 (out-degree) 指起始于某顶点的边的数目）
无向图的邻接矩阵
有向图的邻接矩阵
网的邻接矩阵
注意：在有向图和无向图中，1表示有边，0表示无边。而在网中，有边的写权值，无边的写无穷大，为什么无边的不写0呢？因为如果无边的写0，那么有的边上权值可能为0，会和无边的0产生歧义。
我们从上面的邻接矩阵可以看出以下几个特点：
1、无向图的邻接矩阵一定是对称的，而有向图的邻接矩阵不一定对称。用邻接矩阵来表示一个具有n个顶点的图时需要n²个存储量来存储邻接矩阵。
2、对于无向图，邻接矩阵的第i行非零元素的个数正好是第i个顶点的度。
3、对于有向图，邻接矩阵的第i行非零元素的个数正好是第i个顶点的出度（或入度)。
4、邻接矩阵的特点在于很容易确定图中任意两个顶点之间是否有边相连，但是必须按行、列对每个元素进行检测才能够确定图中有多少条边。
邻接表：
邻接表是图的一种顺序存储和链式存储相结合的存储方式，如下图，对于图中每个顶点Vi，将邻接于Vi的所有顶点Vj链成一个单链表，这个单链表就称为顶点Vi的邻接表。
邻接表是由两部分组成，一部分是头结点：顶点域和指针域，另一部分是表节点：邻接顶点域和指针域。
无向图的邻接表，可以直接读取各顶点的度
有向图的邻接表，可以读取各顶点“出度”
我们观察邻接表，对于无向图，第i个顶点Vi的度就是i号单链表中节点个数，而在有向图中，i号单链表中节点个数只是顶点Vi的“出度”。
为了便于确定有向图节点的“入度”，可以为有向图建立逆邻接表。
有向图的逆邻接表，可以读取各顶点“入度”
一个图的邻接矩阵是唯一的，但其邻接表不是唯一的，因为在邻接表的每个单链表中，各节点的顺序可以使任意的，通常情况下系统都是采用“头插法”来安排链表节点。
边集数组：
边集数组一般在网结构中使用，它适用于一些以边为主的操作。用边集数组表示网时，列出每条边所依附的两个顶点及边上的权，即每个数组元素代表一条边的所有信息。
边集数组由两个一维数组构成，一个存储顶点信息， 一个存储边的信息，这个边数组每个数据元素由一条边的起点下标（begin）、终点下标（end）、和权（weight）组成。如下图：
边集数组
边集数组关注的是边的集合，在边集数组中要查找一个顶点的度需要扫描整个边数组，效率并不高。因此它更适合对边依次进行处理的操作，而不适合对顶点相关的操作。
总结：图的存储结构一般以上述三种最为普遍：邻接矩阵、邻接表和边集数组，其中，邻接矩阵和边集数组相对简单，邻接表重点理解其存储结构：头节点和表节点，网上可以找到很多实现的代码大家可以拷贝下来运行一下体会体会，其中的核心代码部分采用的是“头插法”，但这个头插法有点诡异，它不是从左到右，而是从右到左，这是一个值得注意的地方。此篇主要是针对图结构的概念和存储进行探讨，后面的文章中将进一步探讨图结构的插入和删除原理。
网友评论