算法红皮书第四版 读书笔记 （四） 图

在许多计算机应用中，由相连的结点所表示的模型起到了关键的作用。这些结点之间的连接很自然地会让人们产生一连串的疑问：

沿着这些连接能否从一个结点到达另一个结点？有多少个结点和指定的结点相连？两个结点之间最短的连接是哪一条？

要描述这些问题，我们要使用一种抽象的数学对象，叫做图。

 

 简单的几个实例：

地图

正在计划旅行的人也许想知道“从普罗维登斯到普林斯顿的最短路线”。对最短路径上经历过交通堵塞的旅行者可能会问：“从普罗维登斯到普林斯顿的哪条路线最快？”

要回答这些问题，我们都要处理有关结点（十字路口）之间多条连接（公路）的信息。

网页信息

当我们在浏览网页时，页面上都会包含其他网页的引用（链接）。通过单击链接，我们可以从一个页面跳到另一个页面。整个互联网就是一张图，结点是网页，连接就是超链接。图算法是帮助我们在网络上定位信息的搜索引擎的关键组件。

电路

在一块电路板上，晶体管、电阻、电容等各种元件是精密连接在一起的。我们使用计算机来控制制造电路板的机器并检查电路板的功能是否正常。我们既要检查短路这类简单问题，也要检查这幅电路图中的导线在蚀刻到芯片上时是否会出现交叉等复杂问题。第一类问题的答案仅取决于连接（导线）的属性，而第二个问题则会涉及导线、各种元件以及芯片的物理特性等详细信息。

任务调度

商品的生产过程包含了许多工序以及一些限制条件，这些条件会决定某些任务的先后次序。如何安排才能在满足限制条件的情况下用最少的时间完成这些生产工序呢？

商业交易。零售商和金融机构都会跟踪市场中的买卖信息。在这种情形下，一条连接可以表示现金和商品在买方和卖方之间的转移。在此情况下，理解图的连接结构原理可能有助于增强人们对市场的理解。

无向图（简单连接）、有向图（连接有方向性）、加权图（连接带有权值）和加权有向图（连接既有方向性又带有权值）

 

1、无向图

边（edge）仅仅是两个顶点（vertex）之间的连接

 

相关的图的定义：

路径是由边顺序连接的一系列顶点。简单路径是一条没有重复顶点的路径。

环 是一条至少含有一条边且起点和终点相同的路径。简单环是一条（除了起点和终点必须相同之外）不含有重复顶点和边的环。

路径或者环的长度为其中所包含的边数。

 

 

连通图如果从任意一个顶点都存在一条路径到达另一个任意顶点

 

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

G 有 V-1 条边且不含有环；

G 有 V-1 条边且是连通的；

G 是连通的，但删除任意一条边都会使它不再连通；

G 是无环图，但添加任意一条边都会产生一条环；

G 中的任意一对顶点之间仅存在一条简单路径。

 

2、表示无向图的数据类型

这份 API 含有两个构造函数，有两个方法用来分别返回图中的顶点数和边数，有一个方法用来添加一条边，toString() 方法和 adj() 方法用来允许用例遍历给定顶点的所有相邻顶点（遍历顺序不确定）。

 

在三种图的表示方法中进行选择。

邻接矩阵。我们可以使用一个 V 乘 V 的布尔矩阵。当顶点 v 和顶点 w 之间有相连接的边时，定义 v 行 w 列的元素值为 true，否则为 false。这种表示方法不符合第一个条件—— 含有上百万个顶点的图是很常见的，V2 个布尔值所需的空间是不能满足的。

 

边的数组。我们可以使用一个 Edge 类，含有两个 int 实例变量。这种表示方法很简洁但不满足第二个条件——要实现 adj() 需要检查图中的所有边。

 

邻接表数组。我们可以使用一个以顶点为索引的列表数组，其中的每个元素都是和该顶点相邻的顶点列表，参见图.1.9。这种数据结构能够同时满足典型应用所需的以上两个条件