数据结构图的定义与存储结构C.ppt

  1. 1、本文档共45页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
数据结构图的定义与存储结构C

课程先后关系如图: 7.1 图的定义和术语 1.基本术语 (1)顶点 图中的数据元素通常称为顶点。V是顶点的有穷非空集合;VR是两个顶点之间的关系的集合。 (2)有向图 若称 v,w∈VR表示从v到w的一条弧,且称v为弧尾或初始点,称w为弧头或终端结点,则该图称为有向图。 (3)无向图 若v,w∈VR,必有w,v∈VR,即VR是对称的,则以无序对(v,w)代替这两个有序对,表示v和w之间的一条边,则该图称为无向图。 (4)权/网 有时图的边或弧具有与它相关的数,这些数称为权值(通常表示顶点间的距离或耗费),则带权值的图称为网。 (5)子图 假设有两个图 G=(V,{ VR })和 G’=(V’,{ VR’ }),若 V’ 是 V 的子集,且 VR’ 是 VR 的子集,则称 G’ 为 G 的子图。 (6)完全图 假设用 n 表示图中顶点的数目,用 e 表示边或弧的数目。忽略自身弧/边,即若﹤vi,vj﹥ ∈VR,则 vi≠vj。 对于无向图,有 (n(n-1))/2 条边的无向图称为完全图。对于有向图,有 n(n-1) 条弧的有向图称为有向完全图。 (7)稀疏图/稠密图 边或弧很少(如e<nlogn)的图称稀疏图,反之称稠密图。 (8)邻接点 对于无向图G=(V,{E}),若边(v,v’)∈E,则称顶点 v 和 v’ 互为邻接点,即 v 和 v’ 相邻接。或称边(v,v’)依附于顶点v 和 v’,或称(v,v’)和顶点 v 和 v’ 相关联。 对于有向图G=(V,{E}),若弧v,v’ ∈E,则称顶点 v 邻接到顶点 v’,或称顶点 v’ 邻接自顶点 v ,或弧v,v’和顶点 v,v’ 相关联。 顶点的入度/出度 以顶点 v 为头的弧的数目称 v 的入度,记为ID(v);以顶点 v 为尾的弧的数目称 v 的出度,记为 OD(v)。 顶点 v 的度 TD(v)=ID(v)+OD(v) (10)路径(Path) 无向图G=(V,{E})中,从顶点v到v’的路径是顶点序列(v=vi0,vi1,…,vim=v’),其中(vij-1 ,vij)∈E ,1≤j≤m。 若G是有向图,则路径也是有向的,顶点序列应满足:vij-1 ,vij∈E ,1≤j≤m。 (11)回路/环/简单路径 第一个顶点和最后一个顶点相同的路径称为回路/环。 序列中顶点不重复出现的路径称为简单路径。 除了第一个顶点和最后一个顶点之外,其余顶点不重复出现的回路,称为简单回路或简单环。 (12)连通图/连通分量 在无向图G中,如果从顶点 V 到顶点 V’ 有路径,则称 V 和 V’ 是连通的。 若图中任意两个顶点 vi、vj∈V,vi 和 vj 都是连通的,则称 G 是连通图。 无向图中的极大连通子图称之为连通分量。 (13)强连通图/强连通分量 在有向图 G 中,若对于每一对vi、vj∈V,vi≠vj,从 vi 到 vj 和从 vj 到 vi 都存在路径,则称 G 是强连通图。 有向图中的极大强连通子图称作有向图的强连通分量。 一个连通图的生成树是一个极小连通子图,它含有图中全部顶点,但只有足以构成一棵树的n-1条边。 如果在一棵生成树上添加一条边,必定构成一个环,因为这条边使得它依附的那两个顶点之间有了第二条路径。 如果一个有向图恰有一个顶点的入度为 0,其余顶点的入度均为 1,则是一棵有向树。一个有向图的生成森林由若干棵有向树组成,含有图中全部顶点,但只有足以构成若干棵不相交的有向树的弧。 基本操作 CreateGraph(G,V,VR); // 按V和VR的定义构造图G DestroyGraph(G); // 销毁图G LocateVex(G, u); // 若G中存在顶点u,则返回该顶点 // 在图中位置;否则返回其它信息 GetVex(G, v); // 返回 v 的值 PutVex(G, v, value); // 对 v 赋值value FirstAdjVex(G, v); // 返回v的第一个邻接点。 // 若v在G中没有邻接点,则返回“空” NextAdjVex(G, v, w); // 返回v的(相对于w的)下一 // 个邻接点。若w是v的最后一个邻接点,则“空” InsertVex(G, v); // 在图G中增添新顶点v。 DeleteVex(G, v); // 删除G中顶点v及其相关的弧 InsertArc(G, v, w); // 在G中增

文档评论(0)

taotao0c + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档