图的基本定义

这是《大话数据结构》第七章图的基本知识总结，首先是总结图的基本定义和相关的术语，包括有向图，无向图，连通图等术语的定义。

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

对于上述图的定义，需要注意的是：

线性表中的数据元素被称为元素，树中将数据元素称为结点，而图中数据元素被称为顶点
线性表可以没有数据元素，称为空表；树也可以没有结点，称为空树。但是图的定义中强调了顶点集合V是有穷非空的集合，所以图结构中不能没有顶点。
线性表中，相邻的数据元素之间具有线性关系；树结构中，相邻两层的结点具有层次关系。而图中，任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边来表示，边集可以是空的。

各种图定义

接下来会介绍各自图的定义，包括无向图与有向图，有向完全图和无向完全图，稀疏与稠密图等。

无向边：若顶点$v_i$ 到$v_j$之间的边没有方向，则称这条边为无向边(Edge),用无序偶对$(v_i, v_j)$来表示。

如果图中任意两个顶点之间的边都是无向边，则称该图是无向图。

如下图左边的图就是一个无向图$G_1$，$G_1 = （V_1,{E_1}）$，其中顶点集合 $V_1 = {A,B,C,D}$,边集合是$E_1 = {(A, B), (B, C), (C, D), (D, A), (A, C)}$。

有向边：若顶点$v_i$ 到$v_j$之间的边有方向，则称这条边为有向边，也称为弧(Arc)。用有序偶$$来表示，$v_i$称为弧尾，$v_j$称为弧头。

如果图中任意两个顶点之间的边都是有向边，则称该图是有向图。

如下图右边的图就是一个有向图 $G_2$，$G_2 =（V_2, {E_2}） $,其中顶点集合 $V_2 = {A,B,C,D}$,边集合是$E_2 = {, , , }$。

这里需要注意有向图中有向边的表示是不能随意乱写的，必须是按照定义中$$，弧尾在前，弧头在后的写法。

图中，若不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图是简单图。

如下图所示都不是简单图，而我们主要讨论的都是简单图。

无向完全图是指在无向图中，任意两个顶点之间都存在边。

含有$n$个顶点的无向完全图有$\frac{n\times (n-1)}{2}$条边。

有向完全图是指在有向图中，任意两个顶点之间都存在方向互为相反的两条弧。

含有$n$个顶点的有向完全图有$n\times (n-1)$条边。

由此可以得到一个结论：

对于具有$n$个顶点和$e$条边数的图，无向图有$0 \le e \le \frac{n\times (n-1)}{2}$, 有向图有$0 \le e \le n \times (n-1)$。

有很少边或弧的图称为稀疏图，反之称为稠密图。

这里的稀疏与稠密都是相对而言的。

与图的边或弧相关的数值称为权(Weight)，它可以表示从一个顶点到另一个顶点的距离或耗费。这种带权的图通常称为网(Network)。

下图就是一个带权的图的例子。

假设有两个图 $G = （V，{E}）$，和 $G^\prime = （V^\prime, {E^\prime}） $,如果$V^\prime \subseteq V$, 且 $E^\prime \subseteq E$,则称$G^\prime$是$G$的子图。

下面展示了无向图和有向图与其子图。

图的顶点与边的关系

在无向图 $G=(V,{E})$，如果边 $(v, v^\prime) \in E$,则称顶点$v和v^\prime$互为邻接点(Adjacent),即$v 和 v^\prime$相邻接。边$(v, v^\prime)$依附(incident)于顶点$v 和 v^\prime$，或者说$(v,v^\prime)$与顶点$v 和 v^\prime$相关联。顶点$v$的度(Degree)是和$v$相关联的边的数目，记为TD($v$)。

例如对于上图中上方的无向图，顶点A与B互为邻接点，边(A, B)依附于顶点A与B上，顶点A的度为3。通过计算，可以知道，无向图的边数是各顶点度数和的一半，即$e = \frac{1}{2} \sum_{i=1}^n TD(v_i)$。

有向图 $G=(V,{E})$,如果弧$ \in E$, 则称顶点$v$邻接到顶点$v^\prime$，顶点$v^\prime$邻接自顶点$v$。弧$$和顶点$v,v^\prime$相关联。以顶点$v$为头的弧的数目称为$v$的入度(InDegree),记为$ID(v)$；以顶点$v$为尾的弧的数目称为$v$的出度(OutDegree),记为$OD(v)$,因此顶点$v$的度为$TD(v) = ID(v) + OD(v)$。

例如对上图中下方的有向图，顶点A的入度是2（从B到A的弧，C到A的弧），出度是1（从A到D的弧），所以顶点A的度是3。同样通过计算，可以得到$e =\sum_{i=1}^n ID(v_i) = \sum_{i=1}^n OD(v_i) $。

在无向图 $G=(V,{E})$中从顶点$v$到$v^\prime$的路径(Path)是一个顶点序列$(v=v_{i,0},v_{i,1},\cdots,v_{i,m}=v^\prime),其中(v_{i,j-1},v_{i,j}) \in E, 1 \le j \le m$。

下图就展示了顶点B到顶点D的四种不同路径。

如果$G$是有向图，则路径也是有向的，顶点序列应满足$ \in E, 1 \le j \le m$。如下图所示，顶点B到D右两种路径，而顶点A到B就不存在路径。

路径的长度是路径上的边或弧的数目。

如上图有向图中，左侧的路径长度是2，经过两条弧，而右侧的路径长度是3，经过3条弧。

第一个顶点到最后一个顶点相同的路径称为回路或环(Cycle)。序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或简单环。

下图中，两个图都是一个环，但左侧的图是一个简单环，而右侧图中顶点C重复出现，因此它不是一个简单环。

连通图相关术语

接下来会介绍有关连通图的定义和相关术语。

无向图$G$中，如果从顶点$v$到$v^\prime$有路径，则称$v$和$v^\prime$是连通的。如果对于图中任意两个顶点$v_i、v_j \in V$，$v_i$和$v_j$都是连通的，则称$G$是连通图。

无向图中的极大连通子图称为连通分量。这个连通分量的前提条件有：

是子图；
子图是要连通的；
连通子图要有极大顶点数；
具有极大顶点数的连通子图包含依附于这些顶点的所有边。

有向图$G$中，如果对于每一对$v_i,v_j \in V, v_i \neq v_j$,从$v_i$到$v_j$和从$v_j$到$v_i$都存在路径，则称$G$是强连通图。有向图中的极大强连通子图称做有向图的强连通分量。

如下图所示，图1并不是强连通图，因为顶点A到顶点D存在路径，但不存在从顶点D到顶点A的路径。图2就是强连通图，而且显然图2是图1的极大强连通子图，即是它的强连通分量。

接下来是连通图的生成树定义：

一个连通图的生成树是一个极小的连通子图，它含有图中全部的n个顶点，但只有足以构成一棵树的 n-1 条边。

如下图所示，图1是一个普通图，但是显然它不是生成树，当去掉两条构成环的边后，如图2或图3，就满足生成树的条件了，即n个顶点和n-1条边且连通的定义，它们都是一棵生成树。由此可以得知，如果一个图有n个顶点和小于n-1条边，则是非连通图；如果它多于n-1条边，则必定构成一个环。但有n-1条边也不一定是生成树，如图4。

接下来是有向树的定义：

如果一个有向图中恰有一个顶点的入度为0，其余顶点的入度均为1，则是一棵有向树。

这里入度为0的顶点就相当于树的根结点，而其余顶点的入度都是1，是因为树的非根结点的双亲只有1个。

一个有向图的生成森林由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。

如下图所示，图1是一个有向图，再去掉一些弧后，得到图2和图3，也就是分解成两棵有向树，即图2和图3，而这两棵有向树也是图1有向图的生成森林。

小结

图的基本定义就简单总结到这里，图的术语还是不比树的少，需要多看几遍，同时多使用，接下来会继续总结图的存储结构、遍历等知识点。