Skip to Main Content
算法技术手册(原书第2 版)
book

算法技术手册(原书第2 版)

by George T.Heineman, Gary Pollice, Stanley Selkow
August 2017
Intermediate to advanced content levelIntermediate to advanced
360 pages
8h 35m
Chinese
China Machine Press
Content preview from 算法技术手册(原书第2 版)
127
6
图算法
图是一种用于表示复杂结构化信息的基本结构。图
6-1
中的所有图片都是图的示例。
本章将会讨论图的通用表示法以及相关的一些使用较为频繁的图算法。从本质上来说,
一个图会包含一个元素集合(也称为
顶点
)以及这些元素两两之间的关系(也称为
)。
本章会一直沿用这些术语,虽然在其他描述中也可能会使用术语“结点”和“连接”来
表示相同的概念。此外,这里仅讨论简单图以避免两类情况:顶点有指向自己的边;相
同顶点对之间存在多条边。
图中边所定义的结构使得许多问题都可以描述为:借助图中已有的边,查找从源顶点到
目标顶点的路径。有的时候边会有数值(也称为权值)相关联,还有些时候边带有特定
方向(例如单行道)。
源点最短路径
是这样的一种算法:给定一个顶点
s
,要求计算
出该顶点到图中其他所有顶点的最短路径(边的权值
和)。而
所有点对最短路径
问题
要计算图中所有顶点对
(
u
,
v
)
之间的最短路径。
某些问题则需要更为深入地理解图的结构。例如,无向带权图的最小生成树(
MST
)是
图中边的子集,它满足的条件有:原有的顶点集合在
MST
中依旧相互通;
MST
中边
权值之和最小。本章将展示如何使用
Prim
算法
来高效地解决这个问题。
6.1
G = (
V
,
E
)
由顶点集合
V
以及连接这些顶点对的边集
E
定义
。常见的类图如下:
无向无权图
这种图构建了顶点
(
u
,
v
)
之间不考虑方向的关系。在
采集对称信息时,这种图非常有
用。例如,在社交网络图中,如果
Alice
Bob
的朋友,那么
Bob
也是
Alice
的朋友。
128
6
᪞૰ᅃ๘ ...
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.
Start your free trial

You might also like

机器学习实战:基于Scikit-Learn、Keras 和TensorFlow (原书第2 版)

机器学习实战:基于Scikit-Learn、Keras 和TensorFlow (原书第2 版)

Aurélien Géron
Go语言编程

Go语言编程

威廉·肯尼迪
C++语言导学(原书第2版)

C++语言导学(原书第2版)

本贾尼 斯特劳斯特鲁普

Publisher Resources

ISBN: 9787111562221