[图](2)图的基本术语

(Graph)是一种较线性表和树更为复杂的数据结构

  • 在线性表中,数据元素之间仅有线性关系,每个数据元素只有一个直接前驱和一个直接后继
  • 在树型结构中,数据元素之间有着明显的层次关系,并且每一层上的数据元素可能和下一层中多个元素(即其孩子结点)相关,但只能和上一层中一个元素(即其双亲结点)相关;
  • 而在图形结构中,结点之间的关系可以是任意的,图中任意两个数据元素之间都可能相关。

由此,图的应用极为广泛,特别是近年来的迅速发展,已渗入到诸如语言学,逻辑学,物理,化学,电讯工程,计算机科学以及数学的其他分支中。

读者在“离散数学”课程中已学习图的理论 [ 可看前言 ]

图的定义和术语

图为一个偶对,由V和E组成的偶对,其中:

图:G=(V,E)
V:顶点(数据元素)的 [有穷非空] 集合;
E:边的 [有穷] 集合;

注意:图里边可以只有 [顶点] 没有 [边]
将G=(V,E)展开就是 Graph=(Vertex,Edge)

顶点:图中的数据元素

image-20210121191655965

  • 无向图:每条边都是无方向的
  • 有向图:每条边都是有方向的

完全图:任意两个点都有一条边相连

image-20210122042555225

无向完全图中:有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)
  • image-20210122043829946

有向树:当有向图中仅一个顶点的入度为0,其余顶点的入度均为1

image-20210122044212671

  • 与之前树不同的是,上一章的树所相连的叫做分支,而分支是没有方向的

路径:接续的边构成的顶点序列

路径长度:路径上边或弧的数目 / 权值之和

回路/环:第一个顶点和最后一个顶点相同的路径

简单路径:除路径起点和终点可以相同外,其余顶点均不相同

简单回路(简单环):除路径起点和终点相同外,其余顶点均不相同的路径image-20210122044738461

连通图(强连通图):在无(有)向图G=(V,{E})中,若对任何两个顶点v、u都存在从v到u的路径,则称G是连通图(强连通图)

image-20210122045344869

权和网:图中边或弧所具有的相关数称为权,表明从一个顶点到另一个顶点的距离或耗费,带权的图称为网

子图:设有两个图G=(V,{E})、G1=(V1,{E1}),若V1⊆V,E1⊆E,则称G1是G的子图

image-20210122050140018

连通分量(强连通分量):无向图G的极大连通子图称为G的连通分量

  • 极大连通子图的意思是:该子图是G连通子图,将G的任何不在该子图中的顶点加入,子图不再连通
  • image-20210122050534562

有向图G的极大连通子图称为G的强连通分量

  • 极大强连通子图意思是:该子图是G的强连通子图,将G的任何不在该子图中的顶点加入,子图不再是强连通的
  • image-20210122050843865

极小连通子图:该子图是G的连通子图,在该子图中删除任何一条边,子图不再连通

生成树:包含无向图G所有顶点的极小连通子图

生成森林:对非连通图,由各个连通分量的生成树的集合

image-20210122051155256

图的抽象类型定义

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个邻接点的下一个邻接点,而最后一个邻接点的下一个邻接点为“空”。

本文链接:

https://nullcode.fun/122.html
1 + 3 =
快来做第一个评论的人吧~