- 1、本文档共45页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
数据结构MapleRelated
数据结构-Maple Related-
牟克典
数学科学学院信息科学系
2012秋季
4/10/2017
1
第五讲 图和图算法(1)
图:基本概念和性质
图的基本操作
图的遍历
宽度优先
深度优先
图的表示
生成树
最小生成树
2012年11月21日
10:10-12:00
三教303
4/10/2017
2
图(graph)
图是一种数学结构,数学里有分支 “图论”,研究一种拓扑结构
这里把它看着一类复杂数据结构,用于表示具有各种复杂关系的数据集合。图在实际中应用很广泛
本章介绍图的最基本知识,图的基本实现方法,以及图的若干最基本的计算问题和重要算法
重点算法(这些算法是本章最重要的内容):
图的深度优先有哪些信誉好的足球投注网站与广度优先有哪些信誉好的足球投注网站
最小生成树的 Prim 算法和 Kruskal 算法
求单源最短路径的 Dijkstra 算法
求所有顶点对之间最短路径的 Floyd 算法
拓扑排序
关键路径
4/10/2017
3
图:基本概念
图是二元组 G = ( V, E ),其中
V 是顶点的非空有穷集合(可有空图的概念,用处不大)
E 是顶点偶对 (称为“边”) 的集合,E ? V×V
V 中的顶点也称为图 G 的顶点,E 中的边也称为图 G 的边
有向图:有向图中的边有方向,边是顶点的有序对
有序对用尖括号表示。vi,vj 表示从 vi 到 vj 的有向边,vi 称为边的始点,vj 是边的终点。vi, vj 和 vj, vi 表示两条不同有向边
无向图:无向图中的边没有方向,是顶点的无序对
无序对用圆括号表示,(vi , vj) 和 (vj , vi) 表示同一条无向边
如果图 G 里有边 vi,vj ? E 或者 (vi, vj) ? E
顶点 vj 称为 vi 的邻接顶点(对无向图,邻接点是双向的)
这种边称为与顶点 vi 相关联的边或 vi 的邻接边
与有序树类似,图中的邻接边也可以规定顺序
4/10/2017
4
图
图可用图形自然表示(圆圈表示顶点,线段或箭头表示边)
两个限制:1)不考虑顶点到自身的边,若 (vi ,vj) 或 vi ,vj 是 G 的边,则要求 vi ≠vj;2)顶点间没有重复出现的边,若 (vi ,vj) 或 vi ,vj 是 G 的边,则它是这两个顶点间的唯一边(不存在多重边)
去掉这些限制得到稍微不同的数学研究对象。图论中也研究它们
4/10/2017
5
图:概念和性质
完全图:任意两个顶点之间都有边的图(有向图或无向图)。显然:
n 个顶点的无向完全图有 n*(n-1)/2 条边
n 个顶点的有向完全图有 n*(n-1) 条边
注意图上的重要事实:|E| ≤ |V|2,或者 |E| = O( |V|2 )
度(顶点的度):与一个顶点关联的边的个数。
对于有向图,还分为出度和入度,分别表示以该顶点为始点或者终点的边的个数
无论是有向图还是无向图,顶点数 n,边数 e 和度数满足下面关系:
其中 D(vi) 表示 vi 的度数
4/10/2017
6
路径和相关概念
路径:对图 G = (V, E),若存在顶点序列 vi0,vi1,…,vi(m),使 (vi0,vi1),(vi1,vi2),…, (vi(m-1), vi(m)) 都在 E 中(对有向图 vi0,vi1, vi1,vi2, …, vi(m-1), vi(m) 都在 E 中)
则说从顶点vi0到vi(m) 存在一条路径
vi0,vi1,…,vi(m) 称为从 vi0 到 vi(m) 的路径
路径长度:路径上边的条数
回路(环):起点和终点相同的路径
如果除起点和终点外的其他顶点均不相同,则称为简单回路
简单路径:内部不包含环路的路径,
即,路径上的顶点除起点和终点可能相同外,其它顶点均不相同
简单回路也是简单路径
4/10/2017
7
子图、有根图
对图 G = (V,E) 和 G’ = (V’,E’),如果 V’ ? V 且 E’ ? E,就称 G’ 是 G 的子图。特别的,G 是其自身的子图
下面是有向图G1的几个子图
有根图
如果有向图 G 中存在一个顶点 v,从 v 有路径可以到达图 G 中其它所有顶点,则称 G 为一个有根图,v 称为图 G 的一个根
有根图中的根可能不唯一
4/10/2017
8
连通图
连通:如果无向图 G 中存在从 vi 到 vj 的路径(显然它也是从 vj到 vi 的路径),则称 vi 与 vj 连通(默认顶点 v 到自身连通)
无向图的连通性
连通图:如果无向图 G 中的任意两个不同顶点 vi 和 vj 之间都连通(都存在路径),则称 G 为连通图
极大连通子图是图中极大的连通子图(没有真包含它连通子图)
连通分量:无向图 G 的一个极大连通子图称为 G 的一个连通分量。若 G 不连通,其
您可能关注的文档
- 数学概念及其教学.ppt
- 数学正弦定理人教A版必修页.ppt
- 数学活动找朋友活动过程导入今天徐老师给.ppt
- 数学物理方法第十三章.ppt
- 数学物理方法第九章.ppt
- 数学物理方法第十二章.ppt
- 数学物理方法第十四章.ppt
- 数学物理方法第十章.ppt
- 数学物理方程ch.ppt
- 数学直线与圆圆与圆的位置关系.ppt
- 《中国通史》文字稿第12集春秋争霸.docx
- java教程--类与对象-讲义课件(演讲稿).ppt
- Vue应用程序开发-(1).pptx
- 东北师大版社劳动实践与评价指导手册一年级上册主题二活动一寻找五彩的树叶课时课件.pptx
- 外研版英语四年级上册 Module 4 Unit 2 How much is it单元教学设计.docx
- 外研版英语四年级上册Module 4 单元整体教学设计.docx
- 6《上课之前》课件 鄂科技版 心理健康教育一年级.pptx
- 《1~5的认识》说课课件(共25张PPT)人教版一年级上册数学.pptx
- 六《解决问题(1)》说课课件 人教版 三年级上册数学.pptx
- 七《解决问题》说课课件 人教版 二年级上册数学.pptx
文档评论(0)