图(Graph)
一、图的定义和术语
1. 图的主要类型
- 有向图
- 无向图
- 有向网
- 无向网
二、图的存储结构
1. 数据表示法
使用邻接矩阵进行实现
2. 邻接表
邻接表的原理是：对图上的每一个顶点都创建一个单链表，然后把该链表上的边都存储在链表上。
- 其中头节点存储图上的节点信息：
- 由顶点号和指向下一个节点的指针共同组成
- 其他节点由三个部分组成：
- 和头节点表示的顶点有边相关联的顶点号
- 边的权值
- 指向下一个节点的指针
优点在于：
对于有n个顶点和e条边的无向图，其邻接表有n个顶点结点和2e个边结点，而对于有n个顶点和e条弧的有向图，其邻接表有n个顶点结点和e个弧结点。显然，对于稀疏图，邻接表比邻接矩阵节省存储空间。
下面给出一个例子：
这就是一个邻接表
这就是图和邻接表的对应关系，使用链表来进行存储，极大的优化了链表的存储效率
- 无向图：
在无向图的邻接表中，顶点vi的度恰好等于该顶点的邻接表中边节点的度数
- 有向图：
有向图中关于方向的要求比较苛刻
同时需要特别留意字典顺序进行穿插
有向图中，顶点vi的领接表中边结点的个数仅为该顶点的出度，若要求顶点的入度，则需遍历整个邻接表。有时为了便于求有向图中顶点的入度，可以通过建立一个有向图的逆邻接表得到。逆邻接表就是对图中的每个顶点vi建立一个链接以vi为重点的弧的边表。
3. 十字链表
对于有向图来说，邻接表是有缺陷的。关心了入度问题，想了解入度就必须要遍历整个图才能知道，反之，逆领接表解决了入度却不了解出度的情况。而十字链表可以把它们整合在一起。
十字链表的好处就是因为把邻接表和逆邻接表整合在了一起，这样既容易找到以vi为尾的弧，也容易找到以vi为头的弧，因而容易求得顶点的出度和入度。而且，除了结构复杂一点外，创建图算法的时间复杂度和邻接表相同，因此，在有向图的应用中，十字链表是非常好的数据结构模型。
同时对于有向图并且可以多次重复利用某条边来说，使用十字链表更加适合
当涉及到有向图和边的重复使用时，十字链表是一种常见的图表示方法。十字链表在表示有向图时比邻接表更灵活，因为它分别维护了以每个顶点为起点和终点的边。
以下是对十字链表的简要介绍：
- 顶点节点：
- 每个顶点都由一个顶点节点表示，其中包含顶点的数据以及两个指针：
firstOutEdge和firstInEdge。 firstOutEdge指向以该顶点为起点的第一条边的头部。firstInEdge指向以该顶点为终点的第一条边的头部。
- 边节点：
- 每个边都由一个边节点表示，其中包含目标顶点的索引、边的权重以及两个指针：
nextOutVertex和nextInVertex。 nextOutVertex指向下一条以相同起点的边。nextInVertex指向下一条以相同终点的边。
- 表示：
- 顶点通过十字链表连接，构成整个图的表示。
- 图中的每个顶点都可以分别访问以该顶点为起点和终点的所有边。
- 优势：
- 十字链表对于表示有向图中的边非常灵活，尤其适用于需要支持边的重复使用的情况。
- 它相对节省空间，因为只存储实际存在的边，而不需要为不存在的边分配空间。
以下是一个简单的例子，说明如何使用十字链表表示有向图：
在这个例子中，顶点1有两条出边和一条入边，顶点2有两条出边和一条入边，以此类推。这种表示方法使得图的遍历和操作变得更为方便。
- 建立各个链表中用于存储顶点的首元节点结构：
data | firstin | firstout |
首元节点中有一个数据域和两个指针域（firstin和firstout）来表示：
十字链表本质上来说就是每个节点之间建立起两个链表，分别存储以该节点为弧头和以该节点为弧尾的所有顶点
- 链表中的普通节点的结构是：
tailvex | headvex | hlink | tlink | info |
十字链表中的普通节点存储分为五部分内容：
顶点节点：
- 指向以该顶点为起点的边的指针
- 指向以该顶点为终点的边的指针
边节点：
- 这条边的终点
- 这条边的权重
- 指向下一条以相同起点的边的指针
- 指向下一条以相同终点的边的指针
4. 邻接多重表
有向图的优化存储可以用十字链表来解决，对于无向图来说，如果更关注边的操作，可以仿照十字链表的方式，对边表结点的结构进行一些改造，即形成邻接多重表。
邻接多重表与邻接表的区别，仅仅是在于同一条边在邻接表中用两个结点表示，而在邻接多重表中只有一个结点。这样对边的操作就方便多了。
- 完全图(Complete Graph)
也称简单完全图。假设一个图有n个顶点，那么如果任意两个顶点之间都有边的话，该图就称为完全图。
- 一条边对应两度，会产生两度的影响