教黎 第七章图 程序设计—数据结构 图的遍历算法及其应用 第7章图 7.1图的定义和基本术语 1、图的特征 任意两个数据元素之间都可能相关。结点之间的关系是多对多的。 G=(V,{E}) 2、基本术语 结点：顶点 结点间的关系：无向图：边(yw),v与w互为邻接点，边(y,w)依附于顶点y,w,边(v,w) 和顶点y,w相关联 v的度：和v相关联的边的数目。 有向图：弧<y,w>,v弧尾，w弧头，顶点v邻接到顶点w,顶点w邻接 自顶点v,弧<y,w>和顶点y,相关联。 v的入度：以v为弧头的弧的数目：v的出度：以v为弧尾的弧的数目： v的度：v的入度与出度之和。 路径、回路（环、简单路径、简单回路（简单环） 连通性：若从顶点v到顶点v有路径，则称v和v是连通的 图的规模：顶点数n、边（弧）数、项点的度（有向图：入度/出度） 子图：G=(P,{E}),G=(V,{E),若VcV且EcE,则称G是G的子图。 图的分类： 1)关系的方向性（无向/有向）、关系上是否有附加的数一一权（图/网） 有向图、无向图、有向网、无向网 2)边（弧）数：完全图（边数=n(r1)/2的无向图）、有向完全图（弧数=n(m1)的有向图） 稀疏图(e<nlogn)、稠密图(e>nlogn) 3)连通性：无向图：连通图（任意两顶点都是连通的）、连通分量（极大连通子图）、生成树极 小连通子图)、生成森林 有向图：强/弱连通图、强连通分量、生成树（极小连通子图）、生成森林 3、抽象数据类型定义 ADT Graph 数据对象V:V是具有相同特性的数据元素的集合，称为顶点集。 数据关系R: R=VR) VR={<V,w>WweV且P(W,w),<y,w>表示从v到w的弧，谓词P(V,w) 定义了弧<y,w>的意义或信息} 基本操作： CreateGraph(&G.V.VR) 初始条件：V是图的顶点集，VR是图中弧的集合 操作结果：按V和VR的定义构造图G DestroyGraph(&G) 初始条件：图G存在 操作结果：销毁图G LocateVex(G,u) 初始条件：图G己存在，u和G中顶点有相同特征 文档编号 完成时间 完成人张昱 修改时间20026-6 第1页程序设计——数据结构 第七章 图 图的遍历算法及其应用 文档编号 完 成 人 张 昱 完成时间 修改时间 2002-6-6 第 1 页 第7章 图 7.1 图的定义和基本术语 1、图的特征 任意两个数据元素之间都可能相关。结点之间的关系是多对多的。 G = (V,{E}) 2、基本术语 结点： 顶点 结点间的关系：无向图：边( v, w )，v 与 w 互为邻接点，边( v, w )依附于顶点 v, w，边( v, w ) 和顶点 v, w 相关联 v 的度：和 v 相关联的边的数目。 有向图：弧< v, w >，v 弧尾，w 弧头，顶点 v 邻接到顶点 w，顶点 w 邻接 自顶点 v，弧< v, w >和顶点 v,w 相关联。 v 的入度：以 v 为弧头的弧的数目；v 的出度：以 v 为弧尾的弧的数目； v 的度：v 的入度与出度之和。 路径、回路(环)、简单路径、简单回路(简单环) 连通性：若从顶点 v 到顶点 v’有路径，则称 v 和 v’是连通的 图的规模：顶点数 n、边(弧)数 e、顶点的度(有向图：入度/出度) 子图：G’= (V’,{E’}), G = (V,{E})，若 V’V 且 E’ E，则称 G’是 G 的子图。 图的分类： 1）关系的方向性（无向/有向）、关系上是否有附加的数——权(图/网) 有向图、无向图、有向网、无向网 2）边(弧)数：完全图(边数= n ( n-1 ) / 2 的无向图)、有向完全图(弧数= n ( n-1)的有向图) 稀疏图(e<nlogn)、稠密图(e>nlogn) 3）连通性：无向图：连通图(任意两顶点都是连通的)、连通分量(极大连通子图)、生成树(极 小连通子图)、生成森林 有向图：强/弱连通图、强连通分量、生成树(极小连通子图)、生成森林 3、抽象数据类型定义 ADT Graph{ 数据对象 V：V 是具有相同特性的数据元素的集合，称为顶点集。 数据关系 R： R = {VR} VR = {< v, w >|v, wV且P(v, w)，<v,w>表示从v到w的弧，谓词P(v,w) 定义了弧<v,w>的意义或信息} 基本操作： CreateGraph(&G, V, VR) 初始条件：V 是图的顶点集，VR 是图中弧的集合 操作结果：按 V 和 VR 的定义构造图 G DestroyGraph(&G) 初始条件：图 G 存在 操作结果：销毁图 G LocateVex( G, u ) 初始条件：图 G 已存在，u 和 G 中顶点有相同特征