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.
图算法
｜
157
图算法
ܪူՁཁ
ܪူՁཁ
ܪူՁཁ
ܪူՁཁ
ܪူՁཁ
ణጻᄉஜጷ
ణጻᄉణ࠴ၶಝ
图 6-16：Prim 算法示例
6.8.1 输入 / 输出
输入是一个无向图
G
= (
V
,
E
)
。
输出是使用
pred[]
数
组编码的
MST
。
MST
的
根
为
pred[v] =
－
1
的顶点。
6.8.2 解决方案
例
6-8
中
C++
的解决方案依赖于二叉堆实现优先队列，而优先队列是
Prim
算法
的核心
所在。一般来说，使用二叉堆会降低实现的效率，因为在主循环中检查一个顶点是否存
158
｜
第
6
章
在于优先队列中（二叉堆不支持这个操作）很耗时间。但是，算法能够确保每个顶点在
程序处理完后会从优先队列中删除，所以我们只需要维护一个状态数组
inQueue[]
，
这
个数组在顶点从优先队列中取出时会被更新。在另外一个优化实现版本中，我们维护了
一个外部数组
key[]
，用于记录队列中每一个顶点的当前优先级键值，这个值可以让我
们不需要从优先队列中寻找给定的顶点。
Prim
算法
随机选择一个顶点作为起始顶点
s
。在最小顶点
u
从优先队列
PQ
中移除并“加
入”已访问集合
S
时，算法会使用
S
与不断增长的生成树
T
之间的已有边对
PQ
中的元
素重新排序。回忆一下
decreasePriority
操作，它可以将一个元素往
PQ
的前端移动。
例
6-8
：基于二叉堆的 ...
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.