11第十一讲 图.pdf

图的定义和术语 图的定义和术语 图的存储结构 图的存储结构 图的遍历与连通性 图的遍历与连通性 最小生成树 最小生成树 活动网络 活动网络 最短路径 最短路径 7.1 图的定义和术语 7.1 图的定义和术语 图形结构的形式定义 图是由顶点集合(vertex)及顶点 图形结构的形式定义 图是由顶点集合 及顶点 间的关系集合组成的一种数据结构： 间的关系集合组成的一种数据结构 Graph ＝( V, R ) Graph ＝( V, R ) 其中： 其中： V = { x | x ∈某个数据对象} ，是顶点的有穷非空集 V = { x | x ∈某个数据对象} ，是顶点的有穷非空集 合； 合； R——边的有限集合 R——边的有限集合 R = {(x, y ) | x, y ∈V } 无向图 或 R = {(x, y ) | x, y ∈V } 无向图 或 R = {x, y | x, y ∈V Path (x, y )}有向图 R = {x, y | x, y ∈V Path (x, y )}有向图 是顶点之间关系的有穷集合，也叫做边(edge)集合。 是顶点之间关系的有穷集合，也叫做边(edge)集合。 Path (x, y )表示从x 到y 的一条单向通路, 它是有方向 Path (x, y )表示从x 到y 的一条单向通路, 它是有方向 的。x弧尾，y弧头 的。x弧尾，y弧头 有向图与无向图 有向图与无向图 有向图中：边用x, y表示，且x与y是有序的。 有向图中：边用x, y表示，且x与y是有序的。 a. 有向图中的边称为“弧” a. 有向图中的边称为“弧” b. x——弧尾或初始点 y——弧头或终端点 b. x——弧尾或初始点 y——弧头或终端点 无向图：边用(x, y) 表示，且顶x与y是无序的。 无向图：边用(x, y) 表示，且顶x与y是无序的。 完全图 完全图 在具有n 个顶点的有向图中，最大弧数为n(n-1) 在具有n 个顶点的有向图中，最大弧数为n(n-1) 在具有n 个顶点的无向图中，最大边数为n(n-1)/2 在具有n 个顶点的无向图中，最大边数为n(n-1)/2 顶点的度 顶点的度 无向图：与该顶点相关的边的数目 无向图：与该顶点相关的边的数目 有向图： 有向图： 入度ID(v) ：以该顶点为头的弧的数目 入度ID(v) ：以该顶点为头的弧的数目 出度 ：以该顶点为尾头的弧的数目 OD(v) OD(v) 出度 ：以该顶点为尾头的弧的数目 权 某些图的边具有与它相关的数, 称之为权。 权 某些图的边具有与它相关的数, 称之为权。 这种带权图叫做网络。 这种带权图叫做网络。 子图 设有两个图 G ＝(V, E) 和 G‘ ＝(V’, E ‘) 。 子图 设有两个图 G ＝(V, E) 和 G‘ ＝(V’, E ‘) 。 若 V’⊆ V 且E ‘⊆E, 则称图G’ 是 图G 的子图。 若 V’⊆ V 且E ‘⊆E, 则称图G’ 是 图G 的子图。 路径 在图G ＝(V, E) 中, 若从顶点v 出发, 沿一些边 路径 在图G ＝(V, E) 中, 若从顶点v 出发, 沿一些边 i i 经过一些顶点v , v , …, v