[图](2)图的基本术语
图(Graph)是一种较线性表和树更为复杂的数据结构
- 在线性表中,数据元素之间仅有线性关系,每个数据元素只有一个直接前驱和一个直接后继
- 在树型结构中,数据元素之间有着明显的层次关系,并且每一层上的数据元素可能和下一层中多个元素(即其孩子结点)相关,但只能和上一层中一个元素(即其双亲结点)相关;
- 而在图形结构中,结点之间的关系可以是任意的,图中任意两个数据元素之间都可能相关。
由此,图的应用极为广泛,特别是近年来的迅速发展,已渗入到诸如语言学,逻辑学,物理,化学,电讯工程,计算机科学以及数学的其他分支中。
读者在“离散数学”课程中已学习图的理论 [ 可看前言 ]
图的定义和术语
图为一个偶对,由V和E组成的偶对,其中:
图:G=(V,E)
V:顶点(数据元素)的 [有穷非空] 集合;
E:边的 [有穷] 集合;
注意:图里边可以只有 [顶点] 没有 [边]
将G=(V,E)展开就是 Graph=(Vertex,Edge)
顶点:图中的数据元素
- 无向图:每条边都是无方向的
- 有向图:每条边都是有方向的
完全图:任意两个点都有一条边相连
无向完全图中:有n个顶点,就有n(n-1)/2条边
有向完全图中:n个顶点,就有n(n-1)条边
稀疏图:有很少的边或弧的图(e<nlogn) [为了区分有向图和无向图,在有向图中,边也叫做弧]
网:等同于赋权图,边或弧带权值的图
邻接:有边或者弧相连的两个顶点之间的关系
- 在无向图当中存在(vi,vj),则称vi和vj互为邻接点
- 在有向图当中存在<vi,vj>,则称vi邻接到vj,vj邻接于vi
- 用圆括号则表示偶对不含先后关系,若用尖括号表示的偶对则含有先后关系
关联(依附):边或弧与顶点之间的关系
- 若存在(vi,vj)或<vi,vj>,则称该边/弧关联于vi和vj
顶点的度:与顶点相关联的边的数目,记作TD(v)
- 在有向图中,顶点的度等于该顶点的入度与出度之和
- 顶点v的入度是以v为终点的有向边的条数,记作ID(v)
- 顶点v的出度是以v为起点的有向边的条数,记作OD(v)
有向树:当有向图中仅一个顶点的入度为0,其余顶点的入度均为1
- 与之前树不同的是,上一章的树所相连的叫做分支,而分支是没有方向的
路径:接续的边构成的顶点序列
路径长度:路径上边或弧的数目 / 权值之和
回路/环:第一个顶点和最后一个顶点相同的路径
简单路径:除路径起点和终点可以相同外,其余顶点均不相同
简单回路(简单环):除路径起点和终点相同外,其余顶点均不相同的路径
连通图(强连通图):在无(有)向图G=(V,{E})中,若对任何两个顶点v、u都存在从v到u的路径,则称G是连通图(强连通图)
权和网:图中边或弧所具有的相关数称为权,表明从一个顶点到另一个顶点的距离或耗费,带权的图称为网
子图:设有两个图G=(V,{E})、G1=(V1,{E1}),若V1⊆V,E1⊆E,则称G1是G的子图
连通分量(强连通分量):无向图G的极大连通子图称为G的连通分量
- 极大连通子图的意思是:该子图是G连通子图,将G的任何不在该子图中的顶点加入,子图不再连通
有向图G的极大连通子图称为G的强连通分量
- 极大强连通子图意思是:该子图是G的强连通子图,将G的任何不在该子图中的顶点加入,子图不再是强连通的
极小连通子图:该子图是G的连通子图,在该子图中删除任何一条边,子图不再连通
生成树:包含无向图G所有顶点的极小连通子图
生成森林:对非连通图,由各个连通分量的生成树的集合
图的抽象类型定义
ADT Graph{
数据对象V:V是具有相同特性的数据元素的集合,称为顶点集
数据对象R:
R = {VR};
VR = { <v,w> | v,w∈V,且P(v,w),<v,w>表示从v到w的弧 ,
谓词P(v,w)定义了弧<v,w>的意义或信息 }
基本操作P:
CreateGraph(&G, V, VR)
初始条件:V是图的顶点集, VR是图中弧的集合
操作结果 : 按V和VR的定义构造图G
DestroyGraph(&G)
初始条件:图G存在
操作结果:销毁图G
LocateVex(G, u)
初始条件:图G存在, u和G中顶点有相同特征
操作结果:若G中存在顶点u, 则返回该顶点在图中位置
GetVex(G,x)
初始条件:图G存在,v是G中某个顶点
操作结果:返回v的值
PutVex(G,x)
初始条件:图G存在,v是G中某个顶点
操作结果:对v赋值value
FirstAdjVex(G,v)
初始条件:图G存在,v是G中某个顶点
操作结果:返回v的第一个邻接顶点,若顶点在G中没有邻接顶点,则返回“空”
NextAdjVex(G,v,w)
初始条件:图G存在,v是G中某个顶点,w是v的邻接顶点
操作结果:返回v的(相对于w的)下一个邻接顶点,若w是v的最后一个邻接点,则返回“空”
InsertVex(&G,v)
初始条件:图G存在,v和图中顶点有相同特征
操作结果:在图G中增添新顶点v
DeleteVex(&G,v)
初始条件:图G存在,v是G中某个结点
操作结果:删除G中顶点v及其相关的弧
InsertArc(&G,v,w)
初始条件:图G存在,v和w是G中两个顶点
操作结果:在G中增添弧<v,w>,若G是无向的,则还增添对称弧<w,v>
DeleteArc(&G,v,w)
初始条件:图G存在,v和w是G中两个顶点
操作结果:在G中删除弧<v,w>,若G是无向的,则还删除对称弧<w,v>
DFSTraverse(G,Visit())
初始条件:图G存在,Visit是顶点的应用函数
操作结果:对图进行深度优先遍历,在遍历过程中对每个顶点调用函数Visit一次
且仅一次,一旦Visit()失败,则操作失败
BFSTraverse(G,Visit())
初始条件:图G存在,Visit是顶点的应用函数
操作结果:对图进行广度优先遍历,在遍历过程中对每个顶点调用函数Visit一次
且仅一次,一旦Visit()失败,则操作失败
}ADT Graph
在前述图的基本操作定义中,关于“顶点的位置”和“邻接点的位置“只是一个相对的概念,因为,从图的逻辑结构定义来看,图中的顶点之间不存在全序的关系(即无法将图中顶点排列成一个线性序列),任何一个顶点都可被看成是第一个顶点;另一方面,任一顶点的邻接点之间也不存在次序关系。
但为了操作方便,我们需要将图中顶点按任一的顺序排列起来(这个排列关系和VR无关),由此,所谓“顶点在图中的位置”指的是该顶点在这个人为的随意排列中的位置(或序号),同理,可对某个顶点的所有邻接点进行排队,在这个排队中自然形成了第一个或第k个邻接点,若某个顶点的邻接点的个数大于k,则称第k+1个邻接点为第k个邻接点的下一个邻接点,而最后一个邻接点的下一个邻接点为“空”。