注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

SINOBANJO

IN GOD WE TRUST ! ~ ClueeZhuo

 
 
 
 
 

日志

 
 

SINOBANJO - 数据结构之图  

2014-11-03 01:56:20|  分类: 班卓数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

上次总结我们看过树形结构,这次我们了解图结构。在树形结构中,结点间具有层次关系,每一层结点只能和上层中的至多一个结点相关,但可能和下一层中的多个结点相关,而在图结构中,任意两个结点之间都有可能相关,结点之间的邻接关系是任意的。图结构可以描述复杂的数据对象。SINOBANJO - 数据结构之图 - 班卓 - SINOBANJO

 

基本概念

有这么一个问题:在N个城市之间建立通讯网络,使其中的任意两个城市直接有直接或者间接的通讯线路,假设已知每两个城市之间的通讯线路造价,要求求出一个造价最低的通讯网络。当N很大时,这个问题十分复杂。

对于上述问题我们可以这样来描述通讯网络,用一个原点来代表一个城市,用原点之间的连线来代表对应两个城市之间的通讯线路,在线路上添加数值代表线路造价。这种描述的形成就是图结构。其中原点城市称为顶点,连线通讯线路称为边,连线附带的数值称为权。

图的定义和术语

G由两个集合VE组成,,记为G=(V,E),其中V顶点的又穷非空集合;E是边的集合,边是V中顶点的偶对。若顶点的偶对是有序的则称此图为有向图,有序偶对用尖括号<>括起来;若顶点的偶对是无序的,则称此图为无向图,无序偶对用圆括号()括起来。例如:偶对<v,w>表示有向图中从顶点v到顶点w有一条边,即为v,wV,<v,w>E。偶对(v,w)表示无向图中顶点v和顶点w间有一条边即为 v,wV,(v,w)E

有向图的边称为弧。v,w∈V,<v,w>E,,则有序偶对<v,w>表示有向图G中从vw的一条弧,v称为弧尾或者始点,w称为弧头或者终点。特别注意的是在无向图中(v,w)(w,v)是同一条边,但是在有向图中<v,w><w,v>是不同的两条弧。

在无向图中,若顶点vw间有边(v,w),vw互为邻接点,称为(v,w)与顶点vw相关联。在有向图中,若顶点vw之间有弧<v,w>,则vw邻接,称弧<v,w>与顶点vw相关联。

任何两点之间都有边的无向图称为无向完全图。一个具有n个顶点的无向完全图的边数为C?n=n(n-1)/2。任意两点之间都有弧的有向图称为有向完全图。一个具有n个顶点的有向完全图的弧数为P?n=n(n-1)

图的边附带数值,这个数值叫权。权在实际问题应用中可以表示从一个顶点到另一个顶点的距离、代价、或者耗费等。每条边都带权的图称为带权图。

无向图中顶点v是与该顶点相关联的边的数目记为D(v)。如果G是个有向图,则把以顶点v为终点的弧的数目称为v入度,记为ID(v)。把以顶点v为始点的弧的数目称为v出度,记为OD(v)有向图中的顶点v的度为入度与出度的和,即D(v)=ID(v)+OD(v)

G=(V,E)是一个图,若E′是E的子集,V′是V的子集,并且E′中的边仅与V′中顶点关联,则G=(V,E)称为图G子图

在无向图G=(V,E)中从顶点v到顶点v′的路径是一个顶点序列:V, Vi1, Vi2, …, Vim, V′ ,其中(v, Vi1), (Vi1, Vi2), …, (Vim, V)为图G中的边。若G是有向图,则要求这个顶点序列满足:<v,Vi1>, <Vi1, Vi2>, …, <Vim, V>为图G中的弧。路径上边(或弧)的数目称为路径长度

序列中顶点不重复出现的路径称为简单路径。第一个顶点和最后一个顶点相同的路径称为回路。除了第一个顶点和最后一个顶点外,其余顶点不重复的回路,称为简单回路简单环

在无向图中,如果从顶点v到顶点v′有路径,则称vv′是连通的。如果图中的任意两个顶点vivj都是连通的,则称G连通图。无向图中极大连通子图称为连通分量

在有向图中,如果图中任意一对顶点vivj(ij)都是顶点vi到顶点vj的路径,也是从vjvi的路径,即两个顶点间双向连通,那么称为该有向图是强连接图。有向图的极大连通子图称为强连通分量

一个连通图的生成树,是含有该连通图的全部顶点的一个极小连通子图。若连通图G的顶点个数为n,则G的生成树的边数为n-1。如果G的一个子图G ′的边数大于n-1,则G′中一定有环。相反,如果G′的边数小于n-1,则G′一定不连通。在非连通图中,由每个连通分量都可得到一个极小连通子图,即一棵生成树。那么这些连通分子量的生成树就组成一个非连通图的生成深林

这次就简单总结到此,关于图的运算、存储、遍历还有待了解。感谢阅读。

  评论这张
 
阅读(38)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017