data structure

1. 图的定义

图 G 由顶点集 V 和边集 E 组成,记为 G=(V,E) 。其中 V(G) 表示图 G 中顶点的有限非空集;E(G) 表示图 G 中顶点之间的关系(边)集合。用 |V| 表示图 G 中的顶点个数,也称图 G 的阶。用 |E| 表示图 G 中边的条数 。顶点用 vn 表示,边用 (u,v) 表示 。

注意:线性表可以是空表,树可以是空树,但图不可以是空图。就是说,图中不能一个顶点也没有,图的顶点集 V 一定非空,但边集 E 可以为空,此时图中只有顶点而没有边 。

1.1 有向图

若 E 是有向边(也称弧)的有限集合时,则图 G 为有向图。弧是顶点的有序对,记为 <v,w> ,v 是弧头,w 是狐尾 。

1.2 无向图

若 E 是无向边(简称边)的有限集合时,则图 G 为无向图。边是顶点的无序对,记为 (v,w)(w,v) 。可以说 顶点 v 和 顶点 w 互为邻接点 。

1.3 简单图

一个图 G 若满足:1. 不存在重复边 2. 不存在顶点到自身的边,则称图 G 为简单图。

1.4 多重图

若图 G 中某两个结点之间的边数多于一条,又允许顶点通过同一条边和自己关联,则 G 为多重图。多重图的定义和简单图是相对的。

1.5 完全图(也称完全简单图)

在无向图中,若任意两个顶点之间都存在边,则称该图为无向完全图。含有 n 个顶点的无向完全图有 n(n-1)/2 条边 。

在有向图中,若任意两个顶点之间都存在方向相反的两条弧,则称该图为有向完全图。含有 n 个顶点的有向完全图有 n(n-1) 条有向边。

1.6 子图

设有两个图 G=(V,E) 和 G’=(V’,G’) ,若 V’ 是 V 的子集,且 E‘ 是 E 的子集,则称 G’ 是 G 的子图。若有满足 V(G’)=V(G) 的子图 G’ ,则称其为 G 的生成子图

注意:并非 V 和 E 的任何自己都能构成 G 的子图,因为这样的子集可能不是图,即 E 的子集中的某些边关联的顶点可能不再这个 V 的子集中。

1.7 连通、连通图和连通分量

在无向图中,若从顶点 v 到顶点 w 有路径存在,则称 v 和 w 是连通的。若图 G 中任意两个顶点是连通的,则称图 G 为连通图,否则称为非连通图。无向图中极大连通子图称为连通分量。若一个图有 n 个顶点,并且边数小于 n-1 ,则此图必是非连通图。

注意 :弄清连通、连通图、连通分量的概念非常重要。首先要区分极大连通子图和极小连通子图,极大连通子图是无向图的连通分量,极大即要求该连通子图包括其所有的边;极小连通子图是既要保持图连通又要使得边数最少的子图。

1.8 强连通图、强连通分量

在有向图中,若从顶点 v 到顶点 w 和从顶点 w 到顶点 v 之间都有路径,则称这两个顶点是强连通的。若图中任何一对顶点都是强连通的,则称此图为强连通图。有向图的极大强连通图称为有向图的强连通分量。

注意:强连通图、强连通分量只是针对有向图而言的。一般在无向图中讨论连通性,在有向图中考虑强连通性。

1.9 生成树、生成森林

连通图的生成树是包含图中全部顶点的一个极小连通图。若图中顶点为 n,则它的生成树含有 n-1 条边。对生成树而言,若砍去它的一条边,则会变成非连通图,若加上一条边则会形成一个回路。在非连通图中,连通分量的生成树构成了非连通图的生成森林。

注意:包含无向图中全部顶点的极小连通子图,只有生成树满足条件,因为砍去生成树的任一条边,图将不再连通。

1.10 顶点的度、入度和出度

图中每个顶点的度定义为以该顶点为一个端点的边的数目。

对于无向图,顶点 v 的度是指依附于该顶点的边的条数,记为 TD(v)

在具有 n 个顶点 、e 条边的无向图中,ΣTD(v) =2e ,即无向图的全部顶点的度的和等于边数的 2 倍,因为每条边和两个顶点相关联。

对于有向图,顶点 v 的度分为入度和出度,入度是以顶点 v 为终点的有向边的数目,记为 ID(v);而出度是以顶点 v 为起点的有向边的数目,记为 OD(v) 。顶点 v 的度等于其入度和出度之和,即 TD(v)=ID(v)+OD(v)

出度之和=入度之和=e ,因为每条边都有一个起点和一个终点。

1.11 边的权和网

在一个图中,每条边都可以标上具有某种含义的数值,该数值称为该边的权值。这种边上带有权值的图称为带权图,也称网。

1.12 稠密图、稀疏图

边数很少的图称为稀疏图,反之称为稠密图。稀疏和稠密本身是模糊的概念,稀疏图和稠密图常常是相对而言的。一般当图 G 满足 |E|<|V|log|V| 时,可以将 G 视为稀疏图

1.13 路径、路径长度和回路

顶点 v 到顶点 w 之间的一条路径是指路径上的顶点序列 。路径上边的数目称为路径长度。第一个顶点和最后一个顶点相同的路径称为回路或环。若一个图有 n 个顶点,并且有大于 n-1 条边,则此图一定有环。

1.14 简单路径、简单回路

在路径序列中,顶点不重复出现的路径称为简单路径。除第一个顶点和最后一个顶点外,其余顶点不重复出现的回路称为简单回路

1.15 距离

从顶点 u 出发到顶点 v 的最短路径若存在,则此路径的长度称为从 u 到 v 的距离。若从 u 到 v 根本不存在路径,则记该距离为无穷(∞)

1.16 有向树

一个顶点的入度为 0,其余顶点的入度均为 1 的有向图,称为有向树 。