认识计算机科学的图

我们在学习数据结构的过程中总是避不开堆。而堆是一种图的树形结构。我们可以通过本篇文章进行学习和了解什么是图，图和树的关系，图的便利性，以及图的典型搜索算法--广度优先搜索。

什么是图

与我们印象中的饼状图不同的是，计算机科学中的图常表现为以下的形式：

图1 计算机科学的图

简而言之，由顶点和每对顶点之间的边构成的图形就是图。图可以表示各种关系，没有闭环的图我们称为树。

加权图

在由顶点和边构成的图形中我们还可以加入权重，构成加权图，如下图所示：

图2 加权图

由权值的边可以表示顶点之间的“连接程度”。关于权重的理解，在百度百科中有相关的解释：“权”的古代含义为秤砣，就是秤上可以滑动以观察质量的那个铁疙瘩。《孟子·梁惠王上》曰:“权，然后知轻重。”。我们在此可以理解为某一因素对某一事务的重要程度，倾向于贡献度或重要性。

根据图的内容不同，连接程度的表达的意思也不同。

有向图

我们给图中加入单向箭头时，这张图就变为了有向图。有向图也可以加入权重。

图3 加权有向图

图带来的便利

假设我们需要知道图2的顶点B到顶点D权重之和最小的那条路，那么就可以通过图表示的关系来找到最合适的算法。

图的最短路径搜索

我们将学习图的搜索算法，比如解决最短路径的算法：广度优先搜索和深度优先搜索。比如我们将起点在顶点A，我们需要寻找并不知道在什么位置的顶点G。下面我们将分别使用广度优先搜索和深度优先搜索来进行顶点G的查找，从中感受不同算法的魅力。

图的最短路径搜索

广度优先搜索

1. 从A直达的B、C、D三个顶点选为下一步执行的起始点。优先选择最早成为下一步执行点的那个顶点。假设B、C、D同时被选为下一步的候选起始点，那么可以随机选择一个。我们可以先选择B为下一步的起始点。
2. 顶点B的下一步执行的候选起始点变为E、F、C、D
3. 候补顶点是根据“先入先出”的原则来管理。那么C和D成为了下一步的候选起始点，假设C、D同时被选为下一步的候选起始点，那么可以随机选择一个。我们可以先选择C为下一步的起始点。
4. 顶点C的下一步执行的候选起始点变为E、F、H、D
5. 我们可以选择D为下一步的候选起始点。
6. 顶点D的下一步执行的候选起始点变为E、F、H、I、J 以此类推最终找到顶点G。

深度优先搜索

1. 从A直达的B、C、D三个顶点选为下一步执行的起始点。优先选择最早成为下一步执行点的那个顶点。假设B、C、D同时被选为下一步的候选起始点，那么可以随机选择一个。我们可以先选择B为下一步的起始点。
2. 顶点B的下一步执行的候选起始点变为E、F、C、D
3. 候补顶点是根据“先入后出”的原则来管理。那么E和F成为了下一步的候选起始点，假设E、F同时被选为下一步的候选起始点，那么可以随机选择一个。我们可以先选择E为下一步的起始点。
4. 顶点E的下一步执行的候选起始点变为K、F、C、D
5. 我们可以选择K为下一步的候选起始点。
6. 顶点K的下一步执行的候选起始点变为F、C、D 以此类推找到顶点G。

参考

• 《我的第一本算法书》宫崎修一 石田保辉