前言

数据结构我也学了好几遍了，可能人老了记忆里不行

前一段回想图的存储结构，脑子一团浆糊，这次整理出来供大家讨论

在开始之前，我们先给出本篇的示例图，无向图我们就假设箭头不存在就好了

全篇用这一个图，因为我懒！

邻接矩阵

邻接矩阵是用一个二维数组来存储一个图，我们先来说无向图

我们现在假设实例图没有箭头也没有权值

对称矩阵

我们先来说明一下，我们列标表示起点行标表示终点。

然后连通的地方我们标识为1，非连通的地方我这里就不做标识。

比如A到B有一条边，这时A,B对应的地方就填1

在无向图中，由于A到B，B自然也与A连通，所以自然就形成了对称矩阵

有了无向图的邻接矩阵，有向图和权值自然非常容易表示，之后0表示不连通

有向图

有向图加权值

我们只需要把连通状态改为权值，很轻松的就可以表示连通状态。

下面我们给出结构和初始化代码

代码

邻接表

如图所示我们先用一个数组保存图上的结点

随后我们用链表的方式把这个图的每一条边以链表的形式保存

如果我们要增加权值，在结点结构中增加一格保存权值就可以了。

这里就不说无向图了 如果是无向图只不过是边的结点多了一倍而已

下面给出结构和初始化代码

结构

初始化

接下来我们介绍一些特殊概念

逆邻接表

在有向图中我们有出度和入度的概念，出度就是有几条边起点是这个结点，入度就是有几条边终点是指向这里

如果我们想快速知道入度的边就可以在建立一个逆邻接表。我们简单举几个结点的例子。

D和E的部分忽略

十字链表

十字链表其实就是把邻接表和逆邻接表结构合并

我们需要在结点数组和边结点上各增加一个单元保存逆链表就可以了

逆链表判断规则，我们看链接表图：比如结点B（索引1），新增结点指向结点A后面的第二个边，这个边的nodeIdx正巧是结点B的索引值1。

也就是新增一个结点组成的链表是所有nodeIdx的值等于自身索引的链表。

必要情况下我们边结点需要再多添加一个单元，用来表示起始结点，注意我们之前边结点里标注的一直是终点结点。

邻接多重表

邻接多重表是针对无向图的。

类似于十字链表，我们需要给边结点多添加一到两个单元。

区别在于邻接多重表每个边只创建一个结点，我们通过直接指向其它结点来达到目的。

这样的好处有两点1、节约空间；2、便于删除操作。

边集数组

注意这是一种全新的表示方法，没什么特别的。

就是单纯的把边集保存在一个数组中，这种方式多用在一些算法应用上。

本篇就介绍到这里，后续我们还会继续讨论有关图的知识。