当前位置:首页 » 数据结构精品文章 » 正文

图的相关术语介绍

901 人参与  2018年09月03日 22:42  分类 : 数据结构精品文章  评论

1、图的相关术语介绍。

1)完全图(稀疏图/刷密图)

稠密图:接近完全图,称为稠密图;

稀疏图:称边数很少的图为稀疏图。

2)顶点、边、弧、弧头、弧尾

图中数据元素VI称为项点(vertex l

P(vivj)表示在项点vi和顶点vj之间有一条直接连线。

如果是在无向图中,则称这条连线为边;

如果是在有向图中,一般称这条连线为弧。

边用顶点的无序偶对(vivj)来表示,称顶点vi和顶点vj互为邻接点,边(vivj)依附于项点vi与顶点vj

弧用顶点的有序偶对(vivj)来表示,有序偶对的第1个结点vi被称为始点(或弧尾),在图中就是不带箭头的一端;有序偶对的第2个结点Vj称为终点或弧头),在图中鹉是带箭头的一端。

3)顶点的度、入度、出度:

顶点的度(degree)是指依附于某项点V的边数,通常记为TD (v)

在有向图中,要区别顶点的入度与出度的概念。

项点v的入度是指以项点为终点的弧的数目,记为lD(v)

顶点v出度是指以项点v为始点的弧的数目,记为OD(v)

4)边的权、网图。与边有关的数据信息称为权(weight)

在实际应用中,权值可以有某种含义。比如,在一个反映城市交通线路的图中,边上的数值可以表示该条线路的长度或者等级;

对于一个电子线路图,边上的权值可以表示两个端点之间的电阻、电流或电压值;对于反映工程进度的图而言,边上的权值可以表示从前一个工程到后一个工程所需要的时间等等。边上带权的图称为网图或网络( network)

如果边是有方向的带权图,则就是一个有向网图。

5)路径、路径长度。顶点vp到顶点vq之间的路径(path)是指顶点序列vpvi1vi2…,vimvq。其中,(vpvi1)(vi1vi2)…,(vimvq)分别为图中的边。

路径上边的数目称为路径长度。

所示的无向图中,vl-v4-v3-v5vl-v2-v5是从顶点vl到顶点v5的两条路径,路径长度分别为32

image.png 

6)回路、简单路径、简单回路。

vi的路径为回路或者环( cycle)。序列中顶点不重复出现的路径称为简单路径。

除第一个顶点与最后一个顶点之外,其他顶点不重复出现的回路称为简单回路,或者简单环。

7)子图

对于图G= (VE)G’=(V’E,),若存在V’V的子集,E’E的子集,则称图G’G的一个子图。

2、图的ADT定义

G=V,E~(点集,边集_关系集)

 

image.png 

ADT Grahp{

数据对象VV是具有相同特性的数据元素的集合,称为顶点集。

数据关系RR={VR)

VR={<VW>v,wVP(vw)<vw>表示从vw的弧。

谓词P(VW)定义了弧<VW>的意义或信息}

基本操作13P156

3、图的数组表示法

用两个数组分别存放数据和关系。

有关系则有边信息,无关系则无边信息。

Garcsaij=1/0(ViVj)E  图的最简表现形式,使用亦由数组下标方便实现。

形式描述:

image.png 

4、邻接矩阵存储的定义及特点?

所谓邻接矩阵(Adjacency Matrix)的存储结构,就是用一维数组存储图中顶点的信息,用矩阵表示图中各顶点之间的邻接关系。假设图G=(VE)n个确定的顶点,即V={VoV1…Vn-1},则表示G中各顶点相邻关系为一个n×n的矩阵,矩阵的元素为:

image.png

其中,Wij表示边(ViVj)<ViVj>上的权值:表示一个计算机允许的、大于所有边上权值的数。

邻接矩阵存储的特点

从图的邻接矩阵存储方法容易看出这种表示具有以下特点:

无向图的邻接矩阵一定是一个对称矩阵。因此,在具体存放邻接矩阵时只需存放上(或下)三角矩阵的元素即可。

对于无向图,邻接矩阵的第i(或第i)非零元素(或非元素)的个数正好是第i个顶点的度TD(Vi)

对于有向图,邻接矩阵的第i(或第i)非零元素(或非元素)的个数正好是第i个顶点的出度OD(Vi)(或入度ID(Vi))

用邻接矩阵方法存储图,很容易确定图中任意两个顶点之问是否有边相连;但是,要确定图中有多少条边,则必须按行、按列对每个元素进行检测,所花费的时问代价很大。这是用邻接矩阵存储图的局限性。

来源:我是码农,转载请保留出处和链接!

本文链接:http://www.54manong.com/?id=200

数据结构  

微信号:qq444848023    QQ号:444848023

加入【我是码农】QQ群:864689844(加群验证:我是码农)

<< 上一篇 下一篇 >>

网站分类

标签列表

最近发表

全站首页 | 数据结构 | 区块链| 大数据 | 机器学习 | 物联网和云计算 | 面试笔试

本站资源大部分来自互联网,版权归原作者所有!