• 目录
• 备份

第四章：图

概述

图可以根据是否有向和带权分成以下四种：

• 无向图 （无向不带权）
• 有向图 （有向不带权）
• 加权无向图（无向带权）
• 加权有向图（有向带权）

无向图

无向图定义： 由一组顶点和一组能够将两个顶点链接在一起的边组成。

特殊情况下的图： 自环，平行边。

自环：就是自己连自己。

平行边：同一对顶点上有多条边相连。例如就像家和学校两个点之间存在很多条路可以选择，而路与路之间称为平行边。

术语

图论方面存在很多相关术语，为了便于后续的叙述，先将这些术语罗列出来。

• 相邻：两个顶点和同一条边相连称为相邻。同时也称这条边依附与这两个顶点。
• 顶点的度：与该顶点相邻边的个数。
• 子图：一幅图中所有边的子集以及这些边相关的点所组成的图。
• 路径：边顺序连接起来的一系列的顶点。
• 简单路径：没有重复顶点的路径。
• 环：至少含有一条起点和终点相同的路径。
• 简单环：不含有重复顶点和边的环。
• 连通图：任意一个顶点都存在一条路径到达另一个任意顶点。
• 极大连通子图：非连通图是由若干个连通子图组成，这些连通子图称为极大连通子图。
• 连通分量：极大连通子图的个数称为非连通图的连通分量。
• 树：无环连通图。
• 森林：互不相连的树组成森林。
• 生成树：连通图的子图，含有图中的所有顶点并且还得是一棵树。
• 生成森林：生成树的集合，也就是该图的所有连通子图的生成树的集合。
• 稀疏图：被连接的顶点对很少，也就是边比较少的图。
• 稠密图：大部分的顶点对都有边相连，只有少部分的顶点对之间没有边连接。
• 二分图：顶点集可以分割成两个互不相交的子集。

无向图的表示方法

构建无向图需要满足两个条件：

1. 为各种类型的图预留足够的空间。
2. 处理时速度要快。

存在三种类型的实现方法：

1. 邻接矩阵，二维的布尔矩阵，两点 i 和 j 之间存在边则对应的下标 [i][j] 中的值为 true ，反之为 false 。当图很大时所需的空间也很大，无法满足第一个条件。

2. 边的数组，实现一个 Edge 类，里面设置两个 int 实例变量。这种实现虽然简洁，但是处理慢，例如如果想要得到某个结点的所有边需要遍历全部结点。

3. 邻接表数组，以顶点为索引，其中的元素都是与该顶点相邻的结点。如图：

邻接表的数据结构

在非稠密图中就是采用邻接表的数据结构实现的。每个顶点相邻顶点的元素都保存在该顶点对应的元素所指向的一张链表中。

对于 V 个顶点 E 条边的图，使用的空间为 $V+E$V+E ， 添加一条边所消耗的时间为常数。处理相邻顶点所需的时间也为常数。

深度优先搜索

搜索的本质是遍历全部节点，深搜就是一种遍历方式，如图：

特点是每次都遍历到尽头，也就是走不下去的时候回头再遍历相关节点。

广度优先搜索

广搜和深搜相反，优先遍历相关节点，相关节点都遍历完成后再去遍历下一层的节点指导走到尽头。

有向图

有向图的边是单向的，每条边连接的两个顶点都是一个有序对。

背景： 有向图的背景有很多，简单枚举几个，有一个大致的体会。

1. 食物链物种的间的不是关系是单向的。
2. 网页之间的超链接，往往有去无回。
3. 程序间的模块间的外部引用。

有向图有顶点和有方向的边组成。

有向图中的度分为出度和入度两种类型。出度为该顶点指出的边的总数，入度则为指向该顶点的边的总数。

在一条有向边中，第一个顶点称为头，而第二个顶点则称为尾。

多点可达性可以应用于垃圾回收，顶点代表对象，而顶点之间的边代表对象与对象之间的引用。

最小生成树

生成树表示含有所有顶点的无环连通子图。

而最小生成树表示在生成树的基础上权重最小。

最小生成树只考虑连通图。

边的权重不一定表示距离。

原理

• 用一条边连接树中任意两个顶点都会产生一个新的环。
• 从树中删去一条边将会得到两颗独立的树。

切分定理：指将图中所有顶点分为两个非空且不重叠的两个集合，横切边是一条连接两个属于不同集合的顶点的边。

从横切边中找权重最小的边，这条边一定属于最小生成树中。依次不断寻找权重最小的横切边即可。

Prim 算法

N 个顶点的图中，需要添加 N-1 条边才能构成最小生成树。

对于 prim 算法而言，每次都需要选择一条最小的横切边加入树中。

prim 算法也分为即使实现和延时实现，前者表示一条边的两个顶点都存在于树中的话将会立即删除，反之则不删除等待后续检查边的有效性。

延时实现的遍历顺序为：

即时实现的遍历顺序为：

二者的区别在于即使实现会将某些边从优先队列中删去，这些边是新加入树中顶点与其他已经在书中顶点的所有边。

Kruskal 算法

这个算法比较简单，将所有的边按照权重排序，依次放入图中即可，注意要将不满足条件的边剔除，例如闭环。

最短路径

最短路径的现实背景就是两地之间存在多条路线，选择一条长度最短的路径。

单点最短路径：在加权有向图中，从顶点 s 到顶点 t 的最短路径是所有从 s 到 t 的路径中的权重最小者。

最短路径性质

最短路径的定义：

• 路径是有向的。
• 权重不等价于距离。
• 并不是所有的顶点都是可达的。
• 负权重会使问题更复杂。
• 最短路径一般都是简单的。（忽略环）
• 最短路径不一定是唯一的。
• 可能存在平行边和自环。

注意，最短路径树和最小生成树不同，最短路径树是指从指定顶点出发，计算该顶点到达其他所有顶点的最短路径所构成的树。

Dijkstra

Dijkstra 用于处理权重非负的最短路径问题。

Prim 算法每次拿到的都是权值最小的横切边，而 Dijkstra 算法选择横切边是按照距离起点最近的距离来选择，也就是哪个顶点距离起点最近就选择该顶点相关的横切边。