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

大史不说话 发表于 2018/11/26 09:27:05 2018/11/26
【摘要】 图是由边的集合和点的集合组成的。如果图的边有方向(或者说图中的顶点对是有序的)则成为有向图,如果边没有方向则称为无向图。

野生前端.jpg

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

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

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

三.小结

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


【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区),文章链接,文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件至:cloudbbs@huaweicloud.com进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容。
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。