第上章图
第七章 图
√7.1图的抽象数据类型定义 7.2图的存储表示 7.3图的遍历 7.4最小生成树 7.5拓扑排序 7.6关键路径 7.7两点之间的最短路径问题
7.1 图的抽象数据类型定义 7.2 图的存储表示 7.3 图的遍历 7.4 最小生成树 7.7 两点之间的最短路径问题 7.5 拓扑排序 7.6 关键路径
7.1图的抽象数据类型定义 一、图的结构定义 二、名词和术语 三、基本操作
7.1 图的抽象数据类型定义 一、图的结构定义 二、名词和术语 三、基本操作
、 图的结构定义 图是由一个顶点集V和一个弧集VR构成的数 据结构。 Graph =(V,VR) V是顶点的有穷非空集合， VR是两顶点间关系的集合。 其中，VR={|V,w∈V且P(W,w)} 表示从v到w的一条弧，并称v为弧尾， w为弧头。 谓词Py,w定义了弧的意义或信息
图是由一个顶点集 V 和一个弧集 VR构成的数 据结构。 Graph = (V, VR ) 其中，VR＝{| v,w∈V 且 P(v,w)} 表示从 v 到 w 的一条弧，并称 v 为弧尾， w 为弧头。 谓词 P(v,w) 定义了弧 的意义或信息。 V是顶点的有穷非空集合， VR是两顶点间关系的集合。 v w 一、图的结构定义
二、名词和术语 1.有向图：由于“弧”是有方向的，因此 称由项点集和弧集构成的图为有向图。 例如：G1=(V1,VR1) 其中 V=A,B,C,D,E VR={,, E ,, ,}
由于“弧”是有方向的，因此 称由顶点集和弧集构成的图为有向图。 E A C B D 例如: G1 = (V1 , VR1 ) 其中 V1={A, B, C, D, E} VR1={, , , , , , } 1.有向图： 二、名词和术语
2.无向图： 3.边：若IVR,即VR是对称的， 集构成的图称 则以无序对(v,w代替这两个 有序对，称顶点V和顶点w 作无向图。 之间存在一条边(V,w) 例如：G2(V2,VR2) V2=A,B,C,D,E,F) VR2={(A,B),(A,E), B,E),(C,D),(D,F) (B,F),(C,F)}
若 VR 必有 VR, 即VR是对称的， 则以无序对(v,w)代替这两个 有序对，称顶点 v 和顶点 w 之间存在一条边(v,w) 。 B C A F E D 由顶点集和边 集构成的图称 作无向图。 例如: G2=(V2 ,VR2 ) V2={A, B, C, D, E, F} VR2={(A, B), (A, E), (B, E), (C, D), (D, F), (B, F), (C, F) } 2.无向图： 3.边：
5.有向网，无向网： 弧或边带权的图 分别称作有向网或 无向网。 4.子图： 设图G=(V,VR)和 A 图G口=(V口， VR▣)， 且V口▣V, VR▣▣VR
A B E C F A E F B B C 设图G=(V, VR) 和 图 G =(V , VR ), 且 V V, VR VR, 则称 G 为 G 的子图。 15 9 7 21 11 3 2 弧或边带权的图 分别称作有向网或 无向网。 4. 子图： 5. 有向网，无向网：
6.完全图、稀疏图、稠密图： 完全图 假设图中有n个顶点，e条边， 如果e=n(n-1)/2,则该无向图为完全图。 有向完全图 将含有e=n(n-1)条弧的有向图 称作有向完全图。 稀疏图：如果边或弧的个数满足e<n log n, 则称作稀疏图，否则称作稠密图
完全图 假设图中有 n 个顶点，e 条边， 如果e=n(n-1)/2 ，则该无向图为完全图。 有向完全图 将含有 e=n(n-1) 条弧的有向图 称作有向完全图。 稀疏图：如果边或弧的个数满足 e < n log n， 则称作稀疏图，否则称作稠密图。 6. 完全图、稀疏图、稠密图：
7.邻接点、度 对无向图来说， 邻接点：假若顶点ⅴ和顶点w之间存在一条边， 则称顶点ⅴ和w互为邻接点， 度：与顶点v关联的边的数目，记为TD(v)。 例如： TD(B)=3 A TDA)=2
邻接点：假若顶点v 和顶点w 之间存在一条边， 则称顶点 v 和 w 互为邻接点， 例如: TD(B) = 3 TD(A) = 2 度：与顶点v 关联的边的数目,记为TD(v)。 A C D F E B 7.邻接点、度 对无向图来说
8.入度、出度 对有向图来说， 由于弧有方向性， 顶点的出度：以顶点v 则有入度和出度之分 为弧尾的弧的数目， 记为OD(): 顶点的入度：以顶点V 为弧头的弧的数目， 记为ID(W)。 例如： OD(B)=1 有向图中项点的： ID(B)=2 度(TD)=出度(OD)+入度(D) TD(B)=3
顶点的出度: 以顶点v 为弧尾的弧的数目, A 记为OD(v); B E C F 对有向图来说， 顶点的入度: 以顶点v 为弧头的弧的数目, 记为ID(v)。 有向图中顶点的: 度(TD)=出度(OD)+入度(ID) 例如: I D(B) = 2 OD(B) = 1 TD(B) = 3 由于弧有方向性， 则有入度和出度之分 8.入度、出度