图的创建和遍历.pdfVIP

第7章图

7.1图的定义和术语

7.2图的存贮结构

7.3图的遍历

7.4生成树和最小生成树

7.5拓扑排序

7.6关键路径

7.7最短路径

教学目的、要求

l1．领会图的类型定义。

l2．熟悉图的各种存储结构及其构造算法，了

解各种存储结构的特点及其选用原则。

l3．熟练掌握图的两种遍历算法。

l4．理解各种图的应用问题的算法。

7.1图的定义和术语

7.1.1图的定义

l图是由顶点集V和顶点间的关系集合E（边的集合）组成的一种数据结构，

可以用二元组定义为：G=（V,E）。

l例如，对于下图所示的无向图G1和有向图G2，它们的数据结构可以描述

为：

lG=(V,E),其中V={a,b,c,d},E={(a,b),(a,c),(a,d),(b,d),(c,d)}。

11111

lG=(V,E)，其中V={1,2,3},E={1,2,1,3,2,3,3,1}。

22222

无向图和有向图

7.1.2图的基本术语

1.有向图和无向图

l在图中，若用箭头标明了边是有方向性的，

则称这样的图为有向图，否则称为无向图

l在无向图中，一条边（x,y）与（y,x）表示的

结果相同，用圆括号表示，在有向图中，一

条边x,y与y,x表示的结果不相同，故用

尖括号表示x,y表示从顶点x发向顶点y的

边，x为始点，y为终点。有向边也称为弧，x

为弧尾，y为弧头，则x,y表示为一条弧，

而y,x表示y为弧尾，x为弧头的另一条弧

2.完全图、稠密图、稀疏图

l具有n个顶点，n(n-1)/2条边的图，称为完全无向图，

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

图。完全无向图和完全有向图都称为完全图

l对于一般无向图，顶点数为n，边数为e，则

0≤e≤n(n-1)/2

l对于一般有向图，顶点数为n，弧数为e，则

0≤e≤n(n-1)

l当一个图接近完全图时，则称它为稠密图，相反，

当一个图中含有较少的边或弧时，则称它为稀疏图

3.度、入度、出度

l在图中，一个顶点依附的边或弧的数目，称为该顶

点的度。在有向图中，一个顶点依附的弧头数目，

称为该顶点的入度。一个顶点依附的弧尾数目，称

为该顶点的出度，某个顶点的入度和出度之和称为

该顶点的度

l另外，若图中有n个顶点，e条边或弧，第i个顶点的

度记为TD(v)，则有：

i

4.子图

l若有两个图G和G，G=(V,E)，G=(V,E)，满

12111222

足如下条件：，，即V为V的子集，

21

E为E的子集，称图G为图G的子图。

2121

图与子图

5.权

l在图的边或弧中给出相关的数，称为权。权可以代

表一个顶点到另一个顶点的距离、耗费等，带权图

一般称为网。

无向带权图与有向带权图

6.连通图和强连通图

l在无向图中，若从顶点i到顶点j有路径，则称顶点i和顶点j是

无向图中

连通的。若任意两个顶点都是连通的，则称此无向图为连通

图，否则称为非连通图。

l在有向图中，若从顶点i到顶点j有路径，则称从顶点i和顶点j

是连通的，若图中任意两个顶点都是连通的，则称此有向图

为强连通图，否则称为非强连通图

7.连通分量和强连通分量

l无向图中，极大的连通子图为该图的连通分量。显