频道栏目
首页 > 程序开发 > 软件开发 > 其他 > 正文
有向/无向图的基本性质和操作
2016-11-30 09:51:42         来源:michaelbinwang的博客  
收藏   我要投稿

1. LeetCode上很多算法题目都可以抽象成 “图” ,比如搜索类,tree类,迷宫问题,矩阵path问题等。

2. BFS和DFS比较

DFS 和 BFS 的比较
  • BFS 的time, space占用都以 branching factor为底, 到解的距离d为指数增长;空间占用上 Queue 是不会像 DFS 一样只存一条path的,而是从起点出发越扩越大,因此会有空间不够的风险,空间占用为 O(b^d)。
  • 因此BFS时间占用O(b^d), 空间占用O(b^d)
  • DFS 的time占用以 branching factor 为底,树的深度 D 为指数增长;而空间占用上,却只是 O(bD),可视化探索过程中只把每个 Node 的所有子节点存在 Stack 上, 探索完了再 pop 出来接着探,因此储存的节点数为 O(bD)。
  • 因此DFS时间占用O(b^D),空间占用O(bD)

可以看到无论是 BFS 还是 DFS,树的 branching factor 都是对空间与时间复杂度影响最大的参数;除此之外,BFS 中最重要的是到解的距离,而 DFS 看从当前节点的深度。普遍来讲,DFS 空间上会经济一些,当然也要分情况讨论。\

 

拓扑排序,是有向图 graph 搜索中一种特殊的顺序,本质上还是完全可以靠 BFS / DFS 解决。

点击复制链接 与好友分享!回本站首页
相关TAG标签 有向图 无向图
上一篇:indexOf()
下一篇:ASCII码对应表chr
相关文章
图文推荐
文章
推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站