图(Graph):由顶点的非空有限集合 V (由
$n > 0$ 个顶点组成)与边的集合 E(顶点之间的关系)构成的结构。其形式化定义为$G = (V, E)$ 。
- 顶点(Vertex):图中的数据元素通常称为顶点,在下面的示意图中我们使用原点来表示顶点。
-
边(Edge):图中两个数据元素之间的关联关系通常称为边,在下面的示意图中我们使用连接两个顶点之间的线段来表示边。边的形式化定义为:$e = \langle u, v \rangle$,表示从
$u$ 到$v$ 的一条边,其中$u$ 称为起始点,$v$ 称为终止点。
-
子图(Sub Graph):对于图
$G = (V, E)$ 与$G^{'} = (V^{'}, E^{'})$ ,如果存在$V^{'} \subseteq V$ ,$E^{'} \subseteq E$,则称图$G^{'}$ 是图$G$ 的一个子图。在下面的示意图中我们给出了一个图$G$ 及其一个子图$G^{'}$ 。特别的,根据定义,$G$ 也是其自身的子图。
按照边是否有方向,我们可以将图分为两种类型:「无向图」 和 「有向图」。
- 无向图(Undirected Graph):如果图中的每条边都没有指向性,则称为无向图。例如朋友关系图、路线图都是无向图。
- 有向图(Directed Graph):如果图中的每条边都具有指向性,则称为有向图。例如流程图是有向图。
在无向图中,每条边都是由两个顶点组成的无序对,例如顶点
在有向图中,有向边也被称为弧,每条弧是由两个顶点组成的有序对,例如从顶点
如果无向图中有
如果有向图中有
如下图所示,左侧为包含 4
个顶点的完全无向图,右侧为包含 4
个顶点的完全有向图。
下面介绍一下无向图和有向图中一个重要概念 「顶点的度」。
-
顶点的度:与该顶点
$v_i$ 相关联的边的条数,记为$TD(v_i)$ 。
例如上图左侧的完全无向图中,顶点 3
。
而对于有向图,我们可以将顶点的度分为 「顶点的出度」 和 「顶点的入度」。
-
顶点的出度:以该顶点
$v_i$ 为出发点的边的条数,记为$OD(v_i)$ 。 -
顶点的入度:以该顶点
$v_i$ 为终止点的边的条数,记为$ID(v_i)$ 。 - 有向图中某顶点的度 = 该顶点的出度 + 该顶点的入度,即
$TD(v_i) = OD(v_i) + ID(v_i)$ 。
「路径」 是图中的一个重要概念,对于图
简单来说,如果顶点
-
环(Circle):如果一条路径的起始点和终止点相同(即
$v_{i_0} = v_{i_m}$ ),则称这条路径为 「回路」 或者 「环」。 -
简单路径:顶点序列中顶点不重复出现的路径称为 简单路径。
而根据图中是否有环,我们可以将图分为「环形图」和「无环图」。
- 环形图(Circular Graph):如果图中存在至少一条环路,则该图称为环形图。
- 无环图(Acyclic Graph):如果图中不存在环路,则该图称为无环图。
特别的,在有向图中,如果不存在环路,则将该图称为 「有向无环图(Directed Acyclic Graph)」。因为有向无环图拥有为独特的拓扑结构,经常被用于处理动态规划、导航中寻求最短路径、数据压缩等多种算法场景。
在无向图中,如果从顶点
- 连通无向图:在无向图中,如果图中任意两个顶点之间都是连通的,则称该图为连通无向图。
- 非连通无向图:在无向图中,如果图中至少存在一对顶点之间不存在任何路径,则该图称为非连通无向图。
如下图所示,左侧图中
下面介绍一下无向图的 「连通分量」 概念。有些无向图可能不是连通无向图,但是其子图可能是连通的。这些子图称为原图的连通子图。而无向图的一个极大连通子图(不存在包含它的更大的连通子图)则称为该图的 连通分量。
- 连通子图:如果无向图的子图是连通无向图,则该子图称为原图的连通子图。
- 连通分量:无向图中的一个极大连通子图(不存在包含它的更大的连通子图)称为该图的连通分量。
- 极⼤连通⼦图:无向图中的一个连通子图,并且不存在包含它的更大的连通子图。
例如上图中右侧的非连通无向图,其本身是不连通的。但顶点
在有向图中,如果从顶点
-
强连通有向图:如果图中任意两个顶点
$v_i$ 和$v_j$ ,从$v_i$ 到$v_j$ 和从$v_j$ 到$v_i$ 都有路径,则称该图为强连通图。 - 非连通图:如果图中至少存在一对顶点之间不存在任何路径,则该图称为非连通图。
与无向图类似,有向图的一个极大强连通子图称为该图的 强连通分量。
- 强连通子图:如果有向图的子图是连通有向图,则该子图称为原图的强连通子图。
- 强连通分量:有向图中的一个极⼤强连通⼦图,称为该图的强连通分量。
- 极⼤强连通⼦图:有向图中的一个强连通子图,并且不存在包含它的更大的强连通子图。
有时,图不仅需要表示顶点之间是否存在某种关系,还需要表示这一关系的具体细节。这时候我们需要在边上带一些数据信息,这些数据信息被称为 权。在具体应用中,权值可以具有某种具体意义,比如权值可以代表距离、时间以及价格等不同属性。
- 带权图:如果图的每条边都被赋以⼀个权值,这种图称为带权图。
- 网络:带权的连通⽆向图称为⽹络。
根据图中边的稀疏程度,我们可以将图分为「稠密图」和「稀疏图」。这是一个模糊的概念,目前为止还没有给出一个量化的定义。
-
稠密图(Dense Graph):有很多条边或弧(边的条数 e 远小于完全图的边数,如
$e < nlog_2n$ )的图称为稠密图。 - 稀疏图(Sparse Graph):有很少条边或弧(边的条数 e 接近于完全图的边数)的图称为稀疏图。