图论

图论

“图论”这个名字来自数学，听上去有点唬人，背后其实是一整套与现实紧密相连的工具。这些工具在计算机科学中特别有用，因为它们能解决大量问题。

图可以用来描述一组相互作用的实体（称为顶点或节点）。这些相互作用用顶点之间的连线表示，这些连线称为边。

图的顶点和边都可以带有属性（在文献中有时也叫作标签）。

边可以是有方向的，这时它们被称为弧或箭头。

好吧……这些术语说得头头是道，可图具体有什么用呢？用处多着呢！一个很经典的例子就是道路网络图：顶点是路口，边是道路。用边？也不完全对：这里用弧来表示道路更合适，因为有些路是单行道，只能朝一个方向走。我们还可以给弧加上标签，标明道路的限速和长度。

用图来表示道路网络的好处是，之后可以直接拿大量“现成的”算法来解决这个道路网络中可能遇到的问题。比如说，我们多半会想计算最短路径。这时候，答案来了！我们可以实现一个 Dijkstra 算法 :)

那在 Leek Wars 里，图能派上什么用场呢？首先，可以用图来表示地图。这样一来，如果你用比内置算法更高效的算法，在需要 getPath 的时候就能省下一些操作数。其次，用图结构也能更轻松地处理飞跃 和传送 这类芯片。

在知名的最短路径算法中，除了前面提到的大名鼎鼎的 Dijkstra 算法，还有其他算法，比如 A* 算法。

查找可达格子 时，也可以借助广度优先搜索算法（即 BFS，英文 Breadth-First Search 的缩写）。

在更进阶的用法中，有些饲养员会使用一种特殊的图结构，称为树)，用来生成所有可能的行动序列。