Day 17：图与演算法

有一些演算法是在图(graph)上操作，我们可以先想一些实际的例子，例如：

• 开车的时候，使用导航系统找到最短路径抵达目的地。

• 下棋的程序知道如何利用最少的步数获胜。

• 如果有很多代办事项，其中某些事又必须优先处理，我们可能需要将所有事情合理排序。

应该大部分人都有这些例子的亲身经验，而这些例子都可以想成图的关系。不只在科学中，图在生活中也有非常多应用，所以有许多相关、实用的演算法。当然在看演算法之前，先来大致了解一下图是什麽。

图

图是用来表示物体与物体之间关系的结构。图由两个部分组成：节点(node或vertex)代表物体，边(edge)代表节点之间的关系。例如下方的图就有六个节点和七条边。

另外图中也可能会有环(cycle)，也就是第一个节点和最後一个节点重复的结构，例如图中的1-2-5-1即形成一个环。

看到这里可能会联想到也是由节点组成的树结构。没错，树也是图的一种，它的特性是每个子节点只会有一个父节点，且没有环的结构(树只会往下生长，子节点不会回头指向父节点)。

另外，图可以分为无向图(undirected graph)和有向图(directed graph)。无向图的边没有方向性(如上图)，代表关系是双向的，没有方向上的区别，例如聚会上如果毛豆和大雄握过手，当然也就代表的大雄跟毛豆握过手。

有向图的边则会有箭头来表示出方向性，代表关系是单向的，例如毛豆欠大雄100块，不代表大雄一定欠毛豆钱，所以图上的表达可以是毛豆有单向的箭头指向大雄。

有了这样基本的认识，可以开始解决一些问题。而看到图我们最先想解决的可能是寻找路径的问题。

最短路径问题

假设同样是上方的图，我们想要找到从6到1的最短路径，也就是经过最少段边的路径。因此我们的作法是从6出发，每到一个节点都检查看能不能到达1：

从6可以到1吗？不行，它可以直接到达的地方是4。

从4可以到1吗？不行，它可以直接到达的地方是5和3。

从5可以到1吗？可以，所以最短的路径是6-4-5-1。

虽然感觉好像什麽都没做，只是走向终点，但这样寻找最短路径的方法叫做广度优先搜寻(breadth-first search, BFS)。这种演算法会搜寻一个图中所有节点，它可以用来找出某目标是否在图中，或者节点A到节点B的最短路径，它的作法是：

1. 将一个节点放入伫列(queue)中。

2. 检查伫列的第一个节点是否为目标，

   如果是，结束搜寻；

   如果不是，将所有与它相连的节点放入伫列中。

以刚刚的例子来说，我们一开始将6放进伫列中，6不是目标，所以将相邻的节点4放进伫列中；接着检查4也不是目标，所以将与4相邻的节点5, 3放入伫列，再逐一检查。广度优先搜寻就会如此一直检查下去，直到找到目标或所有节点都被检查完。

这样的步骤可能让人想问，刚刚是因为先检查5，所以找到了最短路径，但如果4之後变成先检查3，就会绕远路吗？

答案是不会，而这也跟步骤中特别强调使用「伫列」有很大关系。

下一回我们会看到伫列的特性，以及它如何确保广度优先搜寻的正确性。