版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、数 据 结 构第三十八课 图的定义与术语,第三十课 图的定义与术语,本课主题: 图的定义与术语 教学目的: 掌握图的定义及常用术语 教学重点: 图的常用术语 教学难点: 图的常用术语 授课内容:,一、图的定义,图是一种数据元素间为多对多关系的数据结构,加上一组基本操作构成的抽象数据类型。,图的抽象数据类型定义(1),ADT Graph 数据对象V :V是具有相同特性的数据元素的集合,称为顶点集。 数据关系R:R=VR VR=|v,wV且P(v,w),表示从v到w的弧, 谓词P(v,w)定义了弧的意义或信息 基本操作P: CreateGraph( 初始条件:V是图的顶点集,VR是图中弧的集合。
2、操作结果:按V和VR的定义构造图G,图的抽象数据类型定义(2),DestroyGraph( 初始条件:图G存在,v是G中某个顶点 操作结果:返回v的值。,FirstAdjVex(G,v); 初始条件:图G存在,v是G中某个顶点 操作结果:返回v的第一个邻接顶点。若顶点在G中没有邻接 顶点,则返回“空” PutVex( 初始条件:图G存在,v是G中某个顶点,w是v的邻接顶点。 操作结果:返回v的(相对于w的)下一个邻接顶点。若w是v的 最后一个邻接点,则返回“空”,图的抽象数据类型定义(3),InsertVex( 初始条件:图G存在,v和w是G中两个顶点 操作结果:在G中增添弧,若G是无向的,则
3、还增添对称弧,图的抽象数据类型定义(4),DeleteArc( 初始条件:图G存在,v是G中某个顶点,Visit是顶点的应用函 数 操作结果:从顶点v起深度优先遍历图G,并对每个顶点调用函数Visit一次。一旦Visit()失败,则操作失败。,图的抽象数据类型定义(5),BFSTRaverse(G,v,Visit(); 初始条件:图G存在,v是G中某个顶点,Visit是顶点的应用函数 操作结果:从顶点v起广度优先遍历图G,并对每个顶点调用函数Visit一次。一旦Visit()失败,则操作失败。 ADT Graph,图的抽象数据类型定义(6),二、图的常用术语(1),有向图、无向图 弧:; 边
4、(x,y)。,二、图的常用术语(2),对于无向图,e的取值范围是0到n(n-1)/2, 有n(n-1)/2条边的无向图称为无向完全图。,如果用n表示图中顶点数目,用e表示边或弧的数目, 则有:,二、图的常用术语(3),对于有向图,e有取值范围是0到n(n-1)。 具有n(n-1)条弧的有向图称为有向完全图。,二、图的常用术语(4),有很少条边或弧的图称为稀疏图,反之称为稠密图。,二、图的常用术语(5),和边(弧)相关的数叫权 带权的图称网。 邻接、邻接点 无向图中, 一条边连起来的两个顶点,互称邻接点; 有向图中,若从顶点x到顶点y有一条弧,则说顶点x邻接到顶点y,而顶点y邻接自顶点x。,对上
5、图有:G1=(V1,A1) 其中:V1=v1,v2,v3,v4 A1=,二、图的常用术语(6),二、图的常用术语(7),度、出度、入度 无向图中和顶点相关的边(e)的个数叫顶点的度。 有向图中从顶点出发的弧的个数叫该顶点的出度,入到该顶点的弧的个数叫该顶点的入度。TD(v)=ID(v)+OD(v),二、图的常用术语(8),路径、路径长度、回路(环)、简单路径 连通、连通图、连通分量 无向图顶点v1到顶点v2有路径,则说v1和v2连通。若任意两个顶点都连通,则说该图是连通的。连通分量是无向图中的极大连通子图。 强连通图、强连通分量,二、图的常用术语(9),二、图的常用术语(10),对有向图,如果每一对顶点之间都有通路,则称该图 为强连通图。,二、图的常用术语(11),生成树、有向树、生成森林 一个连通图的生成树是一个极小连通子图,它含有图的全部顶点,但只有足以构成一棵树的n-1条边。 若有向图中只有一个顶点的入度为0,其余顶点的入度均为1,则该有向图称为有向
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 20261028-093051-部编版五年级语文上册形近字辨析含答案
- 2023年消防设施操作员之消防设备中级技能考试试卷含答案
- 2022年口腔医学主治医师相关专业知识试题与答案
- 《3-6岁儿童学习与发展指南》试题及答案(102题)
- 2024年助理医师资格证考试之口腔助理医师题库练习试卷B卷附答案
- 《医院隔离技术标准(2025版)》培训考核试题(附答案)
- 2022年-2023年护师类之主管护师通关试题库(有答案)
- (2025年)学校食堂食品安全知识培训考核试题附答案
- 《3~6岁儿童学习与发展指南》考试题库及答案(共100题)
- 2026年监装员考试题库及参考答案
- 小学六年级心理健康教育《让友谊之花更美丽》教学设计
- 湖北黄冈市2026-2027学年高三上学期11月期中数学试卷及参考答案
- 2026年上海农商银行招聘面试题及答案
- 2026足球行业市场现状供需分析及投资评估规划分析研究报告
- T/TMAC 248-2025连续石墨化炉能源消耗限额
- 2026年江苏省考《申论》真题及答案解析(A卷)
- 工厂液氯泄漏事故应急预案演练脚本
- 2026年江苏省保安员考试试题带解析及完整附答案
- 统计学基础及应用课件 任务9 相关分析与回归分析
- 2026年川教版(新教材)初中信息科技七年级下册(全册)教学设计(附目录)
- 华为大数据 HCIA-Big Data H13-711模拟练习题库(含答案)
评论
0/150
提交评论