程序员学数据结构

第11章　图：互相连接的对象

图（graph）是我们学习的最后一种数据结构。这种数据结构由一组不具备特定结构性关系的对象组成，而数据集的每个对象可拥有指向一个或多个其他对象的连接。图中的对象通常被称为节点、顶点或是点。对象之间的连接通常被称为边、线或弧。这些连接可以为简易的引用，也可以是含有值的对象。更正规地说，图为一对集合(N,E)，其中N是数据集中的节点集合，而E是数据集中边的集合。

社交媒体数据库中个人之间的可视化关系就是图的一种典型应用。该数据库中的每个人都为图中的一个节点，而此人与他朋友圈里其他人之间的关系为图中的边。可以预想到的是，在这样一个朋友圈中，人与人之间的关系会非常错综复杂，并且他们之间会有许多相同的朋友或同事。当使用树或堆来试图理清这些集合时，它们的结构会迅速崩溃，而图这种数据结构正是为了解决这类问题而设计的，它可以很好地满足用户需求。

本章将涵盖以下主要内容：

• 图数据结构的定义；
• 概念图示；
• 基本操作；
• 图的实现。

11.1　概念图示

通过图示的方法读者能更容易地掌握图数据结构的概念。研究图11-1。

图11-1

图11-1展示了一个基本的图结构，该图由11个节点和12条边组成。集合N和集合E可以表示为：

N={2,3,4,5,9,11,19,38,52,77,97}

E={2:38,2:77,2:97,3:19,4:77,5:2,5:19,11:2,11:4,11:5,11:52,77:9}

注意，这个示例的节点之间只存在单向边。这完全可行，但若允许使用双向边的话，图的功能会更加强大，如图11-2所示。 ...