August 2017
Intermediate to advanced
360 pages
8h 35m
Chinese
Content preview from 算法技术手册（原书第2 版）
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.
图算法
｜
159
图算法
6.8.3 算法分析
在初始化阶段，
Prim
算法
将每个顶点插入优先队列（二叉堆实现）中，总的时间费用
为
O
(
V
log
V
)
。然后
decreaseKey
操作将需要
O
(log
q
)
的时间，其中
q
是优先队列中顶
点的数目，并且
q
总是小于
V
。这个操作最多需要执行
2*
E
次，因为每一个顶点都只会
从优先队列中被删除，而图中的每一条边又会刚好被访问两次。因此总性能是
O
((
V
+
2*
E
)*log
V
)
，也就是
O
((
V
+
E
)*log
V
)
。
6.8.4 衍生算法
Kruskal
算法
可以代替
Prim
算法
。它使用“不相交集”数据结构来构建最小生成树，
按照边的权值大小依序处理所有的边，以最小权值的边开始，以最大权值的边结束。
Kruskal
算法
可以实现为
O
(
E
log
V
)
。算法的细节可以在相关资料（
Cormen
等，
2009
）
中找到。
6.9 关于图的最后一些想法
本章中，我们看到了算法对于稠密图和稀疏图有着不同的表现行为。现在，我们将进一
步深究这个概念，分析找出稀疏图和稠密图的平衡点，了解它们对于存储需求的影响。
6.9.1 存储问题
当使用二维邻接矩阵来表示元素集合中
n
个元素的潜在关系时，该矩阵需要
n
2
个元素的
存储空间，然而有时元素之间的关系集合会非常小，在这种情况下，也就是在所谓的稀
疏图上，由于计算机内存的限制，有可能无法存储超过数千个顶点的图。另外，如果在
大规模矩阵中存储稀疏图，那么遍历矩阵来寻找特定边的操作的费用也会变得很大。不
仅如此，这种存储表示法也限制了许多优秀算法潜在的性能改进。 ...
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Read now
Unlock full access
More than 5,000 organizations count on O’Reilly
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.Julian F.
I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.Addison B.
I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.Amir M.
I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.