数据结构-图-概念
知识框架
图的基本概念
在线性表中，数据元素之间是被串起来的，仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继。在树型结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层多个元素相关，但只能和上一层中一个元素相关。图是一种较线性表和树更加复杂的数据结构。在图结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。
一、图的定义
图(Graph)是由顶点的有穷非空集合V(G)和顶点之间边的集合E(G)组成，通常表示为：G=(V,E),其中，G表示个图，V是图G中顶点的集合，E是图G中边的集合。若$V={v_1,v_2,v_3,\dots,v_n}$ ,则用 $|V|$ 表示图G中顶点的个数，也称图G的阶，$E={(u,v)|u \in V, v \in V}$ ，用 $|E|$ 表示图G中边的条数。
注意：线性表可以是空表，树可以是空树，但图不可以是空图。就是说，图中不能一个顶点也没有，图的顶点集 V 一定非空，但边集 E 可以为空，此时图中只有顶点而没有边。
V: vertex 顶点
E: edge 边
二、图的基本概念和术语
1、有向图
若E是有向边(也称弧)的有限集合时，则图G为有向图。弧是顶点的有序对，记为 <v,w> ,其中v,w是顶点，v称为弧尾，w称为弧头，<v,w>称为从顶点v到顶点w的弧，也称v邻接到w,或w邻接自v。
图（a）所示的有向图 $G_1$ 可表示为 $$ G1 = (V_1 , E_1) \ V1 = (1,2,3) \ E1 = {<1,2>,<2,1>,<2,3>} $$
2、无向图
若E是无向边（简称边）的有限集合时，则图 G 为无向图。边是顶点的无序对，记为 (v,w) 或 (w,v) ,因为 (v,w)=(w,v),其中v,w是顶点。可以说顶点w喝顶点v互为邻接点。边（v,w）依附于顶点w和v，或者说边（v,w）和顶点v,w相关联。
图 （b）所示的无向图 G2 可表示为 $$ G_2 = (V_2,E_2) \ V_2 = {1,2,3,4} \ E2 = {(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)} $$
3、 简单图
一个图 G 若满足：①不存在重复边；②不存在顶点到自身的边，则称图 G 为简单图。上图中 $G_1$ 和 $G_2$ 均为简单图。数据结构中仅讨论简单图。
4、多重图
若图 G 中某两个节点之间的边数多于一条，又允许顶点通过同一条边和自己关联，则图 G 为多重图。多重图的定义和简单图是相对的。
5、完全图（也称简单完全图）
对于无向图，|E|的取值范围是 0 到 n(n-1)/2 ,有 n(n-1)/2 条边的无向图称为完全图，在完全图中任意两个顶点之间都存在边。对于有向图，|E| 的取值范围是 0 到 n(n-1) ，有n(n-1)条弧的有向图称为有向完全图，在有向完全图中任意两个顶点之间都存在方向相反的两条弧。上图中 $G_2$ 为无向完全图，而 $G_3$ 为有向完全图。
6、子图
设有两个图 $G = (V,E)$ 和 $G’=(V’,E’)$ ，若 $V’$是 $V$ 的子集，且 $E’$ 是 $E$ 的子集，则称 $G’$ 是 $G$ 的子图。若有满足 $V(G’) = V(G)$ 的子图 $G’$ ，则称其为 G 的 生成子图。上图中 $G_3$ 为 $G_1$ 的子图。
注意: 并非 V 和 E 的任何子集都能构成 G 的子图，因为这样的子集可能不是图，即 E 的子集中的某些边关联的顶点可能不在这个 V 的子集中。
7、联通、联通图和联通分量
在无向图中，若从顶点 $v$ 到顶点 $w$ 有路径存在，则称 $v$ 和 $w$ 是联通的。若图 G 中任意的两个顶点都是联通的，则称图 G 为 连通图，否则称为非连通图。无向图中的极大连通子图称为连通分量。若一个图有 $n$ 个顶点，并且边数**小于 $n-1$ ** ,则此图必是非连通图。如下图（a）所示，图 $G_4$ 有3个连通分量，如图 （b）所示。
注意: 弄清连通、连通图、连通分量的概念非常重要。首先要区分极大连通子图和极小连通子图，极大连通子图是无向图的连通分量，极大即要求该连通子图包含其所有的边；极小连通子图是既要保持图连通又要使得边数最少的子图。
8、强连通图、强连通分量
在有向图中，若从顶点 $v$ 到顶点 $w$ 和从顶点 $w$ 到顶点 $v$ 之间都有路径，则称这两个顶点是强连通的。若图中任何一对顶点都是强连通的，则称此图为强连通图。有向图中的极大强连通子图称为有向图的强连通分量，图 $G_1$ 的强连通分量如下图所示。
注意：强连通图、强连通分量只是针对有向图而言的。一般在无向图中讨论连通性，在有向图中考虑强连通性。
9、生成树、生成森林
连通图的生成树是包含图中全部顶点的一个极小连通子图。若图中顶点数为 $n$ ，则它的生成树含有 $n-1$ 条边。对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路。在非连通图中，连通分量的生成树构成了非连通图的生成森林。图 $G_2$ 的一个生成树如下图所示。
注意：包含无向图中全部顶点的极小连通子图，只有生成树满足条件，因为砍去生成树的任一条边，图将不再连通。
10、顶点的度、入度和出度
图中每个顶点的度定义为以该顶点为另一个端点的数目。
对于无向图，顶点 $v$ 的度是指依附于该顶点的边的条数，记为 $T D(v)$
在具有 $n$ 个顶点、$e$ 条边的无向图中，$ \sum_{i=1}^{n} TD(v_i) = 2e$ ，即无向图的全部顶点的度的和等于边数的2倍，因为每条边和两个顶点相关联。
对于有向图，顶点 $v$ 的度分为 入度 和 出度，入度是以顶点 $v$ 为终点的有向边的数目，记为 $I D(v)$ ;而出度是以顶点 $v$ 为起点的有向边的数目，记为 $O D(v)$ 。顶点 $v$ 的度等于其入度和出度之和，即 $T D(v) = ID(v)+OD(v)$。
在具有 $n$ 个顶点，$e$ 条边的有向图中，$\sum_{i=1}^{n} ID(v_i) = \sum_{i=1}^{n} OD(v_i) = e$，即有向图的全部顶点的入度之和与出度之和相等，并且等于边数。这是因为每条有向边都有一个起点和终点。
11、边的权和网
在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的 权值。这种边上带有权值的图称为带权图，也称 网。
12、稠密图、稀疏图
边数很少的图称为稀疏图，反之称为稠密图。稀疏和稠密本身是模糊的概念，稀疏图和稠密图常常是相对而言的。一般当图 G 满足 $|E| < |V|log|V|$ 时，可以将 G 视为稀疏图。
13、路径、路径长度和回路
顶点 $v_p$ 到顶点 $v_q$ 之间的一条路径是指顶点序列 $v_p,v_{i_1},v_{i_2},\dots,v_{i_m},v_q$ ，当然关联的边也可以理解为路径的构成要素。路径上边的数目称为路径长度。第一个顶点和最后一个顶点相同的路径称为回路或环。若一个图有 n 个顶点，并且有大于 n-1 条边，则此图一定有环。
14、简单路径、简单回路
在路径序列中，顶点不重复出现的路径称为简单路径。除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。
15、距离
从顶点 $u$ 出发到顶点 $v$ 的最短路径若存在，则此路径的长度称为从 $u$ 到 $v$ 的距离。若从$u$ 到 $v$ 根本不存在路径，则记该距离为无穷 $(\infty)$ 。
16、有向树
一个顶点的入度为 0 、其余顶点的入度均为 1 的有向图，称为有向树。