学点高端技术：数据结构之图详解

上一篇 / 下一篇  2022-03-28 17:41:07 / 个人分类：大数据

查看( 230 ) / 评论( 0 ) / 评分( 0 / 0 )
图的抽象数据类型
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);
……
} ADT Graph
​
添加图片注释，不超过 140 字（可选）
　　顶点（Vertex）：图G中的数据元素称为顶点。
　　有向图：若图G中的每条边都是有方向的，则称图G是有向图。
　　弧（Arc）：在有向图中，一条有向边是由两个顶点组成的有序对，有序对通常用尖括号表示，有向边又称为弧。
　　弧尾（Tail）：弧的始点称为弧尾（起始点）。
　　弧头（Head）：弧的终点称为弧头（终端点）。
　　无向图：若图G中的每条边都是没有方向的，则称G为无向图。无向图中的边均是顶点的无序对，无序对通常用圆括号表示。
　　我们约定：
　　· 一条边或弧中涉及的两个顶点必须不相同，即：若
​
添加图片注释，不超过 140 字（可选）
或
​
添加图片注释，不超过 140 字（可选）
是G中的一条边或弧，则要求
​
添加图片注释，不超过 140 字（可选）

　　· 一对顶点间不能有同方向的两条有向边
　　· 一对顶点间不能有两条无向边
　　设n为图中顶点的数目，e为边或弧的数目：
　　完全图：有
​
添加图片注释，不超过 140 字（可选）
条边的无向图。
　　有向完全图：有n(n-1)条边弧的有向图。
　　稀疏图：有很少条边或弧的图（如e<nlogn）。
　　稠密图：有很多条边或弧的图。
​
添加图片注释，不超过 140 字（可选）
　　子图（Subgraph）：若两个图G=(V,{E})和G’=(V’,{E’})，如果
​
添加图片注释，不超过 140 字（可选）
且
​
添加图片注释，不超过 140 字（可选）
，则称G’为G的子图。
​
添加图片注释，不超过 140 字（可选）
　　入度：在有向图中，把以顶点v为终点的弧的数目称为顶点v的入度，记为
​
添加图片注释，不超过 140 字（可选）
。
　　出度：在有向图中，把以顶点v为始点的弧的数目称为顶点v的出度，记为
​
添加图片注释，不超过 140 字（可选）
。
　　度：在无向图中，一个顶点的度就是与该顶点相关联的边的数目。在有向图中，顶点v的度等于顶点的出度和入度之和。顶点的度记为

收藏 举报

TAG: 软件测试

 

评分：0

我来说两句