图的基本概念

定义

  图论中，图是有序对 {\displaystyle G=(V,E)}，其中 {\displaystyle V} 是点集；{\displaystyle E\subseteq \left\{\left\{x,y\right\}:(x,y)\in V^{2},x\neq y\right\}} 是边集，由所有无序顶点对构成（换句话说，边连接了顶点对）。对于一个边 {\displaystyle \left\{x,y\right\}}，顶点 {\displaystyle x,y} 被称作是边的端点，边则被称为连接了此两个点。

E={(u,v)∣u∈V,v∈V}E=\{(u, v) \quad \mid u \in V, v \in V\}

图（graph）是一种非线性数据结构，由顶点（vertex）和边（edge）组成。我们可以将图 抽象地表示为一组顶点 和一组边 的集合。以下示例展示了一个包含 5 个顶点和 7 条边的图。

V={1,2,3,4,5}E={(1,2),(1,3),(1,5),(2,3),(2,4),(2,5),(4,5)}G={V,E}\begin{array}{l}V=\{1,2,3,4,5\}\\E=\{(1,2),(1,3),(1,5),(2,3),(2,4),(2,5),(4,5)\}\\G=\{V,E\}\end{array}

有向图

  若 E 是有向边（弧）的有限集合时，则图G为有向图。弧是顶点的有序对，记为，其中v,w是顶点，v称为弧尾，w称为弧头， 称为顶点v到w的弧，也称v邻接到w，或w邻接自v。

无向图

  若 E 是无向边（简称边）的有限集合时，则图G为无向图。便是顶点的无序对，记为（v，w）或（w，v），因为（v，w）= （w，v），其中v，w是顶点。可以说顶点w和顶点v互为邻接点。边（v，w）依附顶点w，v，或者说边（v，w）和顶点v，w相关联。

简单图

一个图G若满足：

  • 不存在重复边

  • 不存在顶点到自身的边

多重图

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

完全图（简单完全图）

  在无向图中，若任意两个顶点之间都存在边，则称该图为无向完全图。含有n个顶点的无向完全图有 n（n - 1）/ 2 条边。在有向图中，若任意两个顶点之间都存在方向相反的两条弧，则称该图为有向完全图。含有n个顶点的无向完全图有 n（n - 1）条边。

子图

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

连通、连通图和连通分量

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

  注：极大连通子图 是 无向图的连通分量， 极大 即要求该连通子图包含所有的边；极小连通子图是 即要保持图连通又要使得 边数最少 的子图。

强连通图、强连通分量

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

生成树、生成森林

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

顶点的度，入度和出度

  图中每个顶点的度定义为以该顶点为一个端点的边的个数。（树的结点的度 为 子结点个数 ）

  对于无向图，顶点v 的度是指依附于该顶点的边的条数。具有n个顶点，e条边的无向图中，无向图全部顶点的度的和等于边数的两倍。

  对于有向图，顶点的度分为 入度和出度；入度是以顶点为终点的有向边的数目，而出度是以顶点为起点的有向边的数目；顶点的度等于其入度和出度之和。 在具有n个顶点、e条边的有向图中，有向图的全部顶点的入度之和与出度之和相等，并且等于边数。

边的权 和 网

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

图数据结构包含以下常用术语。

  • 邻接（adjacency）：当两顶点之间存在边相连时，称这两顶点“邻接”。在上图中，顶点 1 的邻接顶点为顶点 2、3、5。

  • 路径（path）：从顶点 A 到顶点 B 经过的边构成的序列被称为从 A 到 B 的“路径”。在图 9-4 中，边序列 1-5-2-4 是顶点 1 到顶点 4 的一条路径。

  • 度（degree）：一个顶点拥有的边数。对于有向图，入度（in-degree）表示有多少条边指向该顶点，出度（out-degree）表示有多少条边从该顶点指出。

稠密图，稀疏图

  边数很少的图称为稀疏图，反之称为稠密图。稀疏和稠密是相对的，一般认为图的|E| < |V| log |V| 时，可以将图视为稀疏图。

路径、路径长度和 回路

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

简单路径，简单回路

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

距离

  从顶点U 出发到顶点V的最短路径若存在，则此路径的长度称为 从 U 到 V的距离。若从U 到 V根本不存在路径，则记该距离为无穷。

有向树

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

Previous图Next存储及基本操作

Last updated

Was this helpful?