野生前端的数据结构基础练习(8)——图
2020-05-20

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

习题主要选自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前面。

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

三.小结

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