图
图（Graph）是比树还要难以理解和学习的“多对多”数据结构，可以认为树也是图的一种。图的知识点众多，按照存储路径的方向分，可分为无向图和有向图，按照图的存储结构分，可分为完全图与有向完全图、连通图与强连通图、连通分量与强连通分量、无环图与有向无环图，其涉及的算法则包括克鲁斯卡尔算法、普里姆算法、迪杰斯特拉算法和弗洛伊德算法等。如下图所示为图的分类。
与表和树相同，图虽然有“多对多”的逻辑关系，但同样可以使用顺序存储和链式存储有效地保存数据元素：与表和树不同的是，图的顺序存储需要两个数组（包含一个二维教组），链式存储则包括邻接表、邻接多重表和十字链表等。
与表和树不同，图中存储的数据元素不叫节点，我们称其为顶点；若两个顶点直接相连，则称它们互为邻接点：两个顶点及它们中间途径的所有顶点组成的序列称为路径；用字母V表示图中顶点的集合，
V
R
V_R
VR表示图中顶点之间关系的集合。
注意：如果路径的始末点相同，则该路径为“回路”或“环”。
按存储路径方向分类
按存储路径的方向，图分为单向图和双向图。单向/双向图的区别就是看路径上有没有箭头，无箭头（双向）的图为无向图，有箭头（单向）的图为有向图。如下图所示为单向/双向图的分类。
1.无向图
在无向图中（如下图所示），相连的两个顶点互相建立联系，顶点的集合可表示为
V
=
{
V
1
,
V
2
,
V
3
,
V
4
,
V
5
,
V
6
,
V
7
}
V=\{V1,V2,V3,V4,V5,V6,V7\}
V={V1,V2,V3,V4,V5,V6,V7}顶点关系的集合可表示为
V
R
=
{
(
V
1
,
V
2
)
,
(
V
1
,
V
3
)
,
(
V
2
,
V
4
)
,
(
V
2
,
V
5
)
,
(
V
4
,
V
5
)
,
(
V
3
,
V
6
)
(
V
3
,
V
7
)
,
(
V
6
,
V
7
)
}
V_R=\{ (V1,V2),(V1,V3),(V2,V4),(V2,V5),(V4,V5),(V3,V6)(V3,V7),(V6,V7) \}
VR={(V1,V2),(V1,V3),(V2,V4),(V2,V5),(V4,V5),(V3,V6)(V3,V7),(V6,V7)}。
2. 有向图
在有向图中（如下图所示），箭头出发的顶点称为“初始点”或“弧尾”，箭头指向的顶点称为“终端点”或“弧头”，指向某一顶点的箭头数称为该顶点的“入度”（InDegree，项点V的入度可表示为 ID(V))，离开某一顶点的箭头数称为该顶点的“出度”（OutDegree，顶点V的出度可表示为 OD（V））。
和无向图不同，在有向图中，各个项点之同的关系是“单向”的。在无向图中，用（V1,V2）表示两个顶点间的二元关系，并将其称为“边”：在有向图中，用＜V1,V2>表示两个顶点间的二元关系，并将其称为“弧”。
按存储结构分类
除了无向图和有向图之外，根据图的存储结构，图又可分为完全图与有向完全图、连通图与强连通图、连通分量与强连通分量、无环图与有向无环图，如下图所示。
1. 完全图与有向完全图
完全图指各顶点与其他顶点均有联系的无向图，满足该条件的有向图即为有向完全图，如下图所示。
一定要分清的是：具有n个顶点的完全图拥有
n
(
n
−
1
)
2
\frac{n(n-1)}{2}
2n(n−1)条边，具有n个顶点的有向完全图拥有n(n-1)条弧。
2.连通图与强连通图
如果图的两个顶点之间至少存在一条路径，则称这两个顶点是连通的。如果无向图中的任意两个顶点都是连通的，则称其为连通图。同理，满足该条件的有向图即为强连通图。如下图所示为连通图与强连通图。
显而易见，完全图一定是连通图，而有向完全图一定是强连通图。
3. 连通分量与强连通分量
如果无向图不是连通图，但其最大连通子图符合连通图的定义，则称该子图为连通外量。同理，满足该条件的有问图即为强连通分量。如下图所示为连通分量与强连通分量示意图。
注意：连通分量的前提是其必须是非连通图。
4. 无环图与有向无环图
无环图就容易理解了，没有回路（环）的无向图都为无环图。同理，满足该条件的有向图即为有向无环图。如下图所示为无环图与有向无环图。
