安徽理工大学：《数据结构》课程教学资源（PPT课件讲稿，C语言版，2018）第7章 图

第七章图 学习要点 理解图的基本概念及有关术语，掌握图的四种存储 结构的表示方法； 熟练掌握图的两种遍历（深度优先搜索和广度优先 搜索)，能列出按上述两种遍历算法得到的序列； 理解最小生成树的概念，能按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)有向网 与边有关的数据信息称为权。 边上带权的图称为网