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[i][j] = vis[j][i] 。

邻接矩阵的优点是：效率高，便于理解，代码简单

邻接矩阵缺点是：占用的内存多。试想一下，如果一张图顶点很多，但是边却很少，那么对应的邻接矩阵中大多数内容都是 0 ，我们称这种情况为稀疏矩阵。如果图中有 105105 个顶点，对应的邻接矩阵数组就有 8*10101010 Byte ,约等于 80000 MB 。你的程序一定爆内存了。

2.5.2 链表法

邻接表可以解决邻接矩阵占用空间的问题。邻接表中，图的每一个顶点都是一个链表的头节点，其后连接着该顶点能够直接达到的相邻顶点。

如果要查询某一个顶点 i 一步能访问的顶点，那只需要便令顶点为 i 的链表即可。

如果要查询有哪些顶点一步能到达顶点 i，这就很尴尬，要访问所有顶点的玲姐表，访问量很大。

2.5.3 逆链表法

为了解决有哪些顶点一步能到达顶点 i的问题，我们可以采用逆邻接表法。逆邻接表，和邻接表是正好相反的。逆邻接表每一个顶点作为链表的头节点，后继节点所存储的是能够直接达到该顶点的相邻顶点。

但是，逆链表法在处理顶点 i 一步能到达哪些顶点问题时，又很尴尬。

2.5.4 十字链表法

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