当前位置: 首页 > news >正文

关于栈和队列随想

1 在算法中栈和队列的地位

在算法中,栈和队列就是一个缓存,缓存那些对自己还有用的元素,还不用扔掉的元素。

比如对图的深度优先搜索,搜到某一层时,还只是访问了该元素的一个邻接节点时,是不能随便扔出栈的,因为可能它还有其它的邻接节点,首先它自己肯定是已经被访问了的,但是如果把它扔了,它的其它邻接节点也就被扔了,所以,只有当它的所有的邻接节点也被访问了的时候才可以把它扔掉。

 一般情况下,图的深度优先遍历用的是递归,boost graph library中用的就是递归来实现的。不要对递归有偏见,不要对递归的函数调用有偏见,

2 对图进行遍历的时候,如何标记栈中的元素已经被访问的邻接节点和未被访问的邻接节点

 图中的每个节点都是有一个label的,并且该label是唯一的,所以,可以弄一个hash表,访问过了的就是true,没有访问的就是false。缺点就是如果用邻接表表示图的话,每次都要遍历一下每个表。

3 邻接表盒邻接矩阵比较

当边比较多的时候,比如满边的时候,用邻接矩阵比较好,因为空间占用上二者一样,但是,邻接矩阵找起邻接关系来更快。

当边比较少的时候,比如没有边的时候,用邻接表会比较好,因为邻接矩阵会有很多空的地方,浪费空间,而邻接表就非常节省空间了。

转载于:https://www.cnblogs.com/hustdc/p/7912019.html

相关文章:

  • HBase Client API 简析
  • 学倦乱语
  • MongoDB分布式存储的MapReduce并行查询
  • CentOS6.x安装nginx1.12.1
  • 【JDK1.8】JDK1.8集合源码阅读——TreeMap(二)
  • jstat 监控调整GC很好用
  • $(document).ready(function(){}), $().ready(function(){})和$(function(){})三者区别
  • RegexOptions.Compiled真的是性能杀手么?
  • Android 从服务器获取时间戳转换为年月日
  • java uuid第一次性能
  • 精度计算-大数乘小数
  • C#~异步编程再续~await与async引起的w3wp.exe崩溃-问题友好的解决
  • Android 中文API (68) —— BluetoothClass.Service
  • 一加3T解锁OEM、刷入TWRP、第三方ROM以及ROOT
  • Binlog中最容易踩到的坑
  • 分享一款快速APP功能测试工具
  • [译]CSS 居中(Center)方法大合集
  • 《Javascript数据结构和算法》笔记-「字典和散列表」
  • CODING 缺陷管理功能正式开始公测
  • Django 博客开发教程 8 - 博客文章详情页
  • Docker: 容器互访的三种方式
  • download使用浅析
  • HTML中设置input等文本框为不可操作
  • JavaScript 无符号位移运算符 三个大于号 的使用方法
  • Js基础——数据类型之Null和Undefined
  • nginx 配置多 域名 + 多 https
  • opencv python Meanshift 和 Camshift
  • PAT A1092
  • ReactNative开发常用的三方模块
  • React系列之 Redux 架构模式
  • SpiderData 2019年2月25日 DApp数据排行榜
  • Vue 动态创建 component
  • 翻译--Thinking in React
  • 开源SQL-on-Hadoop系统一览
  • 前端相关框架总和
  • 入手阿里云新服务器的部署NODE
  • 吐槽Javascript系列二:数组中的splice和slice方法
  • 新版博客前端前瞻
  • ​​​​​​​GitLab 之 GitLab-Runner 安装,配置与问题汇总
  • ​Distil-Whisper:比Whisper快6倍,体积小50%的语音识别模型
  • ​HTTP与HTTPS:网络通信的安全卫士
  • #Linux(Source Insight安装及工程建立)
  • #ubuntu# #git# repository git config --global --add safe.directory
  • $refs 、$nextTic、动态组件、name的使用
  • (Demo分享)利用原生JavaScript-随机数-实现做一个烟花案例
  • (第二周)效能测试
  • (顶刊)一个基于分类代理模型的超多目标优化算法
  • (附源码)springboot 基于HTML5的个人网页的网站设计与实现 毕业设计 031623
  • (十五)devops持续集成开发——jenkins流水线构建策略配置及触发器的使用
  • (转)母版页和相对路径
  • (转)详解PHP处理密码的几种方式
  • (转)原始图像数据和PDF中的图像数据
  • *Django中的Ajax 纯js的书写样式1
  • .\OBJ\test1.axf: Error: L6230W: Ignoring --entry command. Cannot find argumen 'Reset_Handler'
  • .NET CF命令行调试器MDbg入门(四) Attaching to Processes