版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
图的定义和术语及存储结构第1页,课件共35页,创作于2023年2月17.1基本术语7.2存储结构7.3图的遍历7.4图的连通性7.5图的应用第7章图第2页,课件共35页,创作于2023年2月27.1图的基本术语其中:V
是G的顶点集合,是有穷非空集;
VR={<v,w>|v,w∈V且P(v,w)},是有穷集.问:当VR为空时,图G存在否?V=vertex图:记为
Graph=(
V,VR)EACBD<v,w>表示从v到w的一条弧,并称w为弧头,v为弧尾。P(v,w)定义了弧<v,w>的意义或信息。答:还存在!但此时图G只有顶点。第3页,课件共35页,创作于2023年2月3EACBD例如:G=(V,VR)其中V={A,B,C,D,E}VR={<A,B>,<A,E>,<B,C>,<C,D>,<D,B>,<D,A>,<E,C>}无向图:由顶点集和边集构成的图(“边”无方向)若<v,w>VR必有<w,v>VR,则称(v,w)
为顶点v和顶点w之间存在一条边。有向图:由顶点集和弧集构成的图(“弧”是有方向的)第4页,课件共35页,创作于2023年2月4BCAFED例如:
G=(V,VR)其中:V={A,B,C,D,E,F}VR={(A,B),(A,E),(B,E),(C,D),(D,F),(B,F),(C,F)}若
n个顶点的无向图有
n(n-1)/2条边,
称为无向完全图若
n个顶点的有向图有n(n-1)条边,称为有向完全图证明:①有向完全图有n(n-1)条边。证明:若是有向完全图,则n个顶点中的每个顶点都有一条弧指向其它n-1个顶点,因此总边数=n(n-1)1234第5页,课件共35页,创作于2023年2月5证明:从①可以直接推论出无向完全图的边数——因为无方向,两弧合并为一边,所以边数减半,总边数为n(n-1)/2。②无向完全图有n(n-1)/2条边。1234例:判断下列4种图形各属什么类型?第6页,课件共35页,创作于2023年2月6稀疏图:
稠密图:设有两个图G=(V,E)和G’=(V’,E’)。若V’V且E’E,则称图G’是图G的子图。子图:边较少的图。通常边数远少于nlogn边很多的图。无向图中,边数接近n(n-1)/2有向图中,边数接近n(n-1)BBCABECFABECF例如:第7页,课件共35页,创作于2023年2月7ABECF1597211132有向网或无向网是弧或边带权的图。邻接点:若边(v,w)∈VR,则顶点v和顶点w互为邻接点。
边(v,w)依附于顶点v和w,或者与顶点v,w相关联。顶点v的度:是和v相关联的边的数目,记为TD(v).顶点v的出度:
以顶点v
为尾的弧的数目;记为OD(v).顶点v的入度:
以顶点v
为头的弧的数目,记为ID(v).顶点的度(TD)=出度(OD)+入度(ID)问:当有向图中仅1个顶点的入度为0,其余顶点的入度均为1,此时是何形状?答:是树!而且是一棵有向树!第8页,课件共35页,创作于2023年2月8路径:设图G=(V,VR)中的一个顶点序列:v=vi,0,vi,1,…,vi,m=w中,(vi,j-1,vi,j)(或〈vi,j-1,vi,j〉)
VR
1≤j≤m,则称从顶点v
到顶点w
之间存在一条路径。路径长度:路径上边(或弧)的数目。ABECF如:从A到F长度为3的路径{A,B,C,F}或{A,E,C,F}简单路径:指序列中顶点不重复出现的路径。简单回路:指序列中第一个顶点和最后一个顶点相同,其余顶点不重复出现的回路。第9页,课件共35页,创作于2023年2月9连通图:无向图G中任意两个顶点之间都有路径相连通。连通分量:非连通图中的极大连通子图。BACDFEBACDFE强连通图:在有向图中,每一对顶点vi和vj,都存在一条从vi到vj和从vj到vi的路径强连通分量:非强连通图中的极大强连通子图。ABECFABECF第10页,课件共35页,创作于2023年2月10生成树:v1v2v3v4生成森林:假设一个连通图有n个顶点和e条边,其中n-1条边和n个顶点构成一个极小连通子图,称该极小连通子图为此连通图的生成树。由若干棵生成树组成,含全部顶点,但构成这些树的边是最少的。(对有向或无向图均适用)第11页,课件共35页,创作于2023年2月11CreatGraph(&G,V,VR)//按定义(V,VR)构造图DestroyGraph(&G)
//销毁图结构的建立和销毁对顶点的访问操作LocateVex(G,u)
//若G中存在顶点u,则返回该顶点在图中“位置”,否则返回其它信息。GetVex(G,v)
//返回v的值。PutVex(&G,v,value)
//对v赋值value。结构的建立和销毁插入或删除顶点对邻接点的操作遍历插入或删除弧基本操作对顶点的访问操作第12页,课件共35页,创作于2023年2月12对邻接点的操作FirstAdjVex(G,v);//返回v的“第一个邻接点”若该顶点在G中没有邻接点,则返回“空”。NextAdjVex(G,v,w);//返回v的(相对于w的)“下一个邻接点”。若w是v的最后一个邻接点,则返回“空”。插入或删除顶点InsertVex(&G,v);
//在图G中增添新顶点v。DeleteVex(&G,v);//删除G中顶点v及其相关的弧。第13页,课件共35页,创作于2023年2月13插入和删除弧InsertArc(&G,v,w);//在G中增添弧<v,w>,若G是无向的,则还增添对称弧<w,v>。DeleteArc(&G,v,w);//在G中删除弧<v,w>,若G是无向的,则还删除对称弧<w,v>。DFSTraverse(G,v,Visit());//从顶点v起深度优先遍历图G,并对每个顶点调用函数Visit一次且仅一次。BFSTraverse(G,v,Visit());//从顶点v起广度优先遍历图G,并对每个顶点调用函数Visit一次且仅一次。遍历第14页,课件共35页,创作于2023年2月147.2图的存储结构图的特点:链式存储结构:顺序存储结构:难!(多个顶点,无序可言,无法仅以顶点坐标表达相互关系)可用多重链表邻接矩阵(数组)表示法邻接表(链式)表示法十字链表表示法邻接多重表表示法但可用数组描述元素间关系。非线性结构(m:n)邻接矩阵邻接表十字链表邻接多重表各种表示法成立的原则:存入电脑后能唯一复原第15页,课件共35页,创作于2023年2月15①建立一个顶点表和一个邻接矩阵。1.邻接矩阵(数组)表示法记录各个顶点信息表示各个顶点之间关系②设图A=(V,E)有n个顶点,则图的邻接矩阵是一个二维数组A.arcs[n][n],定义为:第16页,课件共35页,创作于2023年2月16分析1:无向图的邻接矩阵是对称的;分析2:顶点i
的度=第i
行(列)中1的个数;特别:完全图的邻接矩阵中,对角元素为0,其余全1。例1:邻接矩阵:A.arcs=(v1v2
v3v4v5)v1v2v3v4v501
0
1010
1010
10111010101110顶点表:无向图的邻接矩阵如何表示?v1v2v3v5v4v4A第17页,课件共35页,创作于2023年2月17例2:有向图的邻接矩阵如何表示?分析1:有向图的邻接矩阵可能是不对称的。分析2:顶点vi的出度=第i行元素之和;
顶点vi的入度=第i列元素之和;
顶点的度=第i行元素之和+第i列元素之和。v1v2v3v4A邻接矩阵:A.arcs=(v1v2
v3v4)v1v2v3v4注:在有向图的邻接矩阵中,第i行含义:以结点vi为尾的弧(即出度边);第j列含义:以结点vj为头的弧(即入度边)。顶点表:01
1
000
000
001
1000第18页,课件共35页,创作于2023年2月18例3:有权图(即网络)的邻接矩阵如何表示?定义:A.arcs[i][j]=Wij<vi,vj>或(vi,vj)∈VR∞反之v1v2v3v4Nv5v65489755613邻接矩阵:N.arcs=(v1v2
v3v4v5v6)顶点表:∞
5
∞
7∞
∞∞
∞
4
∞∞
∞8
∞
∞
∞∞
9∞
∞
5∞∞
6∞
∞
∞
5∞
∞
3
∞
∞∞1
∞v1v2v3v4v5v6第19页,课件共35页,创作于2023年2月19容易实现图的操作,如:求某顶点的度、判断顶点之间是否有边(弧)、找顶点的邻接点等等。
n个顶点需要n*n个单元存储边(弧);空间效率为O(n2)。邻接矩阵法优点:邻接矩阵法缺点:对稀疏图而言尤其浪费空间。图的邻接矩阵在机内如何表示?(参见教材P161)注:用两个数组分别存储顶点表和邻接矩阵#defineINFINITYINT_MAX//最大值∞#defineMAX_VERTEX_NUM20//假设的最大顶点数typedefenum{DG,DN,UDG,UDN}GraphKind;//{有向图,有向网,无向图,无向网}第20页,课件共35页,创作于2023年2月20typedefstructArcCell{//弧的定义
VRTypeadj;//VRType是顶点关系类型。//对无权图,用1或0表示相邻否;对带权图,则为权值类型。
InfoType*info;//该弧相关信息的指针}ArcCell,
AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedefstruct{//图的定义
VertexTypevexs[MAX_VERTEX_NUM];
//顶点向量
AdjMatrixarcs;
//邻接矩阵
intvexnum,arcnum;//顶点数,弧数
GraphKindkind;//图的种类标志
}MGraph;第21页,课件共35页,创作于2023年2月212.邻接表(链式)表示法①对每个顶点vi建立一个单链表,把与vi有关联的边(或以vi为尾的弧)的信息链接起来,表中每个结点都设为3个域。②每个单链表还应当附设一个表头结点(设为2个域),存vi信息;adjvexnextarcinfodatafirstarc表结点头结点邻接点域,表示vi
邻接点的位置链域,指向下一条边或弧的结点数据域,存储顶点vi
信息链域,指向单链表的第一个结点③每个单链表的头结点另外用顺序存储结构存储。边或弧的信息第22页,课件共35页,创作于2023年2月22例1:无向图的邻接表如何表示?v1v2v3v5v4v4邻接表:01234^1334^142^0请注意:邻接表不唯一!因各个边结点的链入顺序是任意的。v1v2v3v4v523^142^0v1邻接点v4的位置此无权图未开第3分量TD(Vi)=单链表中Vi链接的结点个数第23页,课件共35页,创作于2023年2月23例2:有向图的邻接表如何表示?v1v2v3v4V4V3^V2V12^3^0^1邻接表(出边)V4V3V2V1^3^0^2^0逆邻接表(入边)01230123在有向图的邻接表中不易找到指向该顶点的弧。OD(Vi)=邻接表中Vi链接的结点数ID(Vi)=逆邻接表中Vi链接的结点数TD(Vi)=OD(Vi)+ID(Vi)第24页,课件共35页,创作于2023年2月24例3:已知某网的邻接(出边)表,请画出该网络。8064125当邻接表的存储结构形成后,图便唯一确定!第25页,课件共35页,创作于2023年2月25分析1:对于n个顶点e条边的无向图,邻接表中除了n个头结点外,只有2e个表结点,空间效率为O(n+2e)。若是稀疏图(e<<n2),则比邻接矩阵表示法O(n2)省空间。邻接表存储法的特点:分析2:在有向图中,邻接表中除了n个头结点外,只有e个表结点,空间效率为O(n+e)。若是稀疏图,则比邻接矩阵表示法合适。—它其实是对邻接矩阵法的一种改进,两个结点表示一条边或弧邻接表的缺点:邻接表的优点:空间效率高;容易寻找顶点的邻接点;判断两顶点间是否有边或弧,需搜索两结点对应的单链表,没有邻接矩阵方便。第26页,课件共35页,创作于2023年2月26讨论:邻接表与邻接矩阵有什么异同之处?1.联系:邻接表中每个链表对应于邻接矩阵中的一行,链表中结点个数等于一行中非零元素的个数。2.区别:①对于任一确定的无向图,邻接矩阵是唯一的(行列号与顶点编号一致),但邻接表不唯一(链接次序与顶点编号无关)。②邻接矩阵的空间复杂度为O(n2),而邻接表的空间复杂度为O(n+e)。3.用途:邻接矩阵多用于稠密图的存储(e接近n(n-1)/2);而邻接表多用于稀疏图的存储(e<<n2)第27页,课件共35页,创作于2023年2月27图的邻接表在机内如何表示?(参见教材P163)#defineMAX_VERTEX_NUM20
//假设的最大顶点数TypedefstructArcNode{//弧结构
intadjvex;
//该弧所指向的顶点位置
structArcNode*nextarcs;
//指向下一条弧的指针
InfoArc*info;
//该弧相关信息的指针}ArcNode;第28页,课件共35页,创作于2023年2月28Typedefstruct{
//图结构
AdjListvertics
;
//应包含邻接表
intvexnum,arcnum;
//应包含顶点总数和弧总数
intkind;
//还应说明图的种类(用标志)}ALGraph;TypedefstructVNode{
//顶点结构
VertexTypedata;
//顶点信息
ArcNode*firstarc;
//指向第一条依附该顶点的弧的指针}VNode,AdjList[MAX_VERTEX_NUM];
//邻接表
第29页,课件共35页,创作于2023年2月29
它是有向图的另一种链式存储结构。
思路:将邻接矩阵用链表存储,是邻接表、逆邻接表的结合。(1)开设弧结点,设5个域(每段弧是一个数据元素)(2)开设顶点结点,设3个域(每个顶点也是一个数据元素)tailvexheadvexhlinktlinkinfo弧结点3.十字链表表示法tailvex:
弧尾顶点位置headvex:
弧头顶点位置hlink:
弧头相同的下一弧位置tlink:
弧尾相同的下一弧位置info:
弧信息第30页,课件共35页,创作于2023年2月30
data:
顶点信息firstin:
以顶点为弧头的第一条弧结点firstout:
以顶点为弧尾的第一条弧结点问:n个顶点的集合怎样储存?顺序存储结构datafirstinfirstout顶点结点十字链表优点:容易操作,如求顶点的入度、出度等。空间复杂度和建表的时间复杂度都与邻接表相同。第31页,课件共35页,创作于2023年2月31
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2027届辽宁省朝阳市凌源市高三上学期11月月考历史试题(含答案)
- 2026-2027学年上学期单元测试八年级生物复习卷及答案
- 2026-2027学年上学期单元测试八年级历史培优卷打印版
- 2025教师资格证-初中学科专业知识真题试卷及答案
- 2025建筑八大员-机械员机械安全素养检测题及答案
- 2025国家公务员考试结构化面试通关题库及答案
- 雨水口回填夯实施工技术研究
- 强夯法地基处理施工参数优化分析
- 商务合作会议记录函(6篇)范文
- 智能家居产品用户场景化营销指南
- 【MOOC】文献检索与论文写作-西北工业大学 中国大学慕课MOOC答案
- 北师大版七年级上册数学期中考试试题附答案
- 早产儿低体重儿护理课件
- JB-T 7072-2023 水轮机调速器及油压装置 系列型谱
- JBT 14645-2023 低温装置用密封垫片 (正式版)
- (高清版)JTGT 3650-01-2022 公路桥梁施工监控技术规程
- 国内外A2O工艺处理城市污水技术研究现状及展望
- 汽机检修三级安全教育课件
- 数学文化推进核心素养的实践研究教学课件-A3演示文稿设计与制作
- 奔腾B70保养手册
- 运用PDCA缩短门诊患者静脉采血等候时间
评论
0/150
提交评论