图论基础与图存储结构

1、前言

由于后续更新「面试专场」的好几篇文章都涉及到 图 这种数据结构，因此打算先普及一下 图 的相关理论支持，如果后面的相关内容有些点不太容易理解，可以查阅此篇文章。本文不建议一口气阅读完毕，可以先浏览一遍，在后续有需要的时候进行查阅即可。

2、图

图是数据结构中重要内容。相比于线性表与树，图的结构更为复杂。在线性表的存储结构中，数据直接按照前驱后继的线性组织形式排列。在树的结构中，数据节点以层的方式排列，节点与节点之间是一种层次关系。但是，在图的结构中数据之间可以有任意关系，这就使得图的数据结构相对复杂。

2.1 定义

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

例如：图 2.1 所示图

在图 2.1 中，共有 V₀，V₁，V₂，V₃ 这 4 个顶点，4 个顶点之间共有 5 条边。

注：

当线性表没有数据节点时，线性表为空表。
树中没有节点时，树为空树。
但是，在图中不允许没有顶点，但是可以没有边。

2.2 无向边

无向边：若顶点 x 和 y 之间的边没有方向，则称该边为无向边(x,y)，(x,y) 与 (y,x) 意义相同，表示 x 和 y 之间有连接。

图 2.2 所示图中的边均为无向边。

2.3 有向边

有向边：若顶点 x 和 y 之间的边有方向，则称该边为有向边

2.4 无向图

无向图：若图中任意两个顶点之间的边均是无向边，则称该图为无向图。
图2.2所示图为无向图。

2.5 有向图

有向图：若图中任意两个顶点之间的边均是有向边，则称该图为有向图。
图2.3所示的图为有向图。

2.6 顶点与顶点的度

顶点的度：

顶点 V 的度是和 V 相关联的边的数目，记为TD(V)。

图 2.6 所示图中，V₀ 顶点的度为 3 。

入度：

以顶点v为头的边的数目，记为ID(V)。

图2.6所示图中，V₀的入度为1。

出度：

以顶点 v 为尾的边的数目，记为 OD(V)。

图2.6所示图中，V₀的出度为2。

顶点的度 = 入度 + 出度。

即 TD(V) = ID(V) + OD(V)。

2.7 邻接

邻接是两个顶点之间的一种关系。如果图包含（u,v），则称顶点 v 与顶点 u 邻接。在无向图中，这也暗示了顶点 u 也与顶点 v 邻接。换句话说，在无向图中邻接关系是对称的。

2.8 路径

路径：在图中，依次遍历顶点序列之间的边所形成的轨迹。

例如：在图 2.8 中所示图中依次访问顶点 V0 、V3 和 V2 ，则构成一条路径。

3、完全图

完全图：每个顶点都与其他顶点相邻接的图。

无向完全图：在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。（含有n个顶点的无向完全图有(n×(n-1))/2条边）

图 3.1 所示的图为无向完全图。

有向完全图：在有向图中，如果任意两个顶点之间都存在方向互为相反的两条边，则称该图为有向完全图。（含有 n 个顶点的有向完全图有 n×(n-1) 条边）

图3.2所示的图为有向完全图。

4、连通图

在无向图 G 中，如果从顶点 v 到顶点 v' 有路径，则称 v 和 v' 是连通的。 如果对于图中任意两个顶点 vi 、vj ∈E， vi，和vj都是连通的，则称 G 是连通图，否则图为非连通图。

例如：图4.1所示图，图中顶点A、B、C、D是连通的，但是其中任一顶点与顶点E或者顶点F之间没有路径，因此图4.1中所示的图为非连通图。

若添加顶点B与顶点F之间的邻接边，则图变为连通图，如图4.2所示：

5、数组存储

图的数组存储方式也称为邻接矩阵存储。图中的数据信息包括：顶点信息和描述顶点之间关系的边的信息，将这两种信息存储在数组中即为图的数组存储。

首先，创建顶点数组，顶点数组中存储的是图的顶点信息，采用一维数组的方式即可存储所有的顶点信息。存储图中边的信息时，由于边是描述顶点与顶点之间关系的信息，因此需要采用二维数组进行存储。

定义：设图 G 有 n 个顶点，则邻接矩阵是一个n X n的方阵A，定义为：

---