数据结构7-图 完整版.pdf

  1. 1、本文档共70页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
数据结构7-图 完整版

第七章 图 7.1 基本概念和术语 7.2 图的存储结构 7.3 图的遍历 图的应用 7.4 最小代价生成树 7.5 拓扑排序、关键路径 7.6 最短路径 1 图(Graph)是一种较线性表和树更为复杂的数据结构。 q线性表: 数据元素之间构成线性关系,每个数据元素只 有一个直接前驱和一个直接后继。 q树: 数据元素之间具有层次关系,每一层上的元素可能 和下层多个元素相关,但只能和上层中一个元素相关。 q 图:图结构中,结点之间的关系可以是任意的,任意 两个数据元素之间都可能相关。 q图的应用广泛: 电路网络分析、交通运输、管理与线路的铺设 印刷电路板与集成电路的布线、社会网络、WEB链接图 工程进度的安排、课程表的制订、关系数据库的设计 2 7.1 图的定义和术语 一、图的结构定义: q 图是由一个顶点集V 和一个顶点间的关系集合弧集VR (边的集合)构成的数据结构。 可以用二元组定义为:Graph = (V, VR ) 其中,VR ={v,w| v,w ∈V 且P(v,w)} 谓词P(v,w) 定义了弧v,w 的意义或信息。 q顶点:图中的数据元素称为顶点(Vertex), V是顶点的有穷非空集合; VR是两个顶点之间的关系的集合。 q若v,w ∈VR,则v,w 表示从v到w 的一条弧 (Arc). 且称v为弧尾(Tail)或为初始点(Initial node), 称w为弧头(Head)或为终端点(Terminal node). 3 由于 “弧”是有方向的,因此称由顶点集和弧集构成 的图为有向图。弧用尖括号表示。 G = (V , VR ) 1 1 1 A E B C D 其中: V ={A, B, C, D, E} 1 VR ={A,B, A,E,B,C, C,D,D,B,D,A, E,C} 1 4 若v,w ∈VR必有w,v ∈VR,则以(v,w) 代替, 表示两顶点之间有边 (边的顶点对是无序的) 。 此时的图为无向图 (Undigraph)。 例:无向图G2 A B E C D 其中: V2={A, B, C, D, E} VR2={ (A,B), (A,C),(E,C), (E,D),(D,B) } 5 有向图、无向图示例 1 2 A B 3 4 D

文档评论(0)

dajuhyy + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档