- 1、本文档共107页,可阅读全部内容。
- 2、原创力文档(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
第7章图
7.1图的定义和术语
7.2图的存贮结构
7.3图的遍历
7.4生成树和最小生成树
7.5拓扑排序
7.6关键路径
7.7最短路径
教学目的、要求
l1.领会图的类型定义。
l2.熟悉图的各种存储结构及其构造算法,了
解各种存储结构的特点及其选用原则。
l3.熟练掌握图的两种遍历算法。
l4.理解各种图的应用问题的算法。
7.1图的定义和术语
7.1.1图的定义
l图是由顶点集V和顶点间的关系集合E(边的集合)组成的一种数据结构,
可以用二元组定义为:G=(V,E)。
l例如,对于下图所示的无向图G1和有向图G2,它们的数据结构可以描述
为:
lG=(V,E),其中V={a,b,c,d},E={(a,b),(a,c),(a,d),(b,d),(c,d)}。
11111
lG=(V,E),其中V={1,2,3},E={1,2,1,3,2,3,3,1}。
22222
无向图和有向图
7.1.2图的基本术语
1.有向图和无向图
l在图中,若用箭头标明了边是有方向性的,
则称这样的图为有向图,否则称为无向图
l在无向图中,一条边(x,y)与(y,x)表示的
结果相同,用圆括号表示,在有向图中,一
条边x,y与y,x表示的结果不相同,故用
尖括号表示x,y表示从顶点x发向顶点y的
边,x为始点,y为终点。有向边也称为弧,x
为弧尾,y为弧头,则x,y表示为一条弧,
而y,x表示y为弧尾,x为弧头的另一条弧
2.完全图、稠密图、稀疏图
l具有n个顶点,n(n-1)/2条边的图,称为完全无向图,
具有n个顶点,n(n-1)条弧的有向图,称为完全有向
图。完全无向图和完全有向图都称为完全图
l对于一般无向图,顶点数为n,边数为e,则
0≤e≤n(n-1)/2
l对于一般有向图,顶点数为n,弧数为e,则
0≤e≤n(n-1)
l当一个图接近完全图时,则称它为稠密图,相反,
当一个图中含有较少的边或弧时,则称它为稀疏图
3.度、入度、出度
l在图中,一个顶点依附的边或弧的数目,称为该顶
点的度。在有向图中,一个顶点依附的弧头数目,
称为该顶点的入度。一个顶点依附的弧尾数目,称
为该顶点的出度,某个顶点的入度和出度之和称为
该顶点的度
l另外,若图中有n个顶点,e条边或弧,第i个顶点的
度记为TD(v),则有:
i
4.子图
l若有两个图G和G,G=(V,E),G=(V,E),满
12111222
足如下条件:,,即V为V的子集,
21
E为E的子集,称图G为图G的子图。
2121
图与子图
5.权
l在图的边或弧中给出相关的数,称为权。权可以代
表一个顶点到另一个顶点的距离、耗费等,带权图
一般称为网。
无向带权图与有向带权图
6.连通图和强连通图
l在无向图中,若从顶点i到顶点j有路径,则称顶点i和顶点j是
无向图中
连通的。若任意两个顶点都是连通的,则称此无向图为连通
图,否则称为非连通图。
l在有向图中,若从顶点i到顶点j有路径,则称从顶点i和顶点j
是连通的,若图中任意两个顶点都是连通的,则称此有向图
为强连通图,否则称为非强连通图
7.连通分量和强连通分量
l无向图中,极大的连通子图为该图的连通分量。显
文档评论(0)