7.1.1图的定义和术语（1）在线视频

同学们大家好，我是云南大学信息学院教师孔兵

这节课我们开始讨论第7章图

和树结构一样，图也是一类重要的非线性结构

图应用的实例很多，比如说在火车联票，交通网

社交网等问题中都会用到图结构进行建模

图的特点是，图中每个数据元素有多个前驱，多个后继

这里我们可以做一个简单的回顾

线性表的特征是一个前驱，一个后继

树的特征是一个前驱，多个后继

图的特征是多个前驱，多个后继

从他们的特征上就可以看出三者之间的关联

树是一种特殊的图，而线性表是一种特殊的树

当然也是一种特殊的图，它们是一种包含的关系

这节我们首先先介绍图的定义和一些常用术语

先看一下图的抽象数据类型定义

仍然包含三个部分

数据对象，数据关系以及基本操作及

数据对象集合V，包含图中的数据元素

我们又把图中的数据元素称为顶点

数据对象也可以称为顶点集

数据关系仍然用有序对的集合VR表示

VR中包含描述前驱和后继的的有序对

有序对表示前驱是顶点v

后继是顶点w，图中把有序对叫做弧

表示从v到w有一条弧

谓词P(v, w)定义弧的意义和信息

图的基本操作有很多

我们介绍4个，FirstAdjVex(G, v)是求第1个邻接点

NextAdjVex(G,v,w)是求下一个邻接点

DFSTraverse(G,v,Visit( ))是对图进行深度优先遍历

BFSTraverse(G,v,Visit( ))对图的广度优先遍历

这是图中较重要的几个操作，具体含义和实现后面讨论

图的操作基本操作还有很多，大家参看我们的教材

首先给出了图的两个示例G1和G2

其中，G1是有向图，G2是无向图

后续讨论中经常用这两个图作为例子

下面，我们介绍图中的一些定义和术语

顶点。图中的数据元素被称为顶点

如G1中有四个数据元素

也就是有四个顶点v1,v2,v3,v4，G2中有五个顶点

V是顶点的有穷非空集合，定义了数据对象

顶点关系的集合是VR

前面讨论过就是描述关系的有序对或者弧的集合

下面结合G1和G2的例子，说明有向图和无向图的定义

有向图：若∈VR，是顶点关系集合中一个有序对

则表示从v到w的一条弧

且称v为弧尾，称w为弧头，此时的图称为有向图

G1中，每个顶点用圆圈加数据元素表

圈v1表示顶点v1，有序对，也就是一条弧

用一个箭头表示，G1中从v1到v2有一个红色箭头

表示弧，还有其它3条弧

也用3个箭头表示，这样的图就是有向图

无向图：若∈VR时必有∈VR

为简化，以无序对（v,w）代替这两个有序对

表示v和w之间的一条边，此时的图称为无向图

对比有向图的定义，无向图实际上是一种特殊有向图

就是图中有序对总是对称出现

有的时候

必有(w,v)

这时不用画2个箭头了

用一条边代替这两个对称的箭头

如G2中，从v1到v2有条红色的边

描述了无序对（v1, v2）。我们应该记住一点

一个无序对，它背后实际是两个对称的有序对

我们后面在讨论图的存储结构的时候

一条边实际上也是作为两条对称的弧来处理的

之所以讨论无向图，是因为在有些问题背景下

数据元素的关系确实是成对出现的

比如说交通图，我们要描述的关系是从A城到B城有道路

可以用有序对表示，一般而言道路是双向通行的

从A城到B城有道路

那么，从B城到A城必有道路

也就是存在则必定对称出现

类似这样的关系，就适应用无向图来进行描述

下面看一下图结构的描述方式

有两种描述方式，一种是前面一直看到的

叫做图示，画出图给大家看

这种方式是给人看的，清晰方便

但是，一般来说计算机无法处理这样的图

一种是形式化描述，通过顶点集

弧集或边集描述图的数据结构

以有向图G1和无向图G2为例

具体看一下。有向图G1被描述为一个二元组

包括两个集合，顶点集V1中是元素v1到v4，4个顶点

关系集合A1中是4个有序对

对应图示中的4个箭头。不管是什么描述方式

描述的都是同一个图，二者是等价的

把图输入到计算机中处理

一般是输入形式化的描述

计算机处理起来比较容易

无向图G2，描述方式类似

只是描述关系的是边集E2

E2中是无序对的集合，表示的是边

下面讨论图的一些特征

设n为图中的顶点数，e为边或者弧的数目

首先看定义无向完全图的概念，n个顶点的无向图中

边的范围是从0到n(n-1)/2。0很好理解

图中只有n个顶点，一条边都没有，各个顶点

可以说是孤立的

n(n-1)/2是n个顶点的无向图的最大的边数

在两个顶点之间最多有一条边的约束下

要达到最大边数，应该是任意两个顶点之间都有一条边

有n(n-1)/2条边的无向图称为无向完全图

说明一下无向完全图边的计算

考虑n个顶点中的一个顶点

例如V1

那么一端在其余顶点的边有n-1条

如图所示，考虑，在图中去掉v1以及和v1相关的n-1条边

同样处理，剩余顶点中再取一个

和它相关有n-2条边

那么，图中总的边数是

(n-1)+(n-2)，一直加到1

这是一个等差数列

直接计算，结果就是n(n-1)/2

有向完全图，n个顶点的有向完全图弧的范围从0到n(n-1)

有n(n-1)条弧的有向图，称为有向完全图

前面说过，一条边背后实际上是两条弧

所以，有向图中最多的弧数

就是把无向图完全图中的一条边看成是两条弧

很容易可以得到有向完全图的弧数是n(n-1)

网也是一种图结构

如果无向图中的边或者有向图中的弧带有数值

我们把所带的数值称为权

这时候，带权的有向图和无向图相应的称为无向网和有向网

图示中，我们给出了一个有向网的实例

每条弧带一个权值

在有的问题中，除了考虑两个顶点之间是否有关系以外

可能还需要考虑这个关系的一个数值特征

比如说交通图中，除了要表示A到B有道路

很多时候，我们还希望知道这条道路的长度

可能就需要给这个关系，带一个权值

稀疏图和稠密图

有很少的边或者弧的图称为必有稀疏图

反之，称为稠密图

稀疏图和稠密图是个相对的概念

并没有明确定义

有一个值可以参考，n个顶点的图中

如果编或者弧的数目e小于nlogn

那么，可以看作是稀疏图

子图的概念

假设有两个图

G=(V,{E})和G`=(V`,{E`})

如果V`∈ V

且E`∈ E，

则称G`为G的子图

示例中我们给出无向图G1和有向图G2的子图示例

G1给出了4个子图，图1是只有1个顶点

没有边的子图，图2，3,4是G1的另外3个子图

G2给出了2个子图

好同学们，这节课呢

我们就讲到这儿，下次课再见