算法 - 图的基础概念

算法：图的基础概念。

图是一组顶点和一组能够将两个顶点相连的边组成的。四种重要的图模型：

• 无向图
  简单连接。无向图是由一组顶点和一组能够将两个顶点相连的边组成的。
• 有向图
  连接有方向性。有向图由一组顶点和一组有方向的边组成，每条有方向的边都连接着有序的一对顶点。
• 加权图无向图
  无向图的每条边，连接带有权值。
• 加权有向图
  有向图的每条边，连接既有方向性又带有权值。

无向图

本章会介绍图的一些基本概念，这些概念并不是无向图特有的，有些是图的公共特性。

特殊的图

有两种简单而特殊的情况：

• 自环
  一条连接一个顶点和其自身的边，即自己连接自己的环图。
• 平行边
  连接同一对顶点的两条边。

通常含有平行边的图称为多重图，没有平行边或者自环的图称为简单图。

术语表

• 相邻的顶点/邻接点：当两个顶点通过一条边相连时，我们称这两个顶点是相邻的；也称这两个点互为邻接点
• 依附：称这条边（该连接）依附于这两个顶点
• 度数：依附一个顶点的边的总数
  数学特性：所有顶点度数的和 = 2 * 所有的边数。
• 子图：一幅图所有边的子集（以及它们所依附的顶点）组成的图
  图论中很多问题需要识别各种类型的子图，特别是能顺序连接一系列顶点的边所组成的子图。
• 路径：由边顺序连接的一系列顶点
• 简单路径：一条没有重复顶点的路径
• 环：一条至少含有一条边且起点和终点相同的路径
• 简单环：除了顶点和终点相同外的，一条不含有重复顶点和边的环
  我们通常研究的路径和环，如果不做特别说明，都是简单路径和简单环。
• 长度：路径或环的长度为其中所包含的边数
• 连通的：当两个顶点之间存在一条连接双方的路径时，称一个顶点和另一个顶点是连通的
• 连通图：如果从任意一个顶点都存在一条路径到达另外任意一个顶点，称这幅图是连通图
• 极大连通子图：一幅非连通的图由若干连通的部分组成，他们都是极大连通子图。也就是说一个非连通的图由几个极大连通子图组成
• 极小连通子图：也就是生成树
• 无环图：一种不包含环的图
  图论中有很多算法，用来找出一幅图中满足一定条件的无环子图。
• 树：一幅无环连通图
  
• 森林：互不相连的数组成的集合称为森林
• 生成树：连通图的子图，包含图中所有顶点的一颗树；也就是极小连通子图
• 生成树森林：所有连通子图的生成树的集合
• 最小生成树：MST: Minimum Spanning Tree ，一幅加权无向图的最小生成树是它的一颗权值（树中所有边的权值之和）最小的生成树
• 最小生成森林：一幅非连通图中，计算所有连通分量的最小生成树，合并在一起则为最小生成森林
• 密度：已经连接的顶点对占所有可能被连接的顶点对的比例
• 稀疏图：被连接的顶点对很少
• 稠密图：只有少部分顶点对之间没有没有边连接
  
• 二分图：能够将所有节点分为两部分的图，其中图的每条边所连接的两个顶点都分别属于不同的部分
  

对于 V 个顶点的图，索引值是以 0 开始，到最后一个 V-1 个顶点：

• v-w
  使用 v-w 的记法来表示连接 v 和 w 的边。
• u-v-w-x
  使用 u-v-w-x 的记法来表示 u 到 x 的一条路径。
• u-v-w-x-u
  使用 u-v-w-x-u 的记法来表示从起点为 u 的简单环，以及环经过的顶点。

树的性质和特点

树的性质：

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

树的特点：当且仅当一幅含有 V 个节点的图 G 满足下列 5 个条件之一时，它就是一颗树：

• G 有 V-1 条边且不含有环
• G 有 V-1 条边且是连通的
• G 是连通的，但删除任一条边都会使它不再连通
• G 是无环图，但添加任一条边都会产生一条环
• G 中的任意一对顶点之间仅存在一条简单路径

图的存储结构

常用存储结构

常用来表示图的数据结构：

• 邻接矩阵 Adjacency Matrix
  使用一个 V*V 的布尔矩阵，当 v 和 w 有相邻边时设置为 true，否则为 false。需要 V*V 个布尔值空间，空间占用太大。因为研究的大部分图为稀疏图，所以邻接矩阵往往对应为稀疏矩阵；无向图是对称矩阵。邻接矩阵有时也用整型数组表示，每个元素可以表示是否连通，或者边上的权值。
• 边的数组 Edge List
  数组中存储 Edge 元素，每个表示一条边。而 Edge 中包含两个整型变量，分别表示这条边的两个顶点。
• 邻接表数组 Adjacency List
  使用一个以顶点为索引的列表数组，其中每个元素都是和该顶点相邻的顶点列表，以一条链表表示经过顶点的路径。

图存储结构更多的示例可以参考：图存储结构图形化

特点

• 邻接矩阵
  由于没有相连的边也占有空间，因此存在浪费空间的问题，而邻接链表则比较合理地利用空间。
• 邻接链表
  比较耗时，牺牲很大的时间来查找，因此比较耗时，而邻接矩阵法相比邻接链表法来说，时间复杂度低。

有向图

在有向图中，边是单向的：每条边所连接的两个顶点都是一个有序堆，它们的领接性是单向的。有向图由一组顶点和一组有方向的边组成，每条有方向的边都连接着有序的一对顶点。

术语表

• 出度：该顶点指出的边的总数
• 入度：指向该顶点的边的总数
• 头：一条有向边的第一个顶点
• 尾：一条有向边的第二个顶点
• 有向路径：由一系列顶点组成，对于其中的每个顶点都存在一条有向边从它指向序列中的下一个顶点
• 有向环：一条至少含有一条边且起点和终点相同的有向路径
• 简单有向环：（除了起点和终点外）一条不含有重复顶点和边的环
• 长度：路径或环中包含的边数
• 可达性：存在顶点 v 到 w 的路径时，则称 v 能到达 w
  约定：每个顶点都能到达自己。有向图中 v 能到达 w，并不意味着 w 能到达 v，需要考虑到方向性。
  
• 有向无环图：DAG: Directed Acyclic Graph 一幅不含有环的有向图
• 强连通的：如果两个顶点 v 和 w 是相互可达的，则称为它们为强连通的
  两个顶点是强连通的当且仅当它们都在一个普通的环中，也就是说强连通只能出现在环中。
• 强连通图：有向图中任意两个顶点都是强连通的
• 强连通分量：强连通性将所有顶点分为一些平等的部分，每个部分都是由相互均为强连通的顶点的最大子集组成的；我们称这些最大子集为强连通分量
  强连通分量是基于顶点而不是边的，可以认为 V 个顶点的有向图，可能含有 1 ~ V 个强连通分量。一个强连通图，只含有一个强连通分量；一个有向无环图则含有 V 个强连通分量。

强连通性的性质

• 自反性
  任意顶点 v 和自己都是强连通的。
• 对称性
  如果 v 和 w 是强连通的，那么 w 和 v 也是强连通的。
• 传递性
  如果 v 和 w 是强连通的且 w 和 x 也是强连通的，那么 v 和 x 也是强连通的。

加权无向图和加权有向图

• 加权图
  加权图是一种为每条边关联一个权值或是成本的图模型。也就是说：图的每条边，连接带有权值。权重可能是距离、时间、费用等，也可以为 0 或者负数。
• 加权无向图
  加权无向图经常需要解决的问题是最小生成树问题。
• 加权有向图
  加权有向图经常需要解决的问题是最短路径等。

最小生成树

• 最小生成树：MST: Minimum Spanning Tree ，一幅加权无向图的最小生成树是它的一颗权值（树中所有边的权值之和）最小的生成树
• 切分：将图的所有顶点分为两个非空且不重复的两个集合；切分就是将图分成二分图
• 横切边：是一条连接两个属于不同集合的顶点的边
• 切分定理：在一幅加权图中，给定任意的切分，它的横切边中的权重最小者必然属于图的最小生成树；是最小生成树算法的基本定理
  

最短路径

• 最短路径：在一幅加权有向图中，从顶点 s 到顶点 t 的最短路径是所有从 s 到 t 的路径中的权重最小者
• 最短路径树：SPT: Shortest Path Tree，给定一幅加权有向图和顶点 s，以 s 为起点的一颗最短路径树是图的一幅子图，它包含 s 和从 s 可达的所有顶点。这颗有向树的根节点为 s，树的每条路径都是有向图中的一条最短路径。
• 边的松弛：放松边 v-w 意味着检查从 s 到 w 的最短路径是否先从 s 到 v，然后再由 v 到 w。如果是，则比较 distTo[w] 和 distTo[v] + e.weight() 的大小。如果 distTo[w] 小，则 v-w 这条边失效了；否则将 distTo[w] 更新为较小值。
  distTo[] 记录顶点到该点的最短路径。

private void relax(DirectedEdge e){
    int v = e.from(), w = e.to();
    if(distTo[w] > distTo[v] + e.weight()){
        distTo[w] = distTo[v] + e.weight();
        edgeTo[w] = e;
    }
}

• 最短路径的最优性条件
  G 是一幅加权有向图，顶点 s 是 G 的起点，distTo[] 是一个由顶点索引的数组，保存的是 G 中路径的长度。对于从 s 可达的所有顶点 v，distTo[v] 的值是从 s 到 v 的某条路径的长度，对于从 s 不可达的所有顶点 v，该值为无穷大。当且仅当对于从 v 到 w 的任意一条边 e，这些值都满足 distTo[w] <= distTo[v] + e.weight() 时（换句话说，不存在有效边时），它们是最短路径长度。

负权重环

负权重环：加权有向图的负权重环是一个总权重（环上所有边的权重之和）为负的有向环。负权重环的所有边不一定都要求为负的，只要权重之和为负就行。
假设：从起点 s 到可达顶点 v 的路径上，有某个顶点在一个负权重环上，这种情况下从 s 到 v 是不存在最短路径的。因为负权重环可以构造权重任意小的路径（在负权重环上循环 n 圈）。
结论：当且仅当加权有向图中，至少存在一条从 s 到 v 的有向路径，并且这条有向路径上的任意顶点都不在任意负权重环中时， s 到 v 的最短路径才是存在的。

图常见问题

• 是否连通
• 有向图可达性
• 是否存在路径
• 最短路径
• 是否存在环
• 判断有向无环图
• 有向图调度问题
• 有向图拓扑排序
• 是否为二分图
• 社交网络间隔度数/影视作品演员间间隔
• 强连通分量
• 最小生成树
• 负权重环检测

这些问题在图的搜索 中，可以看到图的深度搜索和广度搜索能解决大部分问题。比较难解决的，会单独列出文章分析。

小结

图论的缺点是缺乏单独定义，这就是为什么无法在 jdk, std 等库中找到对应源码。

参考文档

• 《算法：第四版》 第 4 章
• 图存储结构图形化
• 算法-图论
• 算法4-图详解