图的定义和基本术语(精)
13页1、第 13 页图的遍历算法及其应用图 程序设计算法篇 目 录第6章 图26.1 图的定义和基本术语26.2 图的存储和创建36.2.1 图的存储表示36.2.2 图的创建66.3 图的遍历66.3.1 深度优先搜索66.3.2 广度优先搜索76.4 遍历算法的应用86.4.1 应用问题概述86.4.2 求一条包含图中所有顶点的简单路径96.4.3 求距v0最短路径长度最长的一个顶点106.5 图的连通性问题116.5.1 无向图的连通分量和生成树116.5.2 最小生成树136.6 有向无环图及其应用13第6章 图6.1 图的定义和基本术语1、 图的特征任意两个数据元素之间都可能相关。结点之间的关系是多对多的。G = (V,E)2、 基本术语结点:顶点结点间的关系:无向图:边(v,w),v与w互为邻接点,边(v,w)依附于顶点v,w,边(v,w)和顶点v,w相关联v的度:和v相关联的边的数目。有向图:弧,v弧尾,w弧头,顶点v邻接到顶点w,顶点w邻接自顶点v,弧和顶点v,w相关联。v的入度:以v为头的弧的数目;v的出度:以v为尾的弧的数目;v的度:v的入度与出度之和。路径、回路(环)、简
2、单路径、简单回路(简单环)连通性:若从顶点v到顶点v有路径,则称v和v是连通的图的规模:顶点数n、边(弧)数e、顶点的度(有向图:入度/出度)子图:G= (V,E), G = (V,E),若VV且E E,则称G是G的子图。图的分类:1)关系的方向性(无向/有向)、关系上是否有附加的数权(图/网)有向图、无向图、有向网、无向网2)边(弧)数:完全图(边数=n(n-1)/2的无向图)、有向完全图(弧数=n(n-1)的有向图)稀疏图(enlogn)3)连通性:无向图:连通图(任意两顶点都是连通的)、连通分量(极大连通子图)、生成树(极小连通子图)、生成森林有向图:强/弱连通图、强连通分量、生成树(极小连通子图)、生成森林3、 抽象数据类型定义ADT Graph数据对象V:V是具有相同特性的数据元素的集合,称为顶点集。数据关系R:R = VRVR = |v,wV且P(v,w),表示从v到w的弧,谓词P(v,w) 定义了弧的意义或信息 基本操作:CreateGraph(&G, V, VR)初始条件:V是图的顶点集,VR是图中弧的集合操作结果:按V和VR的定义构造图GDestroyGraph(&G
3、)初始条件:图G存在操作结果:销毁图GLocateVex(G,u)初始条件:图G已存在,u和G中顶点有相同特征操作结果:若G中存在顶点u,则返回该顶点在图中位置,否则返回其它信息GetVex(G, v)初始条件:图G存在,v是G中某个顶点操作结果:返回v的值PutVex(&G, v, value)初始条件:图G存在,v是G中某个顶点操作结果:对v赋值valueFirstAdjVex(G, v)初始条件:图G存在,v是G中某个顶点操作结果:返回v的第一个邻接顶点。若顶点在G中没有邻接顶点,则返回“空”NextAdjVex(G, v, w)初始条件:图G存在,v是G中某个顶点,w是v的邻接顶点操作结果:返回v的(相对于w的)下一个邻接顶点。若w是v的最后一个邻接点,则返回“空”InsertVex(&G, v)初始条件:图G存在,v和G中顶点有相同特征操作结果:在图中增添新顶点vDeleteVex(&G, v)初始条件:图G存在,v是G中某个顶点操作结果:删除G中顶点v及其相关的弧InsertArc(&G, v, w)初始条件:图G存在,v和w是G中两个顶点操作结果:在图G中增添弧,若G是无
4、向的,则还应增添对称弧DeleteArc(&G, v, w)初始条件:图G存在,v和w是G中两个顶点操作结果:删除G中的弧,若G是无向的,则还应删除对称弧DFSTraverse(G, v, visit()初始条件:图G存在,v是G中某个顶点,visit是对顶点的应用函数操作结果:从顶点v起深度优先遍历图G,并对每个顶点调用函数visit()一次且至多一次。一旦visit()失败,则操作失败BFSTraverse(G, v, visit()初始条件:图G存在,v是G中某个顶点,visit是对顶点的应用函数操作结果:从顶点v起广度优先遍历图G,并对每个顶点调用函数visit()一次且至多一次。一旦visit()失败,则操作失败ADT Graph6.2 图的存储和创建6.2.1 图的存储表示1、 图的存储表示分析顶点之间的关系是多对多的(m:n),由于m和n都是不定的,无法给出一个这种多对多的关系向线性关系的映射公式图中的关系不能通过顺序映像(即通过顶点之间的存储位置反映顶点之间的逻辑关系)反映;必须另外引入存储空间反映顶点之间的邻接关系。图的存储结构:1)顶点信息;2)边(弧)信息;3)整
《图的定义和基本术语(精)》由会员jiups****uk12分享,可在线阅读,更多相关《图的定义和基本术语(精)》请在金锄头文库上搜索。
建立安全生产长效机制-共创和谐平安输气管道
土石方爆破工程设计方案
康师傅百货商场制度汇编之退换货管理办法
庙头中学2012年中考百日誓师大会学生代表发言稿
围堰拆除爆破工程
华能洱源马鞍山风电场工程土石方爆破管理制度
国资委:全面开展管理提升活动-为培育世界一流企业奠定坚实基础
《专业技术人员职业发展与规划》电子书
应收票据审计方案
建筑给水排水与采暖工程质量验收用表
广播电视管理条例行政处罚裁量标准
广东电力系统调度运行操作管理规定
建筑给排水工程名词解释
幼儿园小班安全健康活动教案:宝宝误食后的急救
建业集团房屋建筑工程交房标准内容技术交底
建筑心理学论文(1)
康师傅百货商场制度汇编之工服管理程序009
建筑工程专业一级建造师继续教育培训结业报告20
廉洁风险防控回头看工作汇报材料
平台工作人员服务规范
2024-04-17 2页
2024-04-17 2页
2024-04-17 2页
2024-04-17 2页
2024-04-17 2页
2024-04-17 2页
2024-04-17 2页
2024-04-17 2页
2024-04-17 2页
2024-04-17 2页