图结构

我们在之前的单链表，循环链表等链表章节当中我们介绍了每个元素之间只有一个直接前驱和一个直接后继元素，同样的，在树与二叉树等章节当中介绍了在树这种结构中，数据元素之间是层次关系，并且每一层上的数据元素可能和下一层中多个元素相关，但只能和上一层中一个元素相关，但是以上这些仅仅都只是一对一，一对多的简单模型

那么如果元素之间存在多对多的关系呢，我们又该如何来处理呢，所以今天我们就来看看另外一种名为图的结构

图的定义

图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为 G(V, E)，其中 G 表示一个图，V 是图 G 中顶点的集合，E 是图 G 中边的集合，比如下图，就是一个图结构

对于图的定义，我们需要明确几个注意的地方

线性表中我们把数据元素叫元素，树中叫结点，而在图中数据元素我们称之为顶点（Vertex）
线性表可以没有数据元素，称为空表，树中可以没有结点，叫做空树，而图结构强调顶点集合 V 要有穷非空
线性表中，相邻的数据元素之间具有线性关系，树结构中，相邻两层的结点具有层次关系，而图结构中，任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边来表示，不过需要注意，边集可以是空的

关于图的各种定义概念十分之多，我们一个一个来进行了解

无向边

若顶点 Vi 到 Vj 之间的边没有方向，则称这条边为无向边（Edge），用无序偶（Vi, Vj）来表示，需要注意的是，无序偶的顺序是随意的，比如写成（Vj, Vi）也是可行的

比如上图当中 G1 是一个无向图，G1 = {V1, E1}，其中

V1 = {A, B, C, D}
E1 = {(A, B), (B, C), (C, D), (D, A), (A, C)}

有向边

若从顶点 Vi 到 Vj 的边有方向，则称这条边为有向边，也成为弧（Arc），用有序偶 <Vi, Vj> 来表示，Vi 称为弧尾，Vj 称为弧头，需要注意的是，有序偶的顺序不能是随意的，需要与方向指向对应，如下图

比如上图 G2 是一个无向图，G2 = {V2, E2}，其中

V2 = {A, B, C, D}
E2 = {<B, A>, <B, C>, <C, A>, <A, D>}

简单图

在图结构中，若不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图为简单图，简单图也是使用最为广泛的，比如下面两个反面示例，它们都不属于简单图

无向完全图

在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图，含有 n 个顶点的无向完全图有 n * (n - 1) / 2 条边，如下图所示

有向完全图

在有向图中，如果任意两个顶点之间都存在方向互为相反的两条弧，则称该图为有向完全图，含有 n 个顶点的有向完全图有 n * (n - 1) 条边，如下图所示

稀疏图和稠密图

这里的稀疏和稠密是模糊的概念，一般使用较少，而且都是相对而言的，通常认为边或弧数小于 n * logn（n 是顶点的个数）的图称为稀疏图，反之称为稠密图

网

有些图的边或弧带有与它相关的数字，这种与图的边或弧相关的数叫做权（Weight，与带权树概念是一致的），带权的图通常称为网（Network），如下图所示

子图

假设有两个图 G1 = (V1, E1) 和 G2 = (V2, E2)，如果 V2 ⊆ V1，E2 ⊆ E1，则称 G2 为 G1 的子图（Subgraph），比如下图这样的情况，右边的图均称为左图的子图

无向图的顶点与边之间的关系

对于无向图G = (V, E)，如果边 (V1, V2) ∈ E，则称顶点 V1 和 V2 互为邻接点（Adjacent），即 V1 和 V2相邻接，边 (V1, V2)依附（incident）于顶点 V1 和 V2，或者说边 (V1, V2) 与顶点 V1 和 V2相关联，顶点 V 的度（Degree）是和 V 相关联的边的数目，记为 TD(V)，如下图中的顶点 A 与 B 互为邻接点，边 (A, B) 依附于顶点 A 与 B 上，所以顶点 A 的度为 3

有向图的顶点与边之间的关系

对于有向图G = (V, E)，如果有 <V1,V2> ∈ E，则称顶点 V1邻接到顶点 V2，顶点 V2邻接自顶点 V1，以顶点 V 为头的弧的数目称为 V 的入度（InDegree），记为 ID(V)，以 V 为尾的弧的数目称为 V 的出度（OutDegree），记为 OD(V)，因此顶点 V 的度为 TD(V) = ID(V) + OD(V)，下图顶点 A 的入度是 2，出度是 1，所以顶点 A 的度是 3

路径

无向图G = (V, E) 中从顶点 V1 到顶点 V2 的路径（Path），下图用蓝线列举了从顶点 B 到顶点 D 的四种不同路径

如果 G 是有向图，则路径也是有向的，比如下图用蓝线列举顶点 B 到顶点 D 的两种路径，而顶点 A 到顶点 B 就不存在路径

回路或环

路径的长度是路径上的边或弧的数目，第一个顶点到最后一个顶点相同的路径称为回路或环（Cycle），序列中顶点不重复出现的路径称为简单路径，除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或简单环，比如下面这个图当中左侧是简单环，右侧则不是简单环，因为右图当中的 C 重复出现了

连通图

在无向图G 中，如果从顶点 V1 到顶点 V2 有路径，则称 V1 和 V2 是连通的，如果对于图中任意两个顶点 Vi 和 Vj 都是连通的，则称 G 是连通图（ConnectedGraph），比如下图当中，左侧不是连通图（因为 E，F 独自在一块，没有一个顶点和 ABCD 相连通），而右侧则是连通图