数据布局-图

1. 感性的认识图

图是是数据布局中最复杂的一种。图的概念特别特别的多，相干的算法题目大概多。假如我们一开始就讲复杂的概念，大概许多同砚都学不下去，太深奥，太枯燥。我们不妨先感性的认识图。
图看起来就像下图如许：

在盘算机科学中，一个图就是一些顶点的聚集，这些顶点通过一系列边结对（毗连）。顶点用圆圈表现，边就是这些圆圈之间的连线。顶点之间通过边毗连。
注意：顶点偶然也称为节点大概交点，边偶然也称为链接。
一个图可以表现一个交际网络，每一个人就是一个顶点，相互认识的人之间通过边接洽。

图有各种形状和巨细。边可以有权重（weight），即每一条边会被分配一个正数大概负数值。思量一个代表航线的图。各个都会就是顶点，航线就是边。那么边的权重可以是飞行时间，大概机票代价。

有了如许一张假设的航线图。从旧金山到莫斯科最自制的门路是到纽约转机。
边可以是有方向的。在上面提到的例子中，边是没有方向的。比方，假如 Ada 认识 Charles，那么 Charles 也就认识 Ada。相反，有方向的边意味着是片面的关系。一条从顶点 X 到 顶点 Y 的边是将 X 联向 Y，不是将 Y 联向 X。
继承前面航班的例子，从旧金山到阿拉斯加的朱诺有向边意味着从旧金山到朱诺有航班，但是从朱诺到旧金山没有（这大概意味着你要先从朱诺飞到某个地方，颠末中转到达旧金山，又大概你改成开车去旧金山）。

2. 图的界说和根本概念

2.1 图的界说和表现

图是由顶点的有穷非空聚集和顶点之间边的聚集构成，通过表现为 G(V,E) ，此中，G 表现一个图，V 是图 G 中顶点的聚集，E 是图 G 中边的聚集。

以上图为例，V={1,2,3,4,5,6}, E = {<1,2>,<1,4>,<2,5>,<4,3>,<5,4>,<6,5>}。
上面的这些表现符号，紧张是为了便于理论的报告和推导。
2.2 无向图和有向图

无边图：若顶点 ViVi​到 VjVj​ 之间的边没有方向，则称这条边为无向边（Edge），用序偶对(ViVi​,VjVj​)标示。下图为无向图的一个例子：

有向图：若从顶点 ViVi​到 VjVj​ 的边是有方向的，则成这条边为有向边，也称为弧（Arc）。用有序对<ViVi​，VjVj​> 标示，ViVi​ 称为弧尾，VjVj​ 称为弧头。假如恣意两条边之间都是有向的，则称该图为有向图。下图为一个有向图的例子，顶点 1,2,4 都可以到大顶点 3 ，但是顶点 3 无法到大顶点 1,2,4。

2.3 入度和出度

对于有向图中的一个顶点 V 来说，箭头指向 V 的弧的数量为 V 的入度（InDegree，记为 ID(V)）；箭头阔别 V 的弧的数量为 V 的出度（OutDegree，记为OD(V)）。
入度和出度信息在欧拉图相干题目中尤其紧张。
2.4 路径和回路

无论是无向图还是有向图，从一个顶点到另一顶点途经的全部顶点构成的序列（包罗这两个顶点），称为一条路径。假如路径中第一个顶点和末了一个顶点类似，则此路径称为回路（或环）。
在此根本上，若路径中各顶点都不重复，此路径被称为简朴路径；若回路中的顶点互不重复，此回路被称为简朴回路（或简朴环）。
2.5 图在步伐中的存储和表达

2.5.1 毗邻矩阵

毗邻矩阵是指用一个二维的数组来记载图中各个顶点之间是否存在边大概弧。假如顶点之间存在边或弧，在相应位置用 1 表现，反之用 0 表现；假如使用二维数组存储网中顶点之间的关系，顶点之间假如有边大概弧的存在，在数组的相应位置存储其权值；反之用 0 表现。

无向图中的边，可以明白为 2 条方向相反的边，以是，无向图毗邻矩阵的内容是对称的。 vis[j] = vis[j] 。
毗邻矩阵的优点是：服从高，便于明白，代码简朴
毗邻矩阵缺点是：占用的内存多。试想一下，假如一张图顶点许多，但是边却很少，那么对应的毗邻矩阵中大多数内容都是 0 ，我们称这种环境为希奇矩阵。假如图中有 105105 个顶点，对应的毗邻矩阵数组就有 8*10101010 Byte ,约即是 80000 MB 。你的步伐肯定爆内存了。
2.5.2 链表法

毗邻表可以办理毗邻矩阵占用空间的题目。毗邻表中，图的每一个顶点都是一个链表的头节点，厥后毗连着该顶点可以大概直接到达的相邻顶点。

假如要查询某一个顶点 i 一步能访问的顶点，那只必要便令顶点为 i 的链表即可。
假如要查询有哪些顶点一步能到达顶点 i，这就很尴尬，要访问全部顶点的玲姐表，访问量很大。
2.5.3 逆链表法

为了办理有哪些顶点一步能到达顶点 i的题目，我们可以接纳逆毗邻表法。逆毗邻表，和毗邻表是恰好相反的。逆毗邻表每一个顶点作为链表的头节点，后继节点所存储的是可以大概直接到达该顶点的相邻顶点。
但是，逆链表法在处置惩罚顶点 i 一步能到达哪些顶点题目时，又很尴尬。

2.5.4 十字链表法

既然毗邻表和逆毗邻表各有各的尴尬，那么，我们就引入了十字链表。十字链表的每一个顶点，都是两个链表的根节点，此中一个链表存储着该顶点能到达的相邻顶点，另一个链表存储着能到达该顶点的相邻节点。