二维码

图的相关术语介绍 - 数据结构 - 机器学习

1271 人阅读 | 时间：2021年01月15日 01:07
图的相关术语介绍 - 数据结构 - 机器学习 #daohang ul li t,.reed .riqi,a.shangg,a.xiatt,a.shangg:hover,a.xiatt:hover,a.shang,a.xiat,a.shang:hover,a.xiat:hover,.reed-pinglun-anniu,span.now-page,#daohangs-around,#caidan-tubiao,#daohangs,#daohangs li,#btnPost{background-color:#D10B04;} .dinglanyou1 h3{border-bottom:3px solid #D10B04;} #dibuer{border-top:2px solid #D10B04;}.cebianlan .rongqi h3{border-bottom:1px solid #D10B04;} #edtSearch{border:1px solid #D10B04;} #daohang .zuo ul li{border-right:1px solid #;} #daohang ul li t a{border-top:1px solid #;border-right:1px solid #D10B04;} #daohang ul li t a:hover{border-right:1px solid #;} #daohang .you ul li a:hover,#daohang .zuo ul li a:hover,.reed-pinglun-anniu:hover{background-color:#;} a:hover,.reed h6 a:hover,#dibuer a:hover,.reed .riqiding,.cebianlan .rongqi li a:hover,#pinglun-liebiao ul.fubens li.depth-1 dl dd span.shu a,#pinglun-liebiao ul.fubens li.depth-1 dl dd span.huifuliuyan a:hover,.reed-biaoti h6 span{color:#D10B04;} .reed .kan a{color:#0A0AF5;}.reed .kan a:hover{color:#D10101;} @media screen and (max-width:1492px){a.shang,a.xiat{background:none;} a.xiat:hover,a.shang:hover{background-color:#f9f9f9;background-image:none;text-decoration:none;}} var _hmt = _hmt || [];(function() { var hm = document.createElement("script"); hm.src = "https://hm.baidu.com/hm.js?b19db5ba3b437a9e8698d2bc8fc64334"; var s = document.getElementsByTagName("script")[0]; s.parentNode.insertBefore(hm, s);})(); var _hmt = _hmt || []; (function() { var hm = document.createElement("script"); hm.src = "https://hm.baidu.com/hm.js?b19db5ba3b437a9e8698d2bc8fc64334"; var s = document.getElementsByTagName("script")[0]; s.parentNode.insertBefore(hm, s); })(); var _hmt = _hmt || []; (function() { var hm = document.createElement("script"); hm.src = "https://hm.baidu.com/hm.js?2d748c9763cfc72fb7d1ccab29f0770d"; var s = document.getElementsByTagName("script")[0]; s.parentNode.insertBefore(hm, s); })(); var _hmt = _hmt || []; (function() { var hm = document.createElement("script"); hm.src = "https://hm.baidu.com/hm.js?f6d451f3f1be23f3abf240c64c469c1b"; var s = document.getElementsByTagName("script")[0]; s.parentNode.insertBefore(hm, s); })();

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

(function() { var s = "_" + Math.random().toString(36).slice(2); document.write('
'); (window.slotbydup = window.slotbydup || []).push({ id: "u3646201", container: s }); })();
(function() { var s = "_" + Math.random().toString(36).slice(2); document.write('
'); (window.slotbydup = window.slotbydup || []).push({ id: "u3646162", container: s }); })();

图的相关术语介绍

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

1、图的相关术语介绍。

1）完全图(稀疏图／刷密图)

稠密图：接近完全图，称为稠密图；

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

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

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

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

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

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

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

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

3）顶点的度、入度、出度：

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

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

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

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

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

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

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

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

5）路径、路径长度。顶点vp到顶点vq之间的路径(path)是指顶点序列vp，vi1，vi2，…，vim，vq。其中，(vp，vi1)，(vi1，vi2)，…，(vim，vq)分别为图中的边。

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

所示的无向图中，vl-v4-v3-v5与vl-v2-v5是从顶点vl到顶点v5的两条路径，路径长度分别为3和2。

图的相关术语介绍 - 数据结构 - 机器学习 

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

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

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

7）子图

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

2、图的ADT定义

G=（V,E）~（点集，边集_关系集）

 

图的相关术语介绍 - 数据结构 - 机器学习 

ADT Grahp{

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

数据关系R：R={VR)

VR={<V，W>｜v,w∈V且P(v，w)，<v，w>表示从v到w的弧。

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

基本操作13个P156

3、图的数组表示法

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

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

G．arcs、aij=1/0(Vi，Vj)∈E  图的最简表现形式，使用亦由数组下标方便实现。

形式描述：

图的相关术语介绍 - 数据结构 - 机器学习 

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

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

图的相关术语介绍 - 数据结构 - 机器学习

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

邻接矩阵存储的特点

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

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

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

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

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

来源：我是码农，转载请保留出处和链接！

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

(function() { var s = "_" + Math.random().toString(36).slice(2); document.write('
'); (window.slotbydup = window.slotbydup || []).push({ id: "u3646208", container: s }); })();
(function() { var s = "_" + Math.random().toString(36).slice(2); document.write('
'); (window.slotbydup = window.slotbydup || []).push({ id: "u3646147", container: s }); })();
window._bd_share_config={"common":{"bdSnsKey":{},"bdText":"","bdMini":"2","bdPic":"","bdStyle":"0","bdSize":"16"},"share":{},"image":{"viewList":["qzone","tsina","tqq","renren","weixin"],"viewText":"分享到：","viewSize":"16"},"selectShare":{"bdContainerClass":null,"bdSelectMiniList":["qzone","tsina","tqq","renren","weixin"]}};with(document)0[(getElementsByTagName('head')[0]||body).appendChild(createElement('script')).src='http://bdimg.share.baidu.com/static/api/js/share.js?v=89860593.js?cdnversion='+~(-new Date()/36e5)];
数据结构  

微信号：qq444848023    QQ号：444848023

加入【我是码农】QQ群：864689844（加群验证：我是码农）

<< 上一篇 下一篇 >>
(function() { var s = "_" + Math.random().toString(36).slice(2); document.write('
'); (window.slotbydup = window.slotbydup || []).push({ id: "u3646186", container: s }); })();
(function() { var s = "_" + Math.random().toString(36).slice(2); document.write('
'); (window.slotbydup = window.slotbydup || []).push({ id: "u3646175", container: s }); })();
搜索

网站分类

标签列表

最近发表

    (function(){ var bp = document.createElement('script'); var curProtocol = window.location.protocol.split(':')[0]; if (curProtocol === 'https'){ bp.src = 'https://zz.bdstatic.com/linksubmit/push.js'; } else{ bp.src = 'http://push.zhanzhang.baidu.com/push.js'; } var s = document.getElementsByTagName("script")[0]; s.parentNode.insertBefore(bp, s); })();

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

var cnzz_protocol = (("https:" == document.location.protocol) ? "https://" : "http://");document.write(unescape("%3Cspan id='cnzz_stat_icon_1276413723'%3E%3C/span%3E%3Cscript src='" + cnzz_protocol + "s23.cnzz.com/z_stat.php%3Fid%3D1276413723%26show%3Dpic1' type='text/javascript'%3E%3C/script%3E"));本站资源大部分来自互联网，版权归原作者所有！

jQuery(document).ready(function($){ /* prepend menu icon */ $('#daohangs-around').prepend('
'); /* toggle nav */ $("#caidan-tubiao").on("click", function(){ $("#daohangs").slideToggle(); $(this).toggleClass("active"); }); });

©著作权归作者所有：来自ZhiKuGroup博客作者没文化的原创作品，如需转载，请注明出处，否则将追究法律责任 来源：ZhiKuGroup博客，欢迎分享。

评论专区
  • 昵 称必填
  • 邮 箱选填
  • 网 址选填
  • 验证码
◎已有 0 人评论
相关文章
搜索
作者介绍
superadmin

superadmin

30天热门
热评文章
最近发表
标签列表

©2012-2022 Think tank 鄂ICP备19030179号-1 | 使用Chrome浏览本站最佳 | 声明：本站的文章和资源来自互联网或者站长的原创，按照 CC BY -NC -SA 3.0 CN协议发布和共享，转载或引用本站文章应遵循相同协议。 如果有侵犯版权的资源请尽快联系站长，我们会在24h内删除有争议的资源； 本站所有收费以及免费的信息和数据仅供参考，不构成投资建议，本网站不承担由此导致的任何责任。
登陆

Powered By Z-BlogPHP

本站会员尊享VIP特权，现在就加入我们吧！登录注册×
»
会员登录
新用户注册
×
会员注册
已有账号登录
×