图的定义
在线性表，数据元素之间是被串起来的，仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继，即存在一对一的关系。在树形结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中多个元素相关，但只能和上一层中一个元素相关，即存在一对多的关系。图是一种较线性表和数更加复杂的数据结构。在图结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关，图存在多对多的关系。
如下图1所示，先来看图的定义。
图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G（V, E），其中，G 表示一个图，V 是图 G 中顶点的集合，E 是图 G 中边的集合。
对于图的定义，我们需要明确几个注意的地方。
- 线性表中我们把数据元素叫元素，树中将数据元素叫结点，在图中数据元素我们则称之为顶点（Vertex）。
- 在图结构中，不允许没有顶点，在定义中，若 V 是顶点的集合，则强调了顶点集合 V 有穷非空。但是允许边集 E 为空。
1. 各种图定义
无向边：若顶点 v i v_i vi 到 v j v_j vj 之间的边没有方向，则称这条边为无向边（Edge），用无序偶对（ v i v_i vi， v j v_j vj）来表示。如果图中任意两个顶点之间的边都是无向边，则称该图为无向图。图1.1就是一个无向图，由于是无方向的，连接顶点 A 与 D 的边，可以表示成无序对（A，D），也可以写成（D，A）。
有向边：若从顶点 v i v_i vi 到 v j v_j vj 的边有方向，则称这条边为有向边，也称为弧。用有序偶< v i , v j v_i, v_j vi,vj>来表示， v i v_i vi 称为弧尾， v j v_j vj 称为弧头。如果图中任意两个顶点之间的边都是有向边，则称该图为有向图。图1.2就是一个有向图。连接顶点 A 到 D 的有向边就是弧，A 就是弧尾，D 是弧头，<A, D>表示弧，注意不能写成<D，A>。
简单图：在图中，若不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图为简单图。我们所讨论的范畴也都简单图。下图1.3便不属于我们讨论的范围。
无向完全图：在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。含有 n 个顶点的无向完全图有 n × ( n − 1 ) 2 \frac{n \times{(n - 1)}}{2} 2n×(n−1) 条边。比如图1.4就是无向完全图。
有向完全图：在有向图中，如果任意两个顶点之间都存在边，则称该图为有向完全图。含有 n 个顶点的有向完全图有 n × ( n − 1 ) n \times{(n - 1)} n×(n−1) 条边。比如图1.5就是有向完全图。
权与网：些图的边或弧具有与它相关的数字，这种与图的边或弧相关的数叫做权（Weight）。这些权可以表示从一个顶点到另一个顶点的距离或耗费。这些带权的图通常称为网。图1.6就是一张带权的图，权表示城市的直线距离。
子图：假设有两个图$ G = (V, {E}) 和 G’ = (V’, {E’})$，如果 V ′ ⊆ V V' \subseteq{V} V′⊆V 且 E ′ ⊆ E E' \subseteq{E} E′⊆E，则称$ G’ 为 G $的子图。例如图1.7带底纹的图均为左侧无向图与有向图的子图。
2. 图的顶点与边间关系
邻接：对于无向图 G=(V, {E})，如果边
(
v
,
v
′
)
∈
E
(v, v') \in E
(v,v′)∈E，则称顶点 v 和 v’ 互为邻接点，即 v 和 v’相邻接。对于有向图 G=(V, {E})，如果弧
<
v
,
v
′
>
∈
E
<v,v'>\in E
<v,v′>∈E，则称顶点 v 邻接到顶点v’，顶点v’邻接自顶点 v。
度：顶点 v 的度（Degree）是和 v 相关联边的数目，即为 TD(v)。在无向图中，边数起始就是各顶点度数和的一半。简记之，
e
=
1
2
∑
i
=
1
n
T
D
(
v
i
)
e=\frac{1}{2}\sum_{i=1}^{n}TD(v_i)
e=21∑i=1nTD(vi)。
入度与出度：在有向图中，以顶点 v 为头的弧的数目称为 v 的入度（InDegree），记为ID(v)；以 v 为尾的弧的数目称为 v 的出度（OutDegree），记为OD(v)；顶点 v 的度为 TD(v) = ID(v) + OD(v)。我们可以发现，有向图的边数会等于出度数及入度数，简记之，
e
=
∑
i
=
1
n
I
D
(
v
i
)
=
∑
i
=
1
n
O
D
(
v
i
)
e=\sum_{i=1}^{n}ID(v_i)=\sum_{i=1}^{n}OD(v_i)
e=∑i=1nID(vi)=∑i=1nOD(vi)。
路径：无向图 G=(V,{E}) 中从顶点 v 到顶点 v’的路径（Path）是一个顶点序列
(
v
=
v
i
,
0
,
v
i
,
1
,
.
.
.
,
v
i
,
m
)
(v=v_{i,0},v_{i,1},...,v_{i,m})
(v=vi,0,vi,1,...,vi,m)，其中
(
v
i
,
j
−
1
,
v
i
,
j
)
∈
E
，
i
≤
j
≤
m
(v_{i,j-1},v_{i,j})\in E，i\le j \le m
(vi,j−1,vi,j)∈E，i≤j≤m。例如图2.1中列举了顶点 B 到顶点 D 四种不同的路径。
如果 G 是有向图，则路径也是有向的，顶点序列应满足 < v i , j − 1 , v i , j > ∈ E ， i ≤ j ≤ m <v_{i,j-1},v_{i,j}>\in E，i \le j \le m <vi,j−1,vi,j>∈E，i≤j≤m。例如下图2.2，顶点 B 到 D 有两种路径。
路径的长度是路径上的边或弧的数目。
简单路径：序列中顶点不重复出现的路径称为简单路径。
回路或环：第一个顶点到最后一个顶点相同的路径称为回路或环（Cycle）。其中除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或简单环。例如下图2.3，其中图即为简单回路，而右图则不是，因为出现重复顶点 C。
3. 连通图相关术语
连通图：在无向图 G 中，如果从顶点 v 到顶点 v’有路径，则称 v 和 v’是连通的。如果对于图中任意两个顶点
v
i
、
v
j
∈
E
，
v
i
和
v
j
v_i、v_j \in E，v_i 和 v_j
vi、vj∈E，vi和vj 都是连通的，则称 G 是连通图。
比如图3.1就不是连通图，因为顶点 A 到 顶点 E 或 F 并不连通。而图3.2就是连通图，其中顶点 A、B、C 和 D 两两都是连通的。
连通分量：无向图的极大连通子图称为连通分量。注意连通分量的概念，它强调：
- 要是子图；
- 子图要是连通的；
- 连通子图含有极大顶点数；
- 具有极大顶点数的连通子图包含依附于这些顶点的所有边。
上面的图3.1具有两个连通分量，分别为上面的图3.1和下面的图3.3。但是图3.4则不是连通分量，因为其不符合极大顶点数的条件。
强连通图：在有向图 G 中，如果对于每一对
v
i
、
v
j
∈
V
、
v
i
≠
v
j
v_i、v_j \in V、v_i \ne v_j
vi、vj∈V、vi=vj，从
v
i
v_i
vi 到
v
j
v_j
vj 和从
v
j
v_j
vj 到
v
i
v_i
vi 都存在路径，则称 G 是强连通图。
强连通分量：有向图中的极大强连通子图称作有向图的强连通分量。与连通分量所强调的相似，唯一不同的是强连通分量要求子图要是强连通的。
比如下图中图1不是强连通图，而图2则是强连通图。同时图2也是图1的强连通分量。
连通图生成树：所谓的一个连通图的生成树是一个极小的连通子图。该极小的连通子图强调：
- 要是子图；
- 子图要是连通的；
- 连通子图含有极大顶点数；
- 具有极大顶点数的连通子图包含依附于这些顶点的最少边。
所以一个含有 n 个顶点的连通图，它的生成树是也含有 n 个顶点，并且只有足以构成一棵树的 n - 1 条边。比如下图的图2就是图1生成树。
从这里我们也可以知道，如果一个图有 n 个顶点和少于 n - 1 条边，则是非连通图，如果它多于 n - 1 条边，必定构成环。另外，有n - 1 条边并不一定是生成树，比如下图图3.7。
如果一个有向图恰有一个顶点的入度为0，其余顶点的入度均为1，则是一颗有向树。
[1] 参考书籍：大话数据结构