第七章图 学习要点 理解图的基本概念及有关术语,掌握图的四种存储 结构的表示方法; 熟练掌握图的两种遍历(深度优先搜索和广度优先 搜索),能列出按上述两种遍历算法得到的序列; 理解最小生成树的概念,能按Prim算法构造最小生 成树; 掌握求最短路径、拓扑排序以及关键路径的算法思 想
第七章 图 ◼ 理解图的基本概念及有关术语,掌握图的四种存储 结构的表示方法; ◼ 熟练掌握图的两种遍历(深度优先搜索和广度优先 搜索),能列出按上述两种遍历算法得到的序列; ◼ 理解最小生成树的概念,能按Prim算法构造最小生 成树; ◼ 掌握求最短路径、拓扑排序以及关键路径的算法思 想。 学习要点
7.1图的的定义和术语 必图的定义 图是由一个顶点集V和一个描述顶点之间关系 (边或者弧)的集合VR构成的数据结构。 Graph (V,VR) 其中,VR={表示从v到w的一条弧,并称V为弧尾或 初始点,W为弧头或终端点。 谓词P(N,w)定义了弧的意义或信息
7.1 图的的定义和术语 图是由一个顶点集 V和一个描述顶点之间关系 (边或者弧)的集合VR构成的数据结构。 Graph = ( V , VR ) 其中,VR={| v,w∈V 且 P(v,w)} 表示从 v 到 w 的一条弧,并称 v 为弧尾或 初始点,w 为弧头或终端点。 谓词 P(v,w) 定义了弧 的意义或信息。 ❖ 图的定义
公图的应用举例 例1交通图(公路、铁路) 顶点:地点 边:连接地点的公路 例2电路图 顶点:元件 边:连接元件之间的线路 例3各种流程图 如产品的生产流程图 /3 顶点:工序 边:各道工序之间的顺序关系
❖ 图的应用举例 例1 交通图(公路、铁路) 顶点:地点 边:连接地点的公路 例2 电路图 顶点:元件 边:连接元件之间的线路 例3 各种流程图 如产品的生产流程图 顶点:工序 边:各道工序之间的顺序关系 V0 V3 V4 V1 V2 V0 V2 V3 V1
冬有向图和无向图 在图中,若用箭头标明了边是有方向性的,则称这 样的图为有向图,否则称为无向图。 在无向图中,一条边(x,y)与(y,x)表示的结果 相同,用圆括号表示。例如: G1= V1={v0,V1,v2,v3,V4} E1={N0,V1),(0,v3),(y1,V2),(V1,V4),(v2,V3),(V2,v4)}
❖ 有向图和无向图 G1= V1={v0, v1, v2, v3, v4 } E1={(v0,v1),(v0,v3),(v1,v2),(v1,v4),(v2,v3),(v2,v4)} V0 V3 V4 V1 V2 在图中,若用箭头标明了边是有方向性的,则称这 样的图为有向图,否则称为无向图。 在无向图中,一条边(x,y)与(y,x)表示的结果 相同,用圆括号表示。例如:
冬有向图和无向图 在有向图中,一条边与sy,x>表示的结果不 相同,用尖括号表示。表示从顶点出发向顶 点y的边,x为始点,y为终点。例如: G2= V2=v0,v1,v2,v3} A2={v0,V1>,,,}
在有向图中,一条边与表示的结果不 相同,用尖括号表示。表示从顶点x出发向顶 点y的边,x为始点,y为终点。例如: G2= V2={v0, v1, v2, v3} A2={, , , } V0 V2 V3 V1 ❖ 有向图和无向图
”名词和术语 顶点、边、弧、弧头、弧尾 完全图、稠密图、稀疏图 度、入度、出度 边的权、网图 路径、路径长度 回路、简单路径、简单回路 子图 连通图、连通分量 强连通图、强连通分量 生成树、生成森林
❖ 名词和术语 顶点、边、弧、弧头、弧尾 完全图、稠密图、稀疏图 度、入度、出度 边的权、网图 路径、路径长度 回路、简单路径、简单回路 子图 连通图、连通分量 强连通图、强连通分量 生成树、生成森林
·顶点、边、弧、弧头、弧尾 图中的数据元素通常称为顶点; 若∈VR,则表示从v到w的一条弧,且 称V为弧尾或初始点,称w为弧头或终端点。 若∈VR,必有则sw,V>∈VR,即VR是对称 的,则以无序对(,w)代替这两个有序对,表示从V和 w的一条边。 W
◼ 顶点、边、弧、弧头、弧尾 V W V W 图中的数据元素通常称为顶点; 若∈VR,则表示从v到w的一条弧,且 称v为弧尾或初始点,称w为弧头或终端点。 若∈VR,必有则∈VR,即VR是对称 的,则以无序对(v,w)代替这两个有序对,表示从v和 w的一条边
·完全图、稠密图、稀疏图 在一个无向图中,如果任意两顶点都有一条直接边 相连接,则称该图为无向完全图。 在一个有向图中,如果任意两顶点之间都有方向互 为相反的两条弧相连接,则称为有向完全图 若一个图接近完全图,称为稠密图; 称边数很少的 图为稀疏图 无向完全图 有向完全图
在一个无向图中,如果任意两顶点都有一条直接边 相连接,则称该图为无向完全图。 在一个有向图中,如果任意两顶点之间都有方向互 为相反的两条弧相连接,则称为有向完全图。 若一个图接近完全图,称为稠密图;称边数很少的 图为稀疏图。 无向完全图 有向完全图 1 3 2 1 3 2 ◼ 完全图、稠密图、稀疏图
度、入度、出度 在图中,一个顶点依附的边或弧的数目,称为该顶 点的度。在有向图中,以顶点V为起点的有向边数称 为顶点V的出度,以顶点V为终点的有向边数称为顶点 V的入度,入度和出度之和称为该顶点的度。 5 5 3
1 7 2 6 5 3 4 2 5 3 6 4 1 ◼ 度、入度、出度 在图中,一个顶点依附的边或弧的数目,称为该顶 点的度。在有向图中,以顶点V为起点的有向边数称 为顶点V的出度,以顶点V为终点的有向边数称为顶点 V的入度,入度和出度之和称为该顶点的度
·边的权、网 与边有关的数据信息称为权。 边上带权的图称为网。 2 3 A B 4 5 (a)无向网 (b)有向网 回
◼ 边的权、网 1 2 5 4 3 1 7 6 3 2 4 5 8 B C A 2 1 4 3 5 (a) 无向网 (b)有向网 与边有关的数据信息称为权。 边上带权的图称为网