认识计算机科学的图 - 成就云开发者社区

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

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

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

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

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

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

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

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

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

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

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