野生前端的数据结构基础练习（8）——图

网上的相关教程非常多，基础知识自行搜索即可。

习题主要选自Orelly出版的《数据结构与算法javascript描述》一书。

参考代码可见:https://github.com/dashnowords/blogs/tree/master/Structure/graph

一.图的基本知识

基本概念

图是由边的集合和点的集合组成的。如果图的边有方向（或者说图中的顶点对是有序的）则成为有向图，如果边没有方向则称为无向图。

基本建模

图可以用来对现实中许多事物进行建模。比如交通流量，计算机网络等。

二.基本练习

• 构建一个图的类Graph

• 图的深度优先搜索（DFS）

深度优先搜索从起始顶点开始，直到到达最后一个顶点，然后回溯，直到遍历完随后顶点或查找到指定顶点。深度优先是应用非常广泛的基本搜索思想，往往借助栈结构来实现。demo中的dfs.js直接使用函数的调用栈来追踪搜索，如果数据量很大，则可以通过手动用一个数组来管理栈。

• 图的广度优先搜索（BFS）

广度优先搜索从第一个顶点开始，尝试访问尽可能靠近它的顶点，搜索范围基本是逐层移动的。它的实现依靠数据结构中的队列来实现。

• BFS查找最短路径

图最常见的操作之一就是寻找从一个顶点到另一个顶点的最短路径。书中示例中通过this.edgeTo这个数组来存储顶点的访问路径，例如w节点是通过访问v节点的临近节点时访问的，那么就执行如下赋值this.edgeTo[w] = v，并将节点标记为已访问，由于广度优先搜索逐层扩展的特性，最终通过this.edgeTo迭代显示出的路径必然是搜索中最先实现标记的路径，也就是最短的路径，所以并不需要将每次访问都记录下来最终再比较步长。

• 拓扑排序

拓扑排序用于输出一个有向无环图所有顶点的线性序列，使之满足：

a 每个顶点只出现一次

b 若存在一条从顶点A到B的路径，那么序列中A一定出现在B前面。

书中给出的示例在输出时描述有误，导致输出结果与真实的排序是相反的，在拓扑排序时采用了栈结构，入栈顺序是反的，正确的输出顺序是按照出栈顺序来输出。

三.小结

图论是非常复杂的领域，对数学基础要求较高，感兴趣的读者可以自行继续研究。至此，基本数据结构的课就补完了，希望你也认真做了练习，完成了这个基本的扫盲过程。