文档介绍：数据结构
(数据结构及其算法)
冯耀霖
Chap 7 图
图的基本概念
图的实现
图的遍历
最短路径问题
最小生成树
§1 图的基本概念
▲图的定义
▲图的相关术语
▲图的基本操作
图(graph)是一种复杂的数据结构,它能够为解决许多具体问题提供非常理想的非数值数学模型。当今,图结构已广泛应用于计算机科学、系统工程、管理工程、通信与网络理论、自动控制、运筹学以至社会科学等诸多学科。
图形结构所研究的图并非生活中所说的图画或地图,而是用一些点和线来表示事物之间关系的某种抽象模型,本质上是数据集合与其上关系的图形表示。
图的定义
图G由两个非空集合V和E组成。V是顶点(Vertex)的有限集,在图中数据元素称为顶点或结点。E是边(Edge)的有限集,边是顶点的无序对或有序对,描述了顶点之间的逻辑关系,每一条边连接V中两个不同的顶点。图的形式化定义为
G=(V, E)
V={vi | vi∈ElemType}
E={(vi , vj) | vi , vj∈V}
或 E={<vi , vj> | vi , vj∈V}
其中,(vi , vj) 为无序对,表示一条无向边,简称边;
<vi , vj>为有序对,表示一条有向边,简称弧。
图的相关术语
1. 无向图
在一个图中,如果连接任意2个顶点的是一条无向边(vi ,vj),即顶点之间的连线是无方向的,则称该图为无向图。。
G1=(V1, E1)
V1={A,B,C,D,E}
E1={(A,B), (A,D), (B,C), (B,E), (C,D), (C,E)}
A
B
C
D
E
A
B
C
D
无向图G1
有向图G2
2. 有向图
在一个图中,如果连接任意2个顶点的是一条弧<vi ,vj>,即顶点之间的连线是有方向的,则称该图为有向图。对于弧<vi ,vj>,vi 被称为起点(弧尾),vj 被称为终点(弧头)。。
G1=(V1, E1)
V1={A,B,C,D}
E1={<A,B>, <A,C>, <C,D>, <D,A>, <D,C>}
3. 混合图
混合图是既含有边又含有弧的图。
4. 无向完全图
在一个无向图中,如果任意2个顶点之间都有一条边连接,则称该图为无向完全图。在一个含有n个顶点的无向完全图中,有n(n-1)/2条边。
5. 有向完全图
在一个有向图中,如果任意2个顶点之间都有方向互为相反的2条弧相连接,则称该图为有向完全图。在一个含有n个顶点的有向完全图中,有n(n-1)条弧。
6. 顶点的度
顶点的度是指依附于某顶点v 的边数,记作deg(v)。在有向图中,顶点的度有入度和出度之分。对于任意顶点v,以v为起点的弧的数目称为v的出度,记为OD(v);而以v为终点的弧的数目称为v的入度,记为ID(v)。
各个顶点的度都相等的无向图也称为正则图,并记作k -正则图,其中k 是各顶点的度。-正则图,也被称为“彼得森图”。
7. 权(weight)
与图的边或弧相关的数值,用于表示从一个顶点到另一个顶点的距离、所需的时间或花费的代价等。